![]() |
![]() |
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 listsCondensed Matter Group Meetings Algebra Reading Group on Sporadic Groups School of Mathematics EventsOther talksPerfect matchings in random sparsifications of Dirac hypergraphs Ultrafast, all-optical, and highly efficient imaging of molecular chirality Geometry of alternating projections in metric spaces with bounded curvature Sensing and metrology activities at NPL, India The development of an optically pumped magnetometer based MEG system Quantum simulations using ultra cold ytterbium |