A linear programming reformulation of the standard quadratic optimization problem.
Klerk, Etienne de.
Pasechnik, Dmitrii V.
Date of Issue2006
School of Physical and Mathematical Sciences
The problem of minimizing a quadratic form over the standard simplex is known as the standard quadratic optimization problem (SQO). It is NP-hard, and contains the maximum stable set problem in graphs as a special case. In this note, we show that the SQO problem may be reformulated as an (exponentially sized) linear program (LP). This reformulation also suggests a hierarchy of polynomial-time solvable LP’s whose optimal values converge finitely to the optimal value of the SQO problem. The hierarchies of LP relaxations from the literature do not share this finite convergence property for SQO, and we review the relevant counterexamples.
Journal of global optimization
© 2006 Springer Science+Business Media B.V. This is the author created version of a work that has been peer reviewed and accepted for publication by Journal of Global Optimization, Springer Science+Business Media B.V. It incorporates referee’s comments but changes resulting from the publishing process, such as copyediting, structural formatting, may not be reflected in this document. The published version is available at: DOI[http://dx.doi.org/10.1007/s10898-006-9037-9].