15th EUROPT Workshop on Advances in Continuous Optimization

Montréal, Canada, 12 — 14 juillet 2017

15th EUROPT Workshop on Advances in Continuous Optimization

Montréal, Canada, 12 — 14 juillet 2017

Horaire Auteurs Mon horaire
Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402

Computational Optimization

12 juil. 2017 13h30 – 15h10

Salle: TD Assurance Meloche Monnex

Présidée par Dominique Orban

4 présentations

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    13h30 - 13h55

    A fixed-point method for approximate projection onto the positive semidefinite cone

    • Douglas Gonçalves, prés., Federal University of Santa Catarina
    • Juliano B. Francisco, Federal University of Santa Catarina

    The projection of a symmetric matrix onto the positive semidefinite cone is an important problem with application in many different areas such as economy, physics and optimization. This problem has analytical solution, but it relies on the eigendecomposition of a given symmetric matrix which becomes prohibitive for larger dimension and dense matrices due to its cubic cost. We present a fixed-point iterative method for computing an approximation of such projection. Each iteration requires matrix-matrix products whose costs may be much less than O(n^3) for certain structured matrices. Numerical experiments showcase the attractiveness of the proposed approach for sparse symmetric banded matrices.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    13h55 - 14h20

    Parameter Optimization in the Nonlinear Stepsize Control Framework for Trust-Region Methods

    • Abel Siqueira, prés., Federal University of Paraná - Brazil
    • Geovani Grapiglia, Federal University of Paraná

    The Nonlinear Stepsize Control (NSC) framework proposed by Toint (2013) generalizes the classical trust-region algorithm and a few of its variants. In the NSC framework, two parameters ($\alpha$, $\beta$) control the update of the trust-region radius. We present an analysis of the sensitivity of the framework to those parameters, and our efforts in finding "best" parameters via derivative-free optimization.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    14h20 - 14h45

    Minimum L-infinity norm solution of linear under-determined systems

    • Montaz Ali, prés., University of the Witwatersrand

    We propose a new algorithm for the solution of minimum infinity solution of under-determined systems. It is a primal method like the one exists in the current literature but it is decidedly more in the spirit of a dual method. It is geometrically and conceptually clear and provides important new insight into the nature of the problem. The method is premised on the observation that at minimum there are at least n - (m -1) elements equal in absolute value and that these elements are maximal. The algorithm is thus logically divided into two parts; firstly a solution with n - (m - 1) elements equal is absolute value and maximal is obtained, and secondly the location of those elements is changed in such a way as to reduce the infinity norm at each step. Heuristics are used to identify an index set corresponding to the initial solution.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    14h45 - 15h10

    A new Python package for the solution of Procrustes Problems

    • Melissa Weber Mendonça, prés., UFSC

    The Procrustes problem can be described as finding rotations and scalings such that one can fit a set of data to another set. This is usually formulated as a solving a minimization problem on a Stiefel manifold (the set of orthogonal matrices). There are several applications to this problem, especially in the determination of rigid body movements, factor analysis and multidimensional scaling. While the Orthogonal Procrustes Problem (OPP) has an analytical solution through the singular value decomposition, the Weighted Orthogonal Procrustes Problem (WOPP) requires an iterative solution. Furthermore, due to the presence of several local minima, it is usually a computationally expensive problem to solve.

    In this work, we present a new package written in the Python programming language for the solution of both OPP and WOPP. Although there are tools available in Python for the solution of the former problem (sometimes referred to as Procrustes Analysis), there are no such tools for the solution of the latter. In this package, we implement a few different solution methods for the WOPP, and some tools to compare them on a list of well known problems.