In this paper we consider approximation algorithms for a class of quadratic optimization problems that contain orthogonality constraints, i.e. constraints of the form $X^TX=I$, where $X \in {\mathbb R}^{m \times n}$ is the optimization variable. Such class of problems, which we denote by (QP-OC), is quite general and captures several well–studied problems in the literature as special cases. In a recent work, Nemirovski [Math. Prog. 109:283–317, 2007] gave the first non–trivial approximation algorithm for (QP-OC). His algorithm is based on semidefinite programming and has an approximation guarantee of $O\left((m+n)^{1/3}\right)$. We improve upon this result by providing the first logarithmic approximation guarantee for (QP-OC). Specifically, we show that (QP-OC) can be approximated to within a factor of $O\left(\ln\left(\max\{m,n\}\right)\right)$. The main technical tool used in the analysis is a concentration inequality for the spectral norm of a sum of certain random matrices, which we develop using tools from functional analysis. Such inequality also has ramifications in the design of so–called safe tractable approximations of chance constrained optimization problems. In particular, we use it to improve a recent result of Ben–Tal and Nemirovski [Manuscript, 2007] on certain chance constrained linear matrix inequality systems.
Citation
Submitted.