Skip to main navigationSkip to main content
The University of Southampton
CORMSIS Centre for Operational Research, Management Sciences and Information Systems

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

16:00 - 17:00
1 March 2017
Room 1083, Building 2, Southampton Business School

For more information regarding this event, please email Dr Yuan Huang at .

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.

Speaker information

Professor Akiko Takeda,Institute of Statistical Mathematics, Japan,Akiko Takeda is a professor at the Institute of Statistical Mathematics, Japan. She holds B.E. and M.E. degrees in Administration Engineering from Keio University and Dr.Sc. degree in Information Science from Tokyo Institute of Technology. Her research interests include solution methods for decision making problems under uncertainty and non-convex optimization problems, which appear in financial engineering, machine learning and energy systems.

Privacy Settings