- Improved Approximation Bound for Quadratic Optimization Problems with Orthogonality Constraints Anthony Man-Cho So (manchosose.cuhk.edu.hk) Abstract: 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. Keywords: Quadratic Optimization, Orthogonality Constraints, Semidefinite Relaxation Category 1: Nonlinear Optimization Category 2: Linear, Cone and Semidefinite Programming Citation: Submitted. Download: [PDF]Entry Submitted: 11/19/2007Entry Accepted: 11/19/2007Entry Last Modified: 11/20/2007Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.