$$ \newcommand{\pmi}{\operatorname{pmi}} \newcommand{\inner}[2]{\langle{#1}, {#2}\rangle} \newcommand{\Pb}{\operatorname{Pr}} \newcommand{\E}{\mathbb{E}} \newcommand{\RR}{\mathbf{R}} \newcommand{\script}[1]{\mathcal{#1}} \newcommand{\Set}[2]{\{{#1} : {#2}\}} \newcommand{\argmin}[2]{\underset{#1}{\operatorname{argmin}} {#2}} \newcommand{\optmin}[3]{ \begin{align*} & \underset{#1}{\text{minimize}} & & #2 \\ & \text{subject to} & & #3 \end{align*} } \newcommand{\optmax}[3]{ \begin{align*} & \underset{#1}{\text{maximize}} & & #2 \\ & \text{subject to} & & #3 \end{align*} } \newcommand{\optfind}[2]{ \begin{align*} & {\text{find}} & & #1 \\ & \text{subject to} & & #2 \end{align*} } $$
A standard quadratic optimization problem is a program of the form
where is the standard -dimensional Euclidean simplex (). 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 -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^{1} and Parrilo^{2}, and they leverage these methodologies in approximation algorithms.
The copositive cone is the set of symmetric matrices
it is a (strict) superset of the positive semidefinite cone. Parrilo ^{2} 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 additive error).
de Klerk, E. and Pasechnik, D.V. (2002), Approximation of the Stability Number of a Graph via Copositive Programming, SIAM Journal of Optimization 12(4), 875–892 ↩
Parrilo, P.A. (2000), Structured Semidefinite Programs and Semi-algebraic Geometry Methods in Robustness and Optimization. PhD thesis, California Institute of Technology, | Pasadena, California, USA. Available at: http://www.cds.caltech.edu/ pablo/. ↩ ↩^{2}