  


Improved Approximation Bound for Quadratic Optimization Problems with Orthogonality Constraints
Anthony ManCho 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 (QPOC), is quite general and captures several wellstudied problems in the literature as special cases. In a recent work, Nemirovski [Math. Prog. 109:283317, 2007] gave the first nontrivial approximation algorithm for (QPOC). 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 (QPOC). Specifically, we show that (QPOC) 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 socalled safe tractable approximations of chance constrained optimization problems. In particular, we use it to improve a recent result of BenTal 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/2007 Modify/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  