Linear matrix inequality
From Wikimization
(New page: In convex optimization, a '''linear matrix inequality (LMI)''' is an expression of the form : <math>LMI(y):=A_0+y_1A_1+y_2A_2+\dots+y_m A_m\succeq0\,</math> where * <math>y=[y_i\,,~i\!...) |
(→LMI Geometry) |
||
(41 intermediate revisions not shown.) | |||
Line 1: | Line 1: | ||
- | In | + | In convex optimization, a '''linear matrix inequality (LMI)''' is an expression of the form |
- | : <math>LMI(y):=A_0+y_1A_1+y_2A_2+\ | + | : <math>LMI(y):=A_0+y_1A_1+y_2A_2+\ldots+y_m A_m\succeq0\,</math> |
where | where | ||
- | * <math>y=[y_i\,,~i\!=\!1\ | + | * <math>y=[y_i\,,~i\!=\!1\ldots m]</math> is a real vector, |
- | * <math>A_0\,, A_1\,, A_2\,,\ | + | * <math>A_0\,, A_1\,, A_2\,,\ldots\,A_m</math> are symmetric matrices in the subspace of <math>n\times n</math> symmetric matrices <math>\mathbb{S}^n</math>, |
- | * <math>B\succeq0 </math> is a generalized inequality meaning <math>B</math> is a | + | * <math>B\succeq0 </math> is a generalized inequality meaning <math>B</math> is a positive semidefinite matrix belonging to the positive semidefinite cone <math>\mathbb{S}_+</math> in the subspace of symmetric matrices <math>\mathbb{S}</math>. |
- | This linear matrix inequality specifies a | + | This linear matrix inequality specifies a convex constraint on ''y''. |
== Convexity of the LMI constraint == | == Convexity of the LMI constraint == | ||
- | <math>LMI(y)\succeq 0</math> is a convex constraint on ''y'' which means membership to a dual (convex) cone as we now explain: '''(''' | + | <math>LMI(y)\succeq 0</math> is a convex constraint on ''y'' which means membership to a dual (convex) cone as we now explain: '''('''[http://meboo.convexoptimization.com/Meboo.html Dattorro, Example 2.13.5.1.1]''')''' |
- | Consider a peculiar vertex-description for a | + | Consider a peculiar vertex-description for a [[Convex cones|convex cone]] defined over the positive semidefinite cone |
'''('''instead of the more common nonnegative orthant, <math>x\succeq0</math>''')''': | '''('''instead of the more common nonnegative orthant, <math>x\succeq0</math>''')''': | ||
Line 18: | Line 18: | ||
<math>\begin{array}{ll}\mathcal{K} | <math>\begin{array}{ll}\mathcal{K} | ||
- | \!\!&=\left\{\left[\begin{array}{c}\langle A_1\,,\,X^{}\rangle\\ | + | \!\!&=\left\{\left[\begin{array}{c}\langle A_1\,,\,X^{}\rangle\\:\\\langle A_m\;,\,X^{}\rangle\end{array}\right]|~X\!\succeq_{\!}0\right\}\subseteq_{}\mathbb{R}^m\\\\ |
- | &=\left\{\left[\begin{array}{c} | + | &=\left\{\left[\begin{array}{c}{\text svec}(A_1)^T\\:\\{\text svec}(A_m)^T\end{array}\right]{\text svec}X~|~X\!\succeq_{\!}0\right\}\\\\ |
- | &:=\;\{A\, | + | &:=\;\{A\,{\text svec}X~|~X\!\succeq_{\!}0_{}\} |
\end{array}</math> | \end{array}</math> | ||
where | where | ||
*<math>A\!\in_{}\!\mathbb{R}^{m\times n(n+1)/2}</math>, | *<math>A\!\in_{}\!\mathbb{R}^{m\times n(n+1)/2}</math>, | ||
- | *symmetric vectorization svec is a stacking of columns defined in (Dattorro ch.2), | + | *symmetric vectorization svec is a stacking of columns defined in '''('''[http://meboo.convexoptimization.com/Meboo.html Dattorro, ch.2.2.2.1]''')''', |
*<math>A_0=\mathbf{0}</math> is assumed without loss of generality. | *<math>A_0=\mathbf{0}</math> is assumed without loss of generality. | ||
- | <math>\mathcal{K}</math> is a convex cone because | + | <math>\mathcal{K}</math> is a [[Convex cones|convex cone]] because |
- | <math>A\,\ | + | <math>A\,{\text svec}{X_{p_1}}_{\,},_{_{}}A\,{\text svec}{X_{p_2}}\!\in\mathcal{K}~\Rightarrow~ |
- | A(\zeta_{\,} | + | A(\zeta_{\,}{\text svec}{X_{p_1}}+_{}\xi_{\,}{\text svec}{X_{p_2}})\in_{}\mathcal{K} |
- | + | {\text~~for\,all~\,}\zeta_{\,},\xi\geq0</math> | |
since a nonnegatively weighted sum of positive semidefinite matrices must be positive semidefinite. | since a nonnegatively weighted sum of positive semidefinite matrices must be positive semidefinite. | ||
- | Now consider the (closed convex) | + | Now consider the (closed convex) dual cone: |
<math>\begin{array}{rl}\mathcal{K}^* | <math>\begin{array}{rl}\mathcal{K}^* | ||
- | \!\!\!&=_{}\left\{_{}y~|~\langle z\,,\,y_{}\rangle\geq_{}0\,~\textrm{for\,all}~\,z\!\in_{_{}\!}\mathcal{K}_{}\right\}\subseteq_{}\ | + | \!\!\!&=_{}\left\{_{}y~|~\langle z\,,\,y_{}\rangle\geq_{}0\,~\textrm{for\,all}~\,z\!\in_{_{}\!}\mathcal{K}_{}\right\}\subseteq_{}\mathbb{R}^m\\ |
- | &=_{}\left\{_{}y~|~\langle z\,,\,y_{}\rangle\geq_{}0\,~\textrm{for\,all}~\,z_{\!}=_{\!}A\,\ | + | &=_{}\left\{_{}y~|~\langle z\,,\,y_{}\rangle\geq_{}0\,~\textrm{for\,all}~\,z_{\!}=_{\!}A\,{\text svec}X\,,~X\succeq0_{}\right\}\\ |
- | &=_{}\left\{_{}y~|~\langle A\,\ | + | &=_{}\left\{_{}y~|~\langle A\,{\text svec}X\,,~y_{}\rangle\geq_{}0\,~\textrm{for\,all}~\,X\!\succeq_{_{}\!}0_{}\right\}\\ |
- | &=\left\{y~|~\langle\ | + | &=\left\{y~|~\langle{\text svec}X\,,\,A^{T\!}y\rangle\geq_{}0\;~\textrm{for\,all}~\,X\!\succeq_{\!}0\right\}\\ |
- | &=\left\{y~|~\ | + | &=\left\{y~|~{\text svec}^{-1}(A^{T\!}y)\succeq_{}0\right\} |
\end{array}</math> | \end{array}</math> | ||
Line 52: | Line 52: | ||
This leads directly to an equally peculiar halfspace-description | This leads directly to an equally peculiar halfspace-description | ||
- | <math>\mathcal{K}^*=\{y\!\ | + | <math>\mathcal{K}^*=\{y\!\in\mathbb{R}^m~|\,\sum\limits_{j=1}^my_jA_j\succeq_{}0_{}\}</math> |
The summation inequality with respect to the positive semidefinite cone | The summation inequality with respect to the positive semidefinite cone | ||
Line 60: | Line 60: | ||
Although matrix <math>\,A\,</math> is finite-dimensional, <math>\mathcal{K}</math> is generally not a polyhedral cone | Although matrix <math>\,A\,</math> is finite-dimensional, <math>\mathcal{K}</math> is generally not a polyhedral cone | ||
- | (unless <math>\,m\,</math> equals 1 or 2) simply because <math>\,X\!\in\mathbb{S}_+^n\,</math> | + | (unless <math>\,m\,</math> equals 1 or 2) simply because <math>\,X\!\in\mathbb{S}_+^n\,.</math> |
- | + | Relative interior of <math>\mathcal{K}</math> may always be expressed | |
+ | <math>\textrm{rel\,int}\,\mathcal{K}=\{A\,{\text svec}X~|~X\!\succ0_{}\}.</math> | ||
- | <math>\textrm{rel\,int}\mathcal{K}=\textrm{int}\mathcal{K}</math> | + | Provided the <math>\,A_j</math> matrices are linearly independent, then |
+ | <math>\textrm{rel\,int}\,\mathcal{K}=\textrm{int}\,\mathcal{K}</math> | ||
- | meaning, | + | meaning, cone <math>\mathcal{K}</math> interior is nonempty; implying, dual cone <math>\mathcal{K}^*</math> is pointed ([http://meboo.convexoptimization.com/Meboo.html Dattorro, ch.2]). |
- | If matrix <math>\,A\,</math> has no nullspace | + | If matrix <math>\,A\,</math> has no nullspace, then |
- | <math>\,A\,\ | + | <math>\,A\,{\text svec}X\,</math> is an isomorphism in <math>\,X\,</math> between the positive semidefinite cone <math>\mathbb{S}_+^n</math> and range <math>\,\mathcal{R}(A)\,</math> of matrix <math>\,A.</math> |
- | + | That is sufficient for [[Convex cones|convex cone]] <math>\,\mathcal{K}\,</math> to be closed, and necessary to have relative boundary | |
+ | <math>\textrm{rel}\,\partial^{}\mathcal{K}=\{A\,{\text svec}X~|~X\!\succeq0\,,~X\!\not\succ_{\!}0_{}\}.</math> | ||
- | <math>\textrm{rel\,int}\mathcal{K}=\{ | + | <br> |
+ | Relative interior of the dual cone may always be expressed | ||
+ | <math>\textrm{rel\,int}\,\mathcal{K}^*=\{y\!\in_{}\!\mathbb{R}^m~|\,\sum\limits_{j=1}^my_jA_j\succ_{}0_{}\}.</math> | ||
- | + | When the <math>A_j</math> matrices are linearly independent, function <math>\,g(y)_{\!}:=_{_{}\!}\sum y_jA_j\,</math> is a linear bijection on <math>\mathbb{R}^m.</math> | |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
Inverse image of the positive semidefinite cone under <math>\,g(y)\,</math> | Inverse image of the positive semidefinite cone under <math>\,g(y)\,</math> | ||
- | must therefore have dimension <math>_{} | + | must therefore have dimension equal to <math>\dim\!\left(\mathcal{R}(A^{\rm T})_{}\!\cap{\text svec}\,\mathbb{S}_+^{_{}n}\right)</math> |
- | + | and relative boundary | |
+ | <math>\textrm{rel\,}\partial^{}\mathcal{K}^*=\{y\!\in_{}\!\mathbb{R}^m~|\,\sum\limits_{j=1}^my_jA_j\succeq_{}0\,,~\sum\limits_{j=1}^my_jA_j\not\succ0_{}\}.</math> | ||
- | <math>\textrm{int}\mathcal{K}^*=\{ | + | When this dimension is <math>\,m\,</math>, the dual cone interior is nonempty |
+ | <math>\textrm{rel\,int}\,\mathcal{K}^*=\textrm{int}\,\mathcal{K}^*</math> | ||
- | + | and closure of convex cone <math>\mathcal{K}</math> is pointed. | |
- | + | ||
- | <math> | + | |
== Applications == | == Applications == | ||
- | There are efficient numerical methods to determine whether an LMI is feasible (''i.e.'', whether there exists a vector <math>y</math> such that <math>LMI(y)\succeq0</math> ), or to solve a | + | There are efficient numerical methods to determine whether an LMI is feasible (''i.e.'', whether there exists a vector <math>y</math> such that <math>LMI(y)\succeq0</math> ), or to solve a convex optimization problem with LMI constraints. |
- | Many optimization problems in | + | Many optimization problems in control theory, system identification, and signal processing can be formulated using LMIs. The prototypical primal and dual semidefinite program are optimizations of a real linear function respectively subject to the primal and dual [[Convex cones|convex cones]] governing this LMI. |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
== External links == | == External links == | ||
- | * S. Boyd, L. El Ghaoui, E. Feron, and V. Balakrishnan, [http://www.stanford.edu/~boyd/lmibook | + | * S. Boyd, L. El Ghaoui, E. Feron, and V. Balakrishnan, [http://www.stanford.edu/~boyd/lmibook Linear Matrix Inequalities in System and Control Theory] |
- | + | ||
- | + | ||
- | [ | + | * C. Scherer and S. Weiland, [http://w3.ele.tue.nl/nl/cs/education/courses/hyconlmi Course on Linear Matrix Inequalities in Control], Dutch Institute of Systems and Control (DISC). |
Current revision
In convex optimization, a linear matrix inequality (LMI) is an expression of the form
where
- is a real vector,
- are symmetric matrices in the subspace of symmetric matrices ,
- is a generalized inequality meaning is a positive semidefinite matrix belonging to the positive semidefinite cone in the subspace of symmetric matrices .
This linear matrix inequality specifies a convex constraint on y.
Contents |
Convexity of the LMI constraint
is a convex constraint on y which means membership to a dual (convex) cone as we now explain: (Dattorro, Example 2.13.5.1.1)
Consider a peculiar vertex-description for a convex cone defined over the positive semidefinite cone
(instead of the more common nonnegative orthant, ):
for given ,
where
- ,
- symmetric vectorization svec is a stacking of columns defined in (Dattorro, ch.2.2.2.1),
- is assumed without loss of generality.
is a convex cone because
since a nonnegatively weighted sum of positive semidefinite matrices must be positive semidefinite.
Now consider the (closed convex) dual cone:
that follows from Fejer's dual generalized inequalities for the positive semidefinite cone:
This leads directly to an equally peculiar halfspace-description
The summation inequality with respect to the positive semidefinite cone is known as a linear matrix inequality.
LMI Geometry
Although matrix is finite-dimensional, is generally not a polyhedral cone (unless equals 1 or 2) simply because
Relative interior of may always be expressed
Provided the matrices are linearly independent, then
meaning, cone interior is nonempty; implying, dual cone is pointed (Dattorro, ch.2).
If matrix has no nullspace, then is an isomorphism in between the positive semidefinite cone and range of matrix
That is sufficient for convex cone to be closed, and necessary to have relative boundary
Relative interior of the dual cone may always be expressed
When the matrices are linearly independent, function is a linear bijection on
Inverse image of the positive semidefinite cone under must therefore have dimension equal to
and relative boundary
When this dimension is , the dual cone interior is nonempty
and closure of convex cone is pointed.
Applications
There are efficient numerical methods to determine whether an LMI is feasible (i.e., whether there exists a vector such that ), or to solve a convex optimization problem with LMI constraints. Many optimization problems in control theory, system identification, and signal processing can be formulated using LMIs. The prototypical primal and dual semidefinite program are optimizations of a real linear function respectively subject to the primal and dual convex cones governing this LMI.
External links
- S. Boyd, L. El Ghaoui, E. Feron, and V. Balakrishnan, Linear Matrix Inequalities in System and Control Theory
- C. Scherer and S. Weiland, Course on Linear Matrix Inequalities in Control, Dutch Institute of Systems and Control (DISC).