This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Ai, W. Articles by Zhang, S. Search for Related Content

On the Low Rank Solutions for Linear Matrix Inequalities

School of Science, Beijing University of Posts and Telecommunications, Beijing 100876, China
Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, Hong Kong
Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, Hong Kong
wenbaoai{at}gmail.com
ywhuang{at}se.cuhk.edu.hk
zhang{at}se.cuhk.edu.hk, http://www.se.cuhk.edu.hk/zhang/

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.

Key Words: rank reduction; linear matrix inequality; joint numerical range
History: Received: October 1, 2006; revision received: March 28, 2008;