Optimization Online


Improved Approximation Bound for Quadratic Optimization Problems with Orthogonality Constraints

Anthony Man-Cho So (manchoso***at***se.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/2007
Entry Accepted: 11/19/2007
Entry Last Modified: 11/20/2007

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society