Foundations and Trends® in Optimization > Vol 2 > Issue 1-2

Low-Rank Semidefinite Programming: Theory and Applications

Alex Lemon, Stanford University, USA, adlemon@stanford.edu Anthony Man-Cho So, The Chinese University of Hong Kong, Hong Kong, manchoso@se.cuhk.edu.hk Yinyu Ye, Stanford University, USA, yyye@stanford.edu
 
Suggested Citation
Alex Lemon, Anthony Man-Cho So and Yinyu Ye (2016), "Low-Rank Semidefinite Programming: Theory and Applications", Foundations and TrendsĀ® in Optimization: Vol. 2: No. 1-2, pp 1-156. http://dx.doi.org/10.1561/2400000009

Published: 04 Aug 2016
© 2016 A. Lemon, A. M.-C. So, Y. Ye
 
Subjects
Optimization,  Dimensionality Reduction,  Operations research,  Randomness in Computation,  Signal Processing for Communications
 

Free Preview:

Article Help

Share

Download article
In this article:
1. Introduction
Part 1. Theory
2. Exact Solutions and Theorems about Rank
3. Heuristics and Approximate Solutions
Part 2. Applications
4. Trust-Region Problems
5. QCQPs with Complex Variables
Appendices
References

Abstract

Finding low-rank solutions of semidefinite programs is important in many applications. For example, semidefinite programs that arise as relaxations of polynomial optimization problems are exact relaxations when the semidefinite program has a rank-1 solution. Unfortunately, computing a minimum-rank solution of a semidefinite program is an NP-hard problem. In this paper we review the theory of low-rank semidefinite programming, presenting theorems that guarantee the existence of a low-rank solution, heuristics for computing low-rank solutions, and algorithms for finding low-rank approximate solutions. Then we present applications of the theory to trust-region problems and signal processing.

DOI:10.1561/2400000009
ISBN: 978-1-68083-136-8
278 pp. $99.00
Buy book
 
ISBN: 978-1-68083-137-5
278 pp. $260.00
Buy E-book
Table of contents:
1. Introduction
Part 1. Theory
2. Exact Solutions and Theorems about Rank
3. Heuristics and Approximate Solutions
Part 2. Applications
4. Trust-Region Problems
5. QCQPs with Complex Variables
Appendices
References

Low-Rank Semidefinite Programming: Theory and Applications

Finding low-rank solutions of semidefinite programs is important in many applications. For example, semidefinite programs that arise as relaxations of polynomial optimization problems are exact relaxations when the semidefinite program has a rank-1 solution. Unfortunately, computing a minimum-rank solution of a semidefinite program is an NP-hard problem. This monograph reviews the theory of low-rank semidefinite programming, presenting theorems that guarantee the existence of a low-rank solution, heuristics for computing low-rank solutions, and algorithms for finding low-rank approximate solutions. It then presents applications of the theory to trust-region problems and signal processing.

 
OPT-009