Abstract
Numerous problems in control and systems theory can be formulated in terms of linear matrix inequalities (LMI). Since solving an LMI amounts to a convex optimization problem, such formulations are known to be numerically tractable. However, the interest in LMI-based design techniques has really surged with the introduction of efficient interior-point methods for solving LMIs with a polynomial-time complexity. This paper describes one particular method called the Projective Method. Simple geometrical arguments are used to clarify the strategy and convergence mechanism of the Projective algorithm. A complexity analysis is provided, and applications to two generic LMI problems (feasibility and linear objective minimization) are discussed.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
F. Alizadeh, Optimization over the positive-semidefinite cone: Interior-point methods and combinatorial applications,SIAM J. on Optimization 5 (1995).
A. Berman,Cones, Matrices, and Mathematical Programming, Lecture Notes in Economics and Mathematical Systems, Vol. 79 (Springer, Berlin, 1973).
S.P. Boyd and L. El Ghaoui, Method of centers for minimizing generalized eigenvalues,Linear Algebra and its Applications 188 (1993) 63–111.
S.P. Boyd, L. El Ghaoui, E. Feron and V. Balakrishnan,Linear Matrix Inequalities in Systems and Control Theory, SIAM Studies in Applied Mathematics (SIAM, Philadelphia, PA, 1994).
J.C. Doyle, K. Glover, P. Khargonekar and B. Francis, State-space solutions to standardH 2 andH control problems,IEEE Transactions on Automatic Control 34 (1989) 831–847.
M.K.H. Fan, A second-order interior point method for solving linear matrix inequality problems, submitted toSIAM J. on Control and Optimization (1993).
P. Gahinet and P. Apkarian, A linear matrix Inequality approach toH control,Internat. J. Robust and Nonlinear Control 4 (1994) 421–448.
P. Gahinet, A. Nemirovski, A.J. Laub and M. Chilali, The LMI control toolbox, in:Proc. Conf. Dec. Contr. (1994) 2038–2041.
P. Gahinet, A. Nemirovski, A.J. Laub and M. Chilali,LMI Control Toolbox (The MathWorks Inc., 1995).
G.H. Golub and C.F. Van Loan,Matrix Computations (Johns Hopkins University Press, Baltimore, 1983).
F. Jarre, An interior-point method for minimizing the maximum eigenvalue of a linear combination of matrices,SIAM J. on Optimization 31 (1993).
N. Karmarkar, A new polynomial-time algorithm for linear programming,Combinatorica 4 (1984) 373–395.
M. Kojima, S. Shindoh and S. Hara, Interior-point methods for the monotone linear complementarity problem in symmetric matrices, Technical Report B-282, Dept. of Information Sciences, Tokyo Institute of Technology, 1994.
Yu. Nesterov and A. Nemirovski, Polynomial-time barrier methods in convex programming,Ekonomika i Matem. Metody 24 (1988), in Russian; translation:Matekon.
Yu. Nesterov and A. Nemirovski, An interior-point method for generalized linear-fractional problems,Mathematical Programming 69 (1995) 177–204.
Yu. Nesterov and A. Nemirovski,Interior Point Polynomial Methods in Convex Programming: Theory and Applications, SIAM Studies in Applied Mathematics (SIAM, Philadelphia, PA, 1994).
M.L. Overton, Large-scale optimization of eigenvalues,SIAM J. on Optimization 2 (1992) 88–120.
F. Rendl and H. Wolkowicz, Applications of parametric programming and eigenvalue maximization to the quadratic assignment problem,Mathematical Programming 53 (1992) 63–78.
L. Vandenberghe and S. Boyd, Primal-dual potential reduction method for problems involving matrix inequalities,Mathematical Programming 69 (1995) 205–236.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Gahinet, P., Nemirovski, A. The projective method for solving linear matrix inequalities. Mathematical Programming 77, 163–190 (1997). https://doi.org/10.1007/BF02614434
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF02614434