University of Birmingham > Talks@bham > Optimisation and Numerical Analysis Seminars > Global optimization via eigenvalues

## Global optimization via eigenvaluesAdd to your list(s) Download to your calendar using vCal - Yuji Nakatsukasa (Oxford University)
- Thursday 01 December 2016, 12:00-13:00
- University House, room 108.
If you have a question about this talk, please contact Sergey Sergeev. 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 optimization 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). This talk is part of the Optimisation and Numerical Analysis Seminars series. ## This talk is included in these lists:Note that ex-directory lists are not shown. |
## Other listsTheoretical Physics Journal Club and Group Meeting Test School of Mathematics Events## Other talksBest Response Dynamics on Random Graphs Generalised hydrodynamics and universalities of transport in integrable (and non-integrable) spin chains Lovász' Theorem and Comonads in Finite Model Theory Quantum simulation of strongly correlated fermions: A theory perspective |