Approximating Quadratic Programs with Postitive Semidefinite Constraints

Abstract:

We describe a polynomial time approximation algorithm to the problem of maximizing a quadratic form subject to quadratic constraints specified by PSD matrices. A special case, that has applications for clustering, is optimizing quadratic forms over the unit cube.

Approximation algorithms with similar guarantees are known, and there is evidence that this factor is optimal. The following analysis is particularly simple