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
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 fixedpoint method for approximate projection onto the positive semidefinite cone
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 fixedpoint iterative method for computing an approximation of such projection. Each iteration requires matrixmatrix 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 TrustRegion Methods
The Nonlinear Stepsize Control (NSC) framework proposed by Toint (2013) generalizes the classical trustregion algorithm and a few of its variants. In the NSC framework, two parameters ($\alpha$, $\beta$) control the update of the trustregion radius. We present an analysis of the sensitivity of the framework to those parameters, and our efforts in finding "best" parameters via derivativefree optimization.

02:20 PM  02:45 PM
Minimum Linfinity norm solution of linear underdetermined systems
We propose a new algorithm for the solution of minimum infinity solution of underdetermined 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
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.