In
convex optimization
Convex optimization is a subfield of mathematical optimization that studies the problem of minimizing convex functions over convex sets (or, equivalently, maximizing concave functions over convex sets). Many classes of convex optimization prob ...
, a linear matrix inequality (LMI) is an expression of the form
:
where
*
symmetric matrices
In linear algebra, a symmetric matrix is a square matrix that is equal to its transpose. Formally,
Because equal matrices have equal dimensions, only square matrices can be symmetric.
The entries of a symmetric matrix are symmetric with r ...
\mathbb^n,
*
B\succeq0 is a generalized inequality meaning
B is a
positive semidefinite matrix
In mathematics, a symmetric matrix M with real entries is positive-definite if the real number z^\textsfMz is positive for every nonzero real column vector z, where z^\textsf is the transpose of More generally, a Hermitian matrix (that is, a ...
belonging to the positive semidefinite cone
\mathbb_+ in the subspace of symmetric matrices
\mathbb{S}.
This linear matrix inequality specifies a
convex
Convex or convexity may refer to:
Science and technology
* Convex lens, in optics
Mathematics
* Convex set, containing the whole line segment that joins points
** Convex polygon, a polygon which encloses a convex set of points
** Convex polytop ...
constraint on ''y''.
Applications
There are efficient numerical methods to determine whether an LMI is feasible (''e.g.'', whether there exists a vector ''y'' such that LMI(''y'') ≥ 0), or to solve a
convex optimization
Convex optimization is a subfield of mathematical optimization that studies the problem of minimizing convex functions over convex sets (or, equivalently, maximizing concave functions over convex sets). Many classes of convex optimization prob ...
problem with LMI constraints.
Many optimization problems in
control theory
Control theory is a field of mathematics that deals with the control of dynamical systems in engineered processes and machines. The objective is to develop a model or algorithm governing the application of system inputs to drive the system to a ...
,
system identification
The field of system identification uses statistical methods to build mathematical models of dynamical systems from measured data. System identification also includes the optimal design of experiments for efficiently generating informative data f ...
and
signal processing
Signal processing is an electrical engineering subfield that focuses on analyzing, modifying and synthesizing '' signals'', such as sound, images, and scientific measurements. Signal processing techniques are used to optimize transmissions, ...
can be formulated using LMIs. Also LMIs find application in
Polynomial Sum-Of-Squares. The prototypical primal and dual
semidefinite program Semidefinite programming (SDP) is a subfield of convex optimization concerned with the optimization of a linear objective function (a user-specified function that the user wants to minimize or maximize)
over the intersection of the cone of positiv ...
is a minimization of a real linear function respectively subject to the primal and dual
convex cone
In linear algebra, a ''cone''—sometimes called a linear cone for distinguishing it from other sorts of cones—is a subset of a vector space that is closed under scalar multiplication; that is, is a cone if x\in C implies sx\in C for every .
...
s governing this LMI.
Solving LMIs
A major breakthrough in convex optimization lies in the introduction of
interior-point method
Interior-point methods (also referred to as barrier methods or IPMs) are a certain class of algorithms that solve linear and nonlinear convex optimization problems.
An interior point method was discovered by Soviet mathematician I. I. Dikin in 1 ...
s. These methods were developed in a series of papers and became of true interest in the context of LMI problems in the work of
Yurii Nesterov
Yurii Nesterov is a Russian mathematician, an internationally recognized expert in convex optimization, especially in the development of efficient algorithms and numerical optimization analysis. He is currently a professor at the University of L ...
and
Arkadi Nemirovski
Arkadi Nemirovski (born March 14, 1947) is a professor at the H. Milton Stewart School of Industrial and Systems Engineering at the Georgia Institute of Technology. He has been a leader in continuous optimization and is best known for his wor ...
.
See also
*
Semidefinite programming Semidefinite programming (SDP) is a subfield of convex optimization concerned with the optimization of a linear objective function (a user-specified function that the user wants to minimize or maximize)
over the intersection of the cone of positiv ...
*
Spectrahedron
In convex geometry, a spectrahedron is a shape that can be represented as a linear matrix inequality. Alternatively, the set of positive semidefinite matrices forms a convex cone in , and a spectrahedron is a shape that can be formed by interse ...
*
Finsler's lemma
References
* Y. Nesterov and A. Nemirovsky, ''Interior Point Polynomial Methods in Convex Programming.'' SIAM, 1994.
External links
* S. Boyd, L. El Ghaoui, E. Feron, and V. Balakrishnan
Linear Matrix Inequalities in System and Control Theory (book in pdf)
* C. Scherer and S. Weiland
Linear Matrix Inequalities in Control
Convex optimization