Conference abstracts

Session B7 - Numerical Linear Algebra

July 13, 17:30 ~ 18:00 - Room B5

Eigenvalue Optimization with Applications to Semidefinite Programs and Rectangular Eigenvalue Problems

Emre Mengi

Koc University, Turkey   -

The majority of interest into eigenvalue optimization has originated from its intimate connection with convex semidefinite programs. This interest has diminished to a degree after the invention of interior point methods, which made numerical solutions of small convex semidefinite programs possible. Nevertheless to this day the convex semidefinite programs with large matrix variables or with large number of constraints stand as a challenge. On the other side, nonconvex eigenvalue optimization problems have been explored especially after late 1980s, the research in this direction has concentrated on particular problems for instance motivated by control theory and depending on only a few optimization variables.

This talk starts with a brief review of a unified algorithm for nonconvex eigenvalue optimization problems over a few variables. The algorithm is based on global piece-wise quadratic models for the eigenvalue functions. It works very well in practice provided bounds on second derivatives of eigenvalue functions are available analytically or heuristically.

The second part features a greedy subspace framework for eigenvalue optimization problems involving large matrices. At every iteration the subspace framework solves a projected eigenvalue optimization problem onto a small subspace, and expands the subspace with the addition of the eigenvectors at the optimal points of the small problem. The proposed framework converges superlinearly both in theory and in practice.

The third part concerns the adaption of the subspace framework for convex semidefinite programs with large matrix variables. Here we benefit from the eigenvalue optimization characterization of the dual of a semidefinite program. The small problems are solved by interior point methods. One difficulty is to start with a subspace that leads to a feasible semidefinite program, we describe an approach to overcome this difficulty.

Finally, we focus on large generalized rectangular eigenvalue problems whose spectra consist of a few imaginary eigenvalues. Such problems arise for instance from robust stability considerations of dissipative Hamiltonian systems. Extraction of their imaginary eigenvalues can be viewed as a nonconvex eigenvalue optimization problem depending on one variable, on which we employ the subspace framework. The small projected problems are nonconvex and solved by the unified algorithm.

Joint work with Nicat Aliyev (Koc University, Turkey), Fatih Kangal (Koc University, Turkey), Karl Meerbergen (KU Leuven, Belgium), Wim Michiels (KU Leuven, Belgium) and Emre Alper Yildirim (Koc University, Turkey).

View abstract PDF

FoCM 2017, based on a nodethirtythree design.