A Linear Programming Reformulation of the Standard Quadratic Optimization Problem

E. de Klerk, D.V. Pasechnik

Research output: Working paperDiscussion paperOther research output

250 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

    de Klerk, E., & Pasechnik, D. V. (2005). A Linear Programming Reformulation of the Standard Quadratic Optimization Problem. (CentER Discussion Paper; Vol. 2005-24). Operations research.