×

Lowest-rank solutions of continuous and discrete Lyapunov equations over symmetric cone. (English) Zbl 1291.90189

Summary: The low-rank solutions of continuous and discrete Lyapunov equations are of great importance but generally difficult to compute in control system analysis and design. Fortunately, M. Mesbahi and G. P. Papavassilopoulos [IEEE Trans. Autom. Control 42, No. 2, 239–243 (1997; Zbl 0872.93029)] 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 B. Recht et al. [SIAM Rev. 52, No. 3, 471–501 (2010; Zbl 1198.90321)].

MSC:

90C26 Nonconvex programming, global optimization
90C25 Convex programming
90C59 Approximation methods and heuristics in mathematical programming
15A06 Linear equations (linear algebraic aspects)
15B48 Positive matrices and their generalizations; cones of matrices

Software:

LMIRank
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Barnett, S., Introduction to Mathematical Control Theory (1975), Oxford University Press: Oxford University Press Oxford · Zbl 0307.93001
[2] Benner, P., Control Theory, Handbook of Linear Algebra (2006), Chapman & Hall/CRC: Chapman & Hall/CRC Boca Raton, FL
[3] Boyd, S.; El Ghaoui, L.; Feron, E.; Balakrishnan, V., Linear Matrix Inequalities in System and Control Theory, SIAM Stud. Appl. Math., vol. 15 (1994) · Zbl 0816.93004
[4] Barnett, S.; Storey, C., Some applications of the Lyapunov matrix equation, IMA J. Appl. Math., 4, 33-42 (1968) · Zbl 0155.12902
[5] Cottle, R. W.; Pang, J. S.; Stone, R. E., The Linear Complementarity Problem (1992), Academic Press: Academic Press Boston · Zbl 0757.90078
[6] Fares, B.; Apkarian, P.; Noll, D., An augmented Lagrangian method for a class of LMI constrained problems in robust control theory, Internat. J. Control, 74, 348-360 (2001) · Zbl 1015.93016
[7] Fazel, M.; Hindi, H.; Boyd, S., A rank minimization heuristic with application to minimum order system approximation, (Proc. Amer. Contr. Conf.. Proc. Amer. Contr. Conf., IEEE (2001)), 4734-4739
[8] Faraut, J.; Korányi, A., Analysis on Symmetric Cones (1994), Oxford University Press: Oxford University Press New York · Zbl 0841.43002
[9] Glicksberg, I. L., A further generalization of the Kakutani fixed point theorem, with application to Nash equilibrium points, Proc. Amer. Math. Soc., 3, 1, 170-174 (1952) · Zbl 0046.12103
[10] Grigoriadis, K. M.; Beran, E. B., Alternating projection algorithms for linear matrix inequalities problems with rank constraints, (El Ghaoui, L.; Niculescu, S.-I., Advances in Linear Matrix Inequality Methods in Control (2000), SIAM: SIAM Philadelphia), 251-267, Ch. 13 · Zbl 0956.93021
[11] Ghaoui, L. El.; Gahinet, P., Rank minimization under LMI constraints: a framework for output feedback problems, (Proc. European Contr. Conf. (July 1993))
[12] Gudmundsson, T.; Laub, A., Approximate solution of large sparse Lyapunov equations, IEEE Trans. Automat. Control, 39, 1110-1114 (1994) · Zbl 0816.93041
[13] El Ghaoui, L.; Oustry, F.; Ait Rami, M., A cone complementarity linearization algorithm for static output-feedback and related problems, IEEE Trans. Automat. Control, 42, 1171-1176 (1997) · Zbl 0887.93017
[14] Gajić, Z.; Qureshi, M., Lyapunov Matrix Equation in System Stability and Control, Mathematics in Science and Engineering (1995), Academic Press: Academic Press San Diego, CA
[15] Gugercin, S.; Sorensen, D. C.; Antoulas, A. C., A modified low-rank Smith method for large-scale Lyapunov equations, Numer. Algorithms, 32, 27-55 (2003) · Zbl 1034.93020
[16] Gowda, M. S.; Sznajder, R., Schur complements, Schur determinantal and Haynsworth inertia formulas in Euclidean Jordan algebras, Linear Algebra Appl., 432, 1553-1559 (2010) · Zbl 1264.15014
[17] Gowda, M. S.; Tao, J., Z-transformations on proper and symmetric cones, Math. Program., 117, 1-2, 195-221 (2009) · Zbl 1167.90022
[18] Gowda, M. S.; Tao, J., Some inequalities involving determinants, eigenvalues, and Schur complements in Euclidean Jordan algebras, Positivity, 15, 3, 381-399 (2011) · Zbl 1236.15047
[19] Hammarling, S. J., Numerical solution of the stable non-negative definite Lyapunov equation, IMA J. Numer. Anal., 2, 303-323 (1982) · Zbl 0492.65017
[20] Hochbruck, M.; Starke, G., Preconditioned Krylov subspace methods for Lyapunov matrix equations, SIAM J. Matrix Anal. Appl., 16, 1, 156-171 (1995) · Zbl 0827.65048
[21] Jaimoukha, I.; Kasenally, E., Krylov subspace methods for solving large Lyapunov equations, SIAM J. Numer. Anal., 31, 227-251 (1994) · Zbl 0798.65060
[22] Kong, L. C.; Tunçel, L.; Xiu, N. H., Equivalent conditions for Jacobian nonsingularity in linear symmetric cone programming, J. Optim. Theory Appl., 148, 2, 364-389 (2011) · Zbl 1229.90080
[23] Larin, V. B.; Aliev, F. A., Construction of square root factor for solution of the Lyapunov matrix equation, Systems Control Lett., 20, 109-112 (1993) · Zbl 0782.93082
[24] Lancaster, P.; Tismenetsky, M., The Theory of Matrices (1985), Academic Press: Academic Press Orlando, FL · Zbl 0516.15018
[25] Li, J. R.; White, J., Low-rank solution of Lyapunov equations, SIAM Rev., 46, 4, 693-713 (2004) · Zbl 1068.65053
[26] Luo, Z. Y.; Xiu, N. H., Feasibility and solvability of Lyapunov-type linear programming over symmetric cones, Positivity, 14, 481-499 (2010) · Zbl 1225.90099
[27] Luo, Z. Y.; Xiu, N. H.; Kong, L. C., Lyapunov-type least-squares problems over symmetric cones, Linear Algebra Appl., 437, 2498-2515 (2012) · Zbl 1260.65032
[28] Mesbahi, M., On the semi-definite programming solution of the least order dynamic output feedback synthesis, (Proc. Amer. Contr. Conf. (1999))
[29] Mesbahi, M.; Papavassilopoulos, G. P., A cone programming approach to the bilinear matrix inequality problem and its geometry, Math. Program., 77, 247-272 (1997) · Zbl 0888.90119
[30] Mesbahi, M.; Papavassilopoulos, G. P., On the rank minimization problems over a positive semidefinite linear matrix inequality, IEEE Trans. Automat. Control, 42, 2, 239-243 (1997) · Zbl 0872.93029
[31] Orsi, R.; Helmke, U.; Moore, J. B., A Newton-like method for solving rank constrained linear matrix inequalities, Automatica, 42, 1875-1882 (2006) · Zbl 1222.90032
[32] Parrilo, P. A., Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization (May 2000), California Institute of Technology, PhD thesis
[33] Parrilo, P. A.; Sven, K., On cone-invariant linear matrix inequalities, IEEE Trans. Automat. Control, 45, 8, 1558-1563 (2000) · Zbl 0988.93029
[34] Penzl, T., Eigenvalue decay bounds for solutions of Lyapunov equations: the symmetric case, Systems Control Lett., 40, 139-144 (2000) · Zbl 0977.93034
[35] Penzl, T., A cyclic low rank Smith method for large sparse Lyapunov equations, SIAM J. Sci. Comput., 21, 4, 1401-1418 (2000) · Zbl 0958.65052
[36] Recht, B.; Fazel, M.; Parrilo, P. A., Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Rev., 52, 3, 471-501 (2010) · Zbl 1198.90321
[37] Simoncini, V., A new iterative method for solving large-scale Lyapunov matrix equations, SIAM J. Sci. Comput., 29, 1268-1288 (2007) · Zbl 1146.65038
[38] Safonov, M. G.; Goh, K. C.; Ly, J. H., Control system synthesis via bilinear matrix inequalities, (Proc. 1994 Amer. Contr. Conf.. Proc. 1994 Amer. Contr. Conf., Baltimore, MD (July 1994))
[39] Safonov, M. G.; Papavassilopoulos, G. P., The diameter of an intersection of ellipsoids and BMI robust synthesis, (Proc. IFAC Symp. Robust Contr.. Proc. IFAC Symp. Robust Contr., Rio de Janeiro, Brazil (Sept. 1994))
[40] Sun, D. F.; Sun, J., Löwner’s operator and spectral functions in Euclidean Jordan algebras, Math. Oper. Res., 33, 2, 421-445 (2008) · Zbl 1218.90197
[41] Skelton, R. E.; Iwasaki, T.; Grigoriadis, K., A Unified Algebraic Approach to Linear Control Design (1998), Taylor and Francis: Taylor and Francis London
[42] Vandereycken, B.; Vandewalle, S., A Riemannian optimization approach for computing low-rank solutions of Lyapunov equations, SIAM J. Matrix Anal. Appl., 31, 5, 2553-2579 (2010) · Zbl 1221.65108
[43] Wachspress, E., Iterative solution of the Lyapunov matrix equation, Appl. Math. Lett., 107, 87-90 (1988) · Zbl 0631.65037
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.