Low-Rank Semidefinite Programming: Theory and Applications (Foundations and Trends in Optimization)

Alex Lemon, Anthony Man-Cho So, Yinyu Ye

  • 出版商: Now Publishers Inc
  • 出版日期: 2016-08-04
  • 售價: $3,870
  • 貴賓價: 9.5$3,677
  • 語言: 英文
  • 頁數: 180
  • 裝訂: Paperback
  • ISBN: 1680831364
  • ISBN-13: 9781680831368
  • 下單後立即進貨 (約1週~2週)


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.