Papers

Solving standard quadratic optimization problems via semidefinite and copositive programming (Bomze 2002)

A standard quadratic optimization problem is a program of the form

$$\begin{array}{ll} \mbox{minimize} & \frac{1}{2} x^TQx \\ \mbox{subject to} & x \in \Delta, \end{array}$$

where $\Delta$ is the standard $n$-dimensional Euclidean simplex ($\{ x \in \RR^n_{+} : \sum_{i=1}^{n} x_i = 1\}$). This problem is non-convex, but it can be reformulated as a convex program known as a copositive problem. Copositive programming is NP-hard (which students of convex optimization might find surprising, as this means that convex optimization is NP-hard); hence, quadratic optimization over the simplex is also NP-hard. Nonetheless, Bomze and de Klerk provide in this paper a polynomial-time approximation scheme (PTAS) for quadratic optimization, which furnishes $\epsilon$-suboptimal solutions in time that is polynomial in the problem dimension. In particular, the authors show how to approximate the copositive cone using either linear inequalities or linear matrix inequalities (LMIs) using the methodologies of de Klerk and Pasechnik¹ and Parrilo², and they leverage these methodologies in approximation algorithms.

The copositive cone $\script{C}_n$ is the set of symmetric matrices

$$\Set{X \in \script{S}^n}{y^TXy \geq 0,\quad \text{for all } y \in \RR^n_+};$$

it is a (strict) superset of the positive semidefinite cone. Parrilo ² showed that the copositive cone can be approximated by a system of LMIs. Bomze’s SDP PTAS replaces the copositive cone in the reformulated quadratic program with an appropriate LMI system, while his LP PTAS replaces it with polyhedral constraints. Both schemes provide a hierarchy of relaxations that can be used to obtain tighter and tighter approximates of the optimal solution. Each scheme is in fact a PTAS because SDPs and LPs can be solved in polynomial time (up to an $\epsilon$ additive error).