Global optimization via eigenvalues

Yuji Nakatsukasa (The University of Oxford)


While non-convex optimization problems are generally regarded as difficult or computationally
intractable, the Courant-Fischer theorem for symmetric eigenvalue problems suggests that each
eigenpair corresponds to a stationary point of a non-convex optimization problem (in this case the
Rayleigh quotient). More generally, matrix eigenvalue problems can be regarded as an important
class of optimization problems that can be solved efficiently.
This observation suggests conversely that perhaps a global solution for some non-convex optimiza-
tion problems can be obtained by solving an eigenvalue problem. In this work we identify such
optimization problems, and show that they lead to a variety of eigenvalue problems, including
generalized, polynomial and multiparameter eigenvalue problems, all of which can be solved reliably and in polynomial time, and essentially non-iteratively.
Specifically, we consider non-convex QCQP (quadratically constrained quadratic programming)
QCQP is known to be NP-hard in general (when the number of constraints k is not fixed), and for k ≥ 2 fixed, it has been an open problem whether they are polynomial-time solvable until recently. We show that (i) for QCQP with one constraint, k = 1, it can be reduced to essentially a single generalized eigenvalue problem, (ii) for QCQP with two constraints, k = 2, the problem can be reduced to a two-parameter eigenvalue problem, and (iii) unconstrained optimization problems with cubic regularization can be reduced to quadratic eigenvalue problems.

Based on joint work with Satoru Adachi, Satoru Iwata, Shinsaku Sakaue and Akiko Takeda (University of Tokyo).

Import this event to your Outlook calendar
▲ Up to the top