A Linear Programming Reformulation of the Standard Quadratic Optimization Problem

E. de Klerk, D.V. Pasechnik

Research output: Working paperDiscussion paperOther research output

240 Downloads (Pure)

Abstract

The problem of minimizing a quadratic form over the standard simplex is known as the standard quadratic optimization problem (SQO).It is NPhard, 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.
Original languageEnglish
Place of PublicationTilburg
PublisherOperations research
Number of pages12
Volume2005-24
Publication statusPublished - 2005

Publication series

NameCentER Discussion Paper
Volume2005-24

Keywords

  • linear programming
  • standard quadratic optimization
  • positive polynomials

Fingerprint Dive into the research topics of 'A Linear Programming Reformulation of the Standard Quadratic Optimization Problem'. Together they form a unique fingerprint.

Cite this