Rank-constrained optimization and its applications.(English)Zbl 1376.93042

Summary: This paper investigates an iterative approach to solve the general Rank-Constrained Optimization Problems (RCOPs) defined to optimize a convex objective function subject to a set of convex constraints and rank constraints on unknown rectangular matrices. In addition, Rank Minimization Problems (RMPs) are introduced and equivalently transformed into RCOPs by introducing a quadratic matrix equality constraint. The rank function is discontinuous and nonconvex, thus the general RCOPs are classified as NP-hard in most of the cases. An Iterative Rank Minimization (IRM) method, with convex formulation at each iteration, is proposed to gradually approach the constrained rank. The proposed IRM method aims at solving RCOPs with rank inequalities constrained by upper or lower bounds, as well as rank equality constraints. Proof of the convergence to a local minimizer with at least a sublinear convergence rate is provided. Four representative applications of RCOPs and RMPs, including system identification, output feedback stabilization, and structured $$H_2$$ controller design problems, are presented with comparative simulation results to verify the feasibility and improved performance of the proposed IRM method.

MSC:

 93B52 Feedback control 90C22 Semidefinite programming 93D15 Stabilization of systems by feedback 93B30 System identification 65K05 Numerical mathematical programming methods

Software:

 [1] Boyd, S.; Vandenberghe, L., Convex optimization (2004), Cambridge University Press · Zbl 1058.90049 [2] Candès, E. J.; Recht, B., Exact matrix completion via convex optimization, Foundations of Computational Mathematics, 9, 6, 717-772 (2009) · Zbl 1219.90124 [3] Dai, R.; Sun, C., Path planning of spatial rigid motion with constrained attitude, Journal of Guidance, Control, and Dynamics, 38, 1356-1365 (2015) [4] Dattorro, J., Convex optimization & Euclidean distance geometry (2015), Meboo Publishing: Meboo Publishing USA [6] Delgado, R. A.; Agüero, J. C.; Goodwin, G. C., A novel representation of rank constraints for real matrices, Linear Algebra and its Applications, 496, 452-462 (2016) · Zbl 1332.15005 [9] El Ghaoui, L.; Oustry, F.; AitRami, M., A cone complementarity linearization algorithm for static output-feedback and related problems, IEEE Transactions on Automatic Control, 42, 8, 1171-1176 (1997) · Zbl 0887.93017 [10] Fares, B.; Apkarian, P.; Noll, D., An augmented Lagrangian method for a class of LMI-constrained problems in robust control theory, International Journal of Control, 74, 4, 348-360 (2001) · Zbl 1015.93016 [11] Fazel, M., Matrix rank minimization with applications (2002), Stanford University, (Ph.D. thesis) [15] Golub, G. H.; Hoffman, A.; Stewart, G. W., A generalization of the eckart-young-mirsky matrix approximation theorem, Linear Algebra and its Applications, 88, 317-327 (1987) · Zbl 0623.15020 [16] Grigoriadis, K. M.; Skelton, R. E., Low-order control design for LMI problems using alternating projection methods, Automatica, 32, 8, 1117-1125 (1996) · Zbl 0855.93026 [18] Horn, R. A.; Johnson, C. R., Matrix analysis (2012), Cambridge University Press [19] Kim, S.; Moon, Y., Structurally constrained $$H_2$$ and $$H_\infty$$ control: A rank-constrained LMI approach, Automatica, 42, 9, 1583-1588 (2006) · Zbl 1128.93325 [20] Lee, K.; Bresler, Y., Admira: Atomic decomposition for minimum rank approximation, IEEE Transactions on Information Theory, 56, 9, 4402-4416 (2010) · Zbl 1366.94112 [22] Markovsky, I., Structured low-rank approximation and its applications, Automatica, 44, 4, 891-909 (2008) · Zbl 1283.93061 [23] Markovsky, I., Low rank approximation: algorithms, implementation, applications (2011), Springer Science & Business Media [24] Markovsky, I.; Usevich, K., Software for weighted structured low-rank approximation, Journal of Computational and Applied Mathematics, 256, 278-292 (2014) · Zbl 1314.65067 [25] Markovsky, I.; Van Huffel, S., High-performance numerical algorithms and software for structured total least squares, Journal of Computational and Applied Mathematics, 180, 2, 311-331 (2005) · Zbl 1070.65025 [26] Markovsky, I.; Van Huffel, S., Left vs right representations for solving weighted low-rank approximation problems, Linear Algebra and its Applications, 422, 2, 540-552 (2007) · Zbl 1115.65047 [27] Markovsky, I.; Willems, J. C.; Rapisarda, P.; De Moor, B. L., Algorithms for deterministic balanced subspace identification, Automatica, 41, 5, 755-766 (2005) · Zbl 1093.93006 [28] Meka, R.; Jain, P.; Caramanis, C.; Dhillon, I. S., Rank minimization via online learning, (Proceedings of the 25th international conference on machine learning (2008), ACM), 656-663 [29] Mesbahi, M., On the rank minimization problem and its control applications, Systems & Control Letters, 33, 1, 31-36 (1998) · Zbl 0902.93027 [30] Mesbahi, M.; Papavassilopoulos, G. P., On the rank minimization problem over a positive semidefinite linear matrix inequality, IEEE Transactions on Automatic Control, 42, 2, 239-243 (1997) · Zbl 0872.93029 [31] Meyer, G., Geometric optimization algorithms for linear regression on fixed-rank matrices (2011), University of Liege: University of Liege Belgium, (Ph.D. thesis) [32] Mohan, K.; Fazel, M., Iterative reweighted algorithms for matrix rank minimization, The Journal of Machine Learning Research, 13, 1, 3441-3473 (2012) · Zbl 1436.65055 [33] Orsi, R.; Helmke, U.; Moore, J. B., A Newton-like method for solving rank constrained linear matrix inequalities, Automatica, 42, 11, 1875-1882 (2006) · Zbl 1222.90032 [34] Recht, B., A simpler approach to matrix completion, The Journal of Machine Learning Research, 12, 3413-3430 (2011) · Zbl 1280.68141 [35] Recht, B.; Fazel, M.; Parrilo, P. A., Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Review, 52, 3, 471-501 (2010) · Zbl 1198.90321 [38] Sturm, J. F., Using sedumi 1.02, a matlab toolbox for optimization over symmetric cones, Optimization Methods and Software, 11, 1-4, 625-653 (1999) · Zbl 0973.90526 [41] Ten Berge, J. M.; Kiers, H. A., A numerical approach to the approximate and the exact minimum rank of a covariance matrix, Psychometrika, 56, 2, 309-315 (1991) · Zbl 0850.62462 [42] Urrutia, G.; Delgado, R. A.; Agüero, J. C., Low-order control design using a novel rank-constrained optimization approach, (2016 australian control conference (AuCC) (2016), IEEE), 38-42 [43] Vandereycken, B., Riemannian and multilevel optimization for rank-constrained matrix problems (2010), Katholieke Universiteit Leuven, (Ph.D. thesis) [44] Willems, J. C., Paradigms and puzzles in the theory of dynamical systems, IEEE Transactions on Automatic Control, 36, 3, 259-294 (1991) · Zbl 0737.93004 [45] Zhao, Y.-B., An approximation theory of matrix rank minimization and its application to quadratic equations, Linear Algebra and its Applications, 437, 1, 77-93 (2012) · Zbl 1242.65086