Optimization Online


A linear programming reformulation of the standard quadratic optimization problem

Etienne De Klerk (E.deKlerk***at***uvt.nl)
Dmitrii, V. Pasechnik (D.V.Pasechnik***at***uvt.nl)

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.

Keywords: linear programming, standard quadratic optimization, positive polynomials

Category 1: Global Optimization (Theory )

Category 2: Linear, Cone and Semidefinite Programming (Linear Programming )

Category 3: Linear, Cone and Semidefinite Programming

Citation: CentER discussion paper: 2005-24, Tilburg University, The Netherlands, 2005.

Download: [PDF]

Entry Submitted: 03/03/2005
Entry Accepted: 03/04/2005
Entry Last Modified: 03/03/2005

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society