The low-rank solutions of continuous and discrete Lyapunov equations are of great importance but generally difficult to achieve in control system analysis and design. Fortunately, Mesbahi and Papavassilopoulos [On the rank minimization problems over a positive semidefinite linear matrix inequality, IEEE Trans. Auto. Control, Vol. 42, No. 2 (1997), 239-243] showed that with the semidefinite cone constraint, the lowest-rank solutions of the discrete Lyapunov inequality can be efficiently solved by a linear semidefinite programming. In this paper, we further show that the lowest-rank solutions of both the continuous and discrete Lyapunov equations over symmetric cone are unique and can be exactly solved by their convex relaxations, the symmetric cone linear programming problems. Therefore, they are polynomial-time solvable. Since the underlying symmetric cone is a more general algebraic setting which contains the semidefinite cone as a special case, our results also answer an open question proposed by Recht, Fazel and Parrilo in [Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Review, Vol.52, No.3, (2010), 471-501].
Citation
Submitted, 10/10/2012