Generalized S-Lemma and strong duality in nonconvex quadratic programming

摘要

On the basis of a new topological minimax theorem, a simple and unified approach is developed to Lagrange duality in nonconvex quadratic programming. Diverse generalizations as well as equivalent forms of the S-Lemma, providing a thorough study of duality for single constrained quadratic optimization, are derived along with new strong duality conditions for multiple constrained quadratic optimization. The results allow many quadratic programs to be solved by solving one or just a few SDP's (semidefinite programs) of about the same size, rather than solving a sequence, often infinite, of SDP's or linear programs of a very large size as in most existing methods.