Low-Rank Semidefinite Programming: Theory and Applications Contributor(s): Lemon, Alex (Author), Man-Cho So, Anthony (Author), Ye, Yinyu (Author) |
|
ISBN: 1680831364 ISBN-13: 9781680831368 Publisher: Now Publishers OUR PRICE: $94.05 Product Type: Paperback - Other Formats Published: May 2016 |
Additional Information |
BISAC Categories: - Computers | Computer Science - Mathematics | Optimization - Technology & Engineering | Electrical |
Series: Foundations and Trends(r) in Optimization |
Physical Information: 0.38" H x 6.14" W x 9.21" (0.57 lbs) 180 pages |
Descriptions, Reviews, Etc. |
Publisher Description: 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. |