A Linear Programming Reformulation of the Standard Quadratic Optimization Problem

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.

MoreLess

Year of publication:	2005
Authors:	de Klerk, Etienne ; Pasechnik, D.V.
Institutions:	Tilburg University, Center for Economic Research
Subject:	linear programming \| standard quadratic optimization \| positive polynomials

More details

Extent:	application/pdf
Series:	Discussion Paper.
Type of publication:	Book / Working Paper
Notes:	The text is part of a series CentER Discussion Paper Number 2005-24
Classification:	C61 - Optimization Techniques; Programming Models; Dynamic Analysis
Source:	RePEc - Research Papers in Economics

Persistent link: https://www.econbiz.de/10011092227