Eigenvalue programming beyond matrices

Abstract

In this paper we analyze and solve eigenvalue programs, which consist of the task of minimizing a function subject to constraints on the "eigenvalues" of the decision variable. Here, by making use of the FTvN systems framework introduced by Gowda, we interpret "eigenvalues" in a broad fashion going beyond the usual eigenvalues of matrices. This allows us to shed new light on classical problems such as inverse eigenvalue problems and also leads to new applications. In particular, after analyzing and developing a simple projected gradient algorithm for general eigenvalue programs, we show that eigenvalue programs can be used to express what we call vanishing quadratic constraints. A vanishing quadratic constraint requires that a given system of convex quadratic inequalities be satisfied and at least a certain number of those inequalities must be tight. As a particular case, this includes the problem of finding a point $x$ in the intersection of $m$ ellipsoids in such a way that $x$ is also in the boundary of at least $\ell$ of the ellipsoids, for some fixed $\ell >0$. At the end, we also present some numerical experiments.

19 pages, 2 figures. A few minor changes and new experiments with multiple SDP blocks

References in corpus (7)

• Calculus of the exponent of Kurdyka-Łojasiewicz inequality and its applications to linear convergence of first-order methods
• Splitting methods with variable metric for KL functions
• Transversality and alternating projections for nonconvex sets
• Convergence rate analysis for averaged fixed point iterations in the presence of Hölder regularity
• Convergence analysis under consistent error bounds
• Generalized subdifferentials of spectral functions over Euclidean Jordan algebras
• Spectrally Constrained Optimization

Cited by in corpus (1)

• Spectrally Constrained Optimization