15th EUROPT Workshop on Advances in Continuous Optimization

Montréal, Canada, 12 — 14 July 2017

15th EUROPT Workshop on Advances in Continuous Optimization

Montréal, Canada, 12 — 14 July 2017

Schedule Authors My Schedule

Computational Optimization

Jul 12, 2017 01:30 PM – 03:10 PM

Location: TD Assurance Meloche Monnex

Chaired by Dominique Orban

4 Presentations

  • 01:30 PM - 01:55 PM

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

    • Douglas Gonçalves, presenter, 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.

  • 01:55 PM - 02:20 PM

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

    • Abel Siqueira, presenter, 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.

  • 02:20 PM - 02:45 PM

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

    • Montaz Ali, presenter, 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.

  • 02:45 PM - 03:10 PM

    A new Python package for the solution of Procrustes Problems

    • Melissa Weber Mendonça, presenter, 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.