skip to main content
10.5555/1496770.1496900guideproceedingsArticle/Chapter ViewAbstractPublication PagessodaConference Proceedingsconference-collections
research-article
Free access

Improved approximation bound for quadratic optimization problems with orthogonality constraints

Published: 04 January 2009 Publication History

Abstract

In this paper we consider the problem of approximating a class of quadratic optimization problems that contain orthogonality constraints, i.e. constraints of the form XTX = I, where X ε Rm x n is the optimization variable. This 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 [17] gave the first non--trivial approximation algorithm for (Qp--Oc). His algorithm is based on semidefinite programming and has an approximation guarantee of O ((m + n)1/3). 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(ln (max{m, n})). The main technical tool used in the analysis is the so--called non--commutative Khintchine inequality, which allows us to prove a concentration inequality for the spectral norm of a Rademacher sum of matrices. As a by-product, we resolve in the affirmative a conjecture of Nemirovski concerning the typical spectral norm of a sum of certain random matrices. The aforementioned concentration inequality also has ramifications in the design of so-called safe tractable approximations of chance constrained optimization problems. In particular, we use it to simplify and improve a recent result of Ben--Tal and Nemirovski [4] concerning certain chance constrained linear matrix inequality systems.

References

[1]
A. Agarwal, M. Charikar, K. Makarychev, and Y. Makarychev. O(√log n) Approximation Algorithms for Min UnCut, Min 2CNF Deletion, and Directed Cut Problems. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC '05), pages 573--581, 2005.
[2]
N. Alon, K. Makarychev, Y. Makarychev, and A. Naor. Quadratic Forms on Graphs. Inventiones Mathematicae, 163(3):499--522, 2006.
[3]
S. Arora, J. R. Lee, and A. Naor. Euclidean Distortion and the Sparsest Cut. Journal of the American Mathematical Society, 21(1):1--21, 2008.
[4]
A. Ben-Tal and A. Nemirovski. On Safe Tractable Approximations of Chance Constrained Linear Matrix Inequalities. Manuscript, 2007.
[5]
A. Buchholz. Operator Khintchine Inequality in Non--Commutative Probability. Mathematische Annalen, 319:1--16, 2001.
[6]
V. H. de la Peña and E. Giné. Decoupling: From Dependence to Independence. Probability and Its Applications. Springer--Verlag, 1999.
[7]
M. X. Goemans. Semidefinite Programming in Combinatorial Optimization. Mathematical Programming, 79:143--161, 1997.
[8]
M. X. Goemans and D. P. Williamson. Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. Journal of the ACM, 42(6):1115--1145, 1995.
[9]
J. C. Gower and G. B. Dijksterhuis. Procrustes Problems, volume 30 of Oxford Statistical Science Series. Oxford University Press, 2004.
[10]
M. Grötschel, L. Lovász, and A. Schrijver. Geometric Algorithms and Combinatorial Optimization, volume 2 of Algorithms and Combinatorics. Springer--Verlag, second corrected edition, 1993.
[11]
S. He, Z.-Q. Luo, J. Nie, and S. Zhang. Semidefinite Relaxation Bounds for Indefinite Homogeneous Quadratic Optimization. SIAM Journal on Optimization, 19(2):503--523, 2008.
[12]
R. Holzman and D. J. Kleitman. On the Product of Sign Vectors and Unit Vectors. Combinatorica, 12(3):303--316, 1992.
[13]
R. A. Horn and C. R. Johnson. Matrix Analysis. Cambridge University Press, 1985.
[14]
T. C. Koopmans and M. Beckmann. Assignment Problems and the Location of Economic Activities. Econometrica, 25(1):53--76, 1957.
[15]
Z.-Q. Luo, N. D. Sidiropoulos, P. Tseng, and S. Zhang. Approximation Bounds for Quadratic Optimization with Homogeneous Quadratic Constraints. SIAM Journal on Optimization, 18(1):1--28, 2007.
[16]
F. Lust-Piquard. Inégalités de Khintchine dans Cp (1 < p < ∞). Comptes Rendus de l'Académie des Sciences de Paris, Série I, 303(7):289--292, 1986.
[17]
A. Nemirovski. Sums of Random Symmetric Matrices and Quadratic Optimization under Orthogonality Constraints. Mathematical Programming, Series B, 109(2--3):283--317, 2007.
[18]
A. Nemirovski, C. Roos, and T. Terlaky. On Maximization of Quadratic Form over Intersection of Ellipsoids with Common Center. Mathematical Programming, Series A, 86:463--473, 1999.
[19]
A. Nemirovski and A. Shapiro. Convex Approximations of Chance Constrained Programs. SIAM Journal on Optimization, 17(4):969--996, 2006.
[20]
A. Nemirovski and A. Shapiro. Scenario Approximations of Chance Constraints. In G. Calafiore and F. Dabbene, editors, Probabilistic and Randomized Methods for Design under Uncertainty, pages 3--47. Springer--Verlag, London, 2006.
[21]
Y. Nesterov, H. Wolkowicz, and Y. Ye. Semidefinite Programming Relaxations of Nonconvex Quadratic Optimization. In H. Wolkowicz, R. Saigal, and L. Van-denberghe, editors, Handbook of Semidefinite Programming: Theory, Algorithms, and Applications, International Series in Operations Research and Management Science, pages 361--419. Kluwer Academic Publishers, 2000.
[22]
P. M. Pardalos and H. Wolkowicz, editors. Quadratic Assignment and Related Problems, volume 16 of DI-MACS Series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society, 1994.
[23]
G. Pisier. Non--Commutative Vector Valued Lp --Spaces and Completely p--Summing Maps. Astérisque, 247, 1998.
[24]
A. M.-C. So. On the Performance of Semidefinite Relaxation MIMO Detectors for QAM Constellations. Manuscript, 2008.
[25]
A. M.-C. So. Probabilistic Analysis of the Semidefinite Relaxation Detector in Digital Communications. Manuscript, 2008.
[26]
A. M.-C. So, Y. Ye, and J. Zhang. A Unified Theorem on SDP Rank Reduction. To appear in Mathematics of Operations Research, 2008.
[27]
A. M.-C. So, J. Zhang, and Y. Ye. On Approximating Complex Quadratic Optimization Problems via Semidefinite Programming Relaxations. Mathematical Programming, Series B, 110(1):93--110, 2007.
[28]
N. Tomczak-Jaegermann. The Moduli of Smoothness and Convexity and the Rademacher Averages of Trace Classes Sp (1 ≤ p < ∞). Studia Mathematica, 50:163--182, 1974.
[29]
J. A. Tropp. The Random Paving Property for Uniformly Bounded Matrices. Studia Mathematica, 185(1):67--82, 2008.
[30]
H. Wolkowicz. Semidefinite Programming Approaches to the Quadratic Assignment Problem. In P. M. Pardalos and L. S. Pitsoulis, editors, Nonlinear Assignment Problems: Algorithms and Applications, pages 143--174. Kluwer Academic Publishers, 2000.

Cited By

View all
  • (2011)Low rank matrix-valued chernoff bounds and approximate matrix multiplicationProceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms10.5555/2133036.2133145(1422-1436)Online publication date: 23-Jan-2011

Recommendations

Comments

Information & Contributors

Information

Published In

cover image Guide Proceedings
SODA '09: Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms
January 2009
1297 pages

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 04 January 2009

Qualifiers

  • Research-article

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)26
  • Downloads (Last 6 weeks)7
Reflects downloads up to 30 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2011)Low rank matrix-valued chernoff bounds and approximate matrix multiplicationProceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms10.5555/2133036.2133145(1422-1436)Online publication date: 23-Jan-2011

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media