Optimization Online


Solving standard quadratic optimization problems via linear, semidefinite and copositive programming

I.M. Bomze (immanuel.bomze***at***univie.ac.at)
E. De Klerk (E.deKlerk***at***uvt.nl)

Abstract: The problem of minimizing a (non-convex) quadratic function over the simplex (the standard quadratic optimization problem) has an exact convex reformulation as a copositive programming problem. In this paper we show how to approximate the optimal solution by approximating the cone of copositive matrices via systems of linear inequalities, and, more refined, linear matrix inequalities (LMI's). In particular, we show that our approach leads to a polynomial-time approximation scheme for the standard quadratic optimization problem. This is an improvement on the previous complexity result by Nesterov who showed that a 2/3-approximation is always possible. Numerical examples from various applications are provided to illustrate our approach.

Keywords: Approximation algorithms, stability number, semidefinite programming, copositive cone, standard quadratic optimization

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 2: Global Optimization (Theory )

Category 3: Combinatorial Optimization (Other )

Citation: I. Bomze, E. de Klerk. Solving standard quadratic optimization problems via semidefinite and copositive programming. J. Global Optimization, Volume 24, Issue 2, pp. 163-185, 2002.

Download: [Postscript]

Entry Submitted: 05/23/2001
Entry Accepted: 05/24/2001
Entry Last Modified: 05/14/2007

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