Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/94850
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
http://hdl.handle.net/10220/9276
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:
File Description SizeFormat 
7. A linear programming reformulation of the standard quadratic optimization problem.pdf205.01 kBAdobe PDFThumbnail
View/Open

Google ScholarTM

Check

Altmetric

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.