Finding low-rank solutions of sparse linear matrix inequalities using convex optimization

Abstract. This paper is concerned with the problem of finding a low-rank solution of an arbitrary sparse linear matrix inequality (LMI). To this end, we map the sparsity of the LMI problem into a graph. We develop a theory relating the rank of the minimum-rank solution of the LMI problem to the sparsity of its underlying graph. Furthermore, we propose three graph-theoretic convex programs to obtain a low-rank solution. Two of these convex optimization problems need a tree decomposition of the sparsity graph, which is an NP-hard problem in the worst case. The third one does not rely on any computationally-expensive graph analysis and is always polynomial-time solvable. The results of this work can be readily applied to three separate problems of minimum-rank matrix completion, conic relaxation for polynomial optimization, and affine rank minimization. The results are finally illustrated on two applications of optimal distributed control and nonlinear optimization for electrical networks