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.
|Place of Publication||Tilburg|
|Number of pages||12|
|Publication status||Published - 2005|
|Name||CentER Discussion Paper|
- linear programming
- standard quadratic optimization
- positive polynomials