On the low rank solutions for linear matrix inequalities

Wenbao Ai, Yongwei Huang, Shuzhong Zhang

Research output: Contribution to journalArticle

12 Scopus citations


In this paper we present a polynomial-time procedure to find a low-rank solution for a system of linear matrix inequalities (LMI). The existence of such a low-rank solution was shown in the work of Au-Yeung and Poon and the work of Barvinok. In the approach of Au-Yeung and Poon an earlier unpublished manuscript of Bohnenblust played an essential role. Both proofs in the work of Au-Yeung and Poon and that of Barvinok are nonconstructive in nature. The aim of this paper is to provide a polynomial-time constructive procedure to find such a low-rank solution approximatively. Extensions of our new results and their relations to some of the known results in the literature are discussed.

Original languageEnglish (US)
Pages (from-to)965-975
Number of pages11
JournalMathematics of Operations Research
Issue number4
StatePublished - Nov 1 2008


  • Joint numerical range
  • Linear matrix inequality
  • Rank reduction

Fingerprint Dive into the research topics of 'On the low rank solutions for linear matrix inequalities'. Together they form a unique fingerprint.

Cite this