![]() |
![]() |
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
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 listsEPS - College Research Teas Bravo Particle Physics SeminarsOther talksThe tragic destiny of Mileva Marić Einstein Quantifying the economic and environmental effects of the RCEP Parameter estimation for macroscopic pedestrian dynamics models using trajectory data TBA Quantum-Enhanced Interferometry hunting in the Dark Universe: How Gravitatioanl-wave detector technology can be (ab)used for other mysteries in fundamental physics. TBA |