CORMSIS Seminar - Nonconvex Quadratic Optimization with One or Two Constraints Event

Event details

Abstract of the talk: We consider a class of nonconvex quadratic optimization problems having one or two quadratic constraints (1QCQP or 2QCQP). The motivation of this work comes primarily from binary classification in machine learning, but the problems themselves are important; some types of 1QCQP and 2QCQP are well-studied as the trust-region subproblem (TRS) and Celis-Dennis-Tapia (CDT) problem, respectively. Although both are nonconvex optimization problems, the TRS has been shown to be solvable in polynomial time. For the CDT problem, no polynomial-time algorithm was known until Bienstock's recent work. In this talk, we provide a polynomial-time global optimization algorithm for 2QCQP as well as 1QCQP. The algorithm first finds all the points that satisfy the Karush-Kuhn-Tucker (KKT) optimality conditions by solving a generalized eigenvalue problem and then identifies a relevant KKT point with the minimum objective function value. We show numerical results for applying the algorithm for 2QCQP. To the best of our knowledge, no polynomial-time algorithm has been implemented and used to solve large-scale 2QCQP. Parts of this talk are based on joint work with S. Iwata, Y. Nakatsukasa and S. Sakaue.