On the Low Rank Solutions for Linear Matrix Inequalities

• 成果类型: Article
• 署名作者: Ai, Wenbao; Huang, Yongwei; Zhang, Shuzhong
• 署名单位: Beijing University of Posts & Telecommunications; Chinese University of Hong Kong
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1080.0331
• 发表日期: 2008
• 页码: 965-975
• 关键词: error-bounds

摘要

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.