Please use this identifier to cite or link to this item:
|Title:||A linear programming reformulation of the standard quadratic optimization problem||Authors:||Klerk, Etienne de.
Pasechnik, Dmitrii V.
|Keywords:||DRNTU::Science::Mathematics||Issue Date:||2006||Source:||Klerk, E. d., & Pasechnik, D. V. (2006). A linear programming reformulation of the standard quadratic optimization problem. Journal of Global Optimization, 37(1), 75-84.||Series/Report no.:||Journal of global optimization||Abstract:||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.||URI:||https://hdl.handle.net/10356/94850
|DOI:||http://dx.doi.org/10.1007/s10898-006-9037-9||Rights:||© 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].||Fulltext Permission:||open||Fulltext Availability:||With Fulltext|
|Appears in Collections:||SPMS Journal Articles|
Files in This Item:
|7. A linear programming reformulation of the standard quadratic optimization problem.pdf||205.01 kB||Adobe PDF|
Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.