Linear matrix inequality

From Wikimization

(Difference between revisions)

Jump to: navigation, search

Revision as of 14:35, 5 December 2008

In convex optimization, a linear matrix inequality (LMI) is an expression of the form

$LaTeX: LMI(y):=A_0+y_1A_1+y_2A_2+\dots+y_m A_m\succeq0\,$

where

$LaTeX: y=[y_i\,,~i\!=\!1\dots m]$ is a real vector,
$LaTeX: A_0\,, A_1\,, A_2\,,\dots\,A_m$ are symmetric matrices in the subspace of $LaTeX: n\times n$ symmetric matrices $LaTeX: \mathbb{S}^n$ ,
$LaTeX: B\succeq0$ is a generalized inequality meaning $LaTeX: B$ is a positive semidefinite matrix belonging to the positive semidefinite cone $LaTeX: \mathbb{S}_+$ in the subspace of symmetric matrices $LaTeX: \mathbb{S}$ .

This linear matrix inequality specifies a convex constraint on y.

1 Convexity of the LMI constraint
2 LMI Geometry
3 Applications
4 External links

Convexity of the LMI constraint

$LaTeX: LMI(y)\succeq 0$ 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 closed convex cone defined over the positive semidefinite cone

(instead of the more common nonnegative orthant, $LaTeX: x\succeq0$ ):

for $LaTeX: X\!\in\mathbb{S}^n$ given $LaTeX: \,A_j\!\in\mathbb{S}^n$ , $LaTeX: \,j\!=\!1\ldots m$

$LaTeX: \begin{array}{ll}\mathcal{K} \!\!&=\left\{\left[\begin{array}{c}\langle A_1\,,\,X^{}\rangle\\\vdots\\\langle A_m\;,\,X^{}\rangle\end{array}\right]|~X\!\succeq_{\!}0\right\}\subseteq_{}\reals^m\\\\ &=\left\{\left[\begin{array}{c}\textrm{svec}(A_1)^T\\\vdots\\\textrm{svec}(A_m)^T\end{array}\right]\!\textrm{svec}X~|~X\!\succeq_{\!}0\right\}\\\\ &:=\;\{A\,\textrm{svec}X~|~X\!\succeq_{\!}0_{}\} \end{array}$

where

$LaTeX: A\!\in_{}\!\mathbb{R}^{m\times n(n+1)/2}$ ,
symmetric vectorization svec is a stacking of columns defined in (Dattorro, Ch.2.2.2.1),
$LaTeX: A_0=\mathbf{0}$ is assumed without loss of generality.

$LaTeX: \mathcal{K}$ is a convex cone because

$LaTeX: A\,\textrm{svec}{X_{{\rm p}_1}}_{\,},_{_{}}A\,\textrm{svec}{X_{{\rm p}_2}}\!\in\mathcal{K}~\Rightarrow~ A(\zeta_{\,}\textrm{svec}{X_{{\rm p}_1\!}}+_{}\xi_{\,}\textrm{svec}{X_{{\rm p}_2}})\in_{}\mathcal{K} \textrm{~~for\,all~\,}\zeta_{\,},\xi\geq0$

since a nonnegatively weighted sum of positive semidefinite matrices must be positive semidefinite.

Now consider the (closed convex) dual cone:

$LaTeX: \begin{array}{rl}\mathcal{K}^* \!\!\!&=_{}\left\{_{}y~|~\langle z\,,\,y_{}\rangle\geq_{}0\,~\textrm{for\,all}~\,z\!\in_{_{}\!}\mathcal{K}_{}\right\}\subseteq_{}\reals^m\\ &=_{}\left\{_{}y~|~\langle z\,,\,y_{}\rangle\geq_{}0\,~\textrm{for\,all}~\,z_{\!}=_{\!}A\,\textrm{svec}X\,,~X\succeq0_{}\right\}\\ &=_{}\left\{_{}y~|~\langle A\,\textrm{svec}X\,,~y_{}\rangle\geq_{}0\,~\textrm{for\,all}~\,X\!\succeq_{_{}\!}0_{}\right\}\\ &=\left\{y~|~\langle\textrm{svec}X\,,\,A^{T\!}y\rangle\geq_{}0\;~\textrm{for\,all}~\,X\!\succeq_{\!}0\right\}\\ &=\left\{y~|~\textrm{svec}^{-1}(A^{T\!}y)\succeq_{}0\right\} \end{array}$

that follows from Fejer's dual generalized inequalities for the positive semidefinite cone:

$LaTeX: Y\succeq0~\Leftrightarrow~\langle Y\,,\,X\rangle\geq0\;~\textrm{for\,all}~\,X\succeq0$

This leads directly to an equally peculiar halfspace-description

$LaTeX: \mathcal{K}^*=\{y\!\in_{}\!\mathbb{R}^m~|\,\sum\limits_{j=1}^my_jA_j\succeq_{}0_{}\}$

The summation inequality with respect to the positive semidefinite cone is known as a linear matrix inequality.

LMI Geometry

Although matrix $LaTeX: \,A\,$ is finite-dimensional, $LaTeX: \mathcal{K}$ is generally not a polyhedral cone (unless $LaTeX: \,m\,$ equals 1 or 2) simply because $LaTeX: \,X\!\in\mathbb{S}_+^n\,$ .

Provided the $LaTeX: A_j$ matrices are linearly independent, then relative interior = interior

$LaTeX: \textrm{rel\,int}\mathcal{K}=\textrm{int}\mathcal{K}$

meaning, the cone interior is nonempty; implying, the dual cone is pointed (Dattorro, ch.2).

If matrix $LaTeX: \,A\,$ has no nullspace, on the other hand, then $LaTeX: \,A\,\textrm{svec}X\,$ is an isomorphism in $LaTeX: \,X\,$ between the positive semidefinite cone $LaTeX: \mathbb{S}_+^n$ and range $LaTeX: \,\mathcal{R}(A)\,$ of matrix $LaTeX: \,A$ .

In that case, convex cone $LaTeX: \,\mathcal{K}\,$ has relative interior

$LaTeX: \textrm{rel\,int}\mathcal{K}=\{A\,\textrm{svec}X~|~X\!\succ_{\!}0_{}\}$

and boundary

$LaTeX: \textrm{rel}\,\partial^{}\mathcal{K}=\{A\,\textrm{svec}X~|~X\!\succeq_{\!}0\,,~X\!\nsucc_{\!}0_{}\}$

When the $LaTeX: A_j$ matrices are linearly independent, function $LaTeX: \,g(y)_{\!}:=_{_{}\!}\sum y_jA_j\,$ on $LaTeX: \mathbb{R}^m$ is a linear bijection.

Inverse image of the positive semidefinite cone under $LaTeX: \,g(y)\,$ must therefore have dimension $LaTeX: _{}m$ .

In that circumstance, the dual cone interior is nonempty

$LaTeX: \textrm{int}\mathcal{K}^*=\{y\!\in_{}\!\mathbb{R}^m~|\,\sum\limits_{j=1}^my_jA_j\succ_{}0_{}\}$

having boundary

$LaTeX: \partial^{}\mathcal{K}^*=\{y\!\in_{}\!\mathbb{R}^m~|\,\sum\limits_{j=1}^my_jA_j\succeq_{}0\,,~\sum\limits_{j=1}^my_jA_j\nsucc_{}0_{}\}$

Applications

There are efficient numerical methods to determine whether an LMI is feasible (i.e., whether there exists a vector $LaTeX: y$ such that $LaTeX: LMI(y)\succeq0$ ), 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 is a minimization 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).

Retrieved from "http://www.convexoptimization.com/wikimization/index.php/Linear_matrix_inequality"

@@ Line 8: / Line 8: @@
 This linear matrix inequality specifies a convex constraint on ''y''.
-L8BXV0  <a href="http://nkoyrmvtnrvl.com/">nkoyrmvtnrvl</a>, [url=http://ltlocxpixvli.com/]ltlocxpixvli[/url], [link=http://teptabaxugtp.com/]teptabaxugtp[/link], http://hanuhwgvohbe.com/
+==  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: '''('''[http://meboo.convexoptimization.com/BOOK/convexgeometry.pdf Dattorro, Example 2.13.5.1.1]''')'''
+Consider a peculiar vertex-description for a closed convex cone defined over the positive semidefinite cone
+'''('''instead of the more common nonnegative orthant, <math>x\succeq0</math>''')''':
+for <math>X\!\in\mathbb{S}^n</math> given <math>\,A_j\!\in\mathbb{S}^n</math>, <math>\,j\!=\!1\ldots m</math>
+<math>\begin{array}{ll}\mathcal{K}
+\!\!&=\left\{\left[\begin{array}{c}\langle A_1\,,\,X^{}\rangle\\\vdots\\\langle A_m\;,\,X^{}\rangle\end{array}\right]|~X\!\succeq_{\!}0\right\}\subseteq_{}\reals^m\\\\
+&=\left\{\left[\begin{array}{c}\textrm{svec}(A_1)^T\\\vdots\\\textrm{svec}(A_m)^T\end{array}\right]\!\textrm{svec}X~|~X\!\succeq_{\!}0\right\}\\\\
+&:=\;\{A\,\textrm{svec}X~|~X\!\succeq_{\!}0_{}\}
+\end{array}</math>
+where
+*<math>A\!\in_{}\!\mathbb{R}^{m\times n(n+1)/2}</math>,
+*symmetric vectorization svec is a stacking of columns defined in '''('''[http://meboo.convexoptimization.com/BOOK/convexgeometry.pdf Dattorro, Ch.2.2.2.1]''')''',
+*<math>A_0=\mathbf{0}</math> is assumed without loss of generality.
+<math>\mathcal{K}</math> is a convex cone because
+<math>A\,\textrm{svec}{X_{{\rm p}_1}}_{\,},_{_{}}A\,\textrm{svec}{X_{{\rm p}_2}}\!\in\mathcal{K}~\Rightarrow~
+A(\zeta_{\,}\textrm{svec}{X_{{\rm p}_1\!}}+_{}\xi_{\,}\textrm{svec}{X_{{\rm p}_2}})\in_{}\mathcal{K}
+\textrm{~~for\,all~\,}\zeta_{\,},\xi\geq0</math>
+since a nonnegatively weighted sum of positive semidefinite matrices must be positive semidefinite.
+Now consider the (closed convex) dual cone:
+<math>\begin{array}{rl}\mathcal{K}^*
+\!\!\!&=_{}\left\{_{}y~|~\langle z\,,\,y_{}\rangle\geq_{}0\,~\textrm{for\,all}~\,z\!\in_{_{}\!}\mathcal{K}_{}\right\}\subseteq_{}\reals^m\\
+&=_{}\left\{_{}y~|~\langle z\,,\,y_{}\rangle\geq_{}0\,~\textrm{for\,all}~\,z_{\!}=_{\!}A\,\textrm{svec}X\,,~X\succeq0_{}\right\}\\
+&=_{}\left\{_{}y~|~\langle A\,\textrm{svec}X\,,~y_{}\rangle\geq_{}0\,~\textrm{for\,all}~\,X\!\succeq_{_{}\!}0_{}\right\}\\
+&=\left\{y~|~\langle\textrm{svec}X\,,\,A^{T\!}y\rangle\geq_{}0\;~\textrm{for\,all}~\,X\!\succeq_{\!}0\right\}\\
+&=\left\{y~|~\textrm{svec}^{-1}(A^{T\!}y)\succeq_{}0\right\}
+\end{array}</math>
+that follows from Fejer's dual generalized inequalities for the positive semidefinite cone:
+* <math>Y\succeq0~\Leftrightarrow~\langle Y\,,\,X\rangle\geq0\;~\textrm{for\,all}~\,X\succeq0</math>
+This leads directly to an equally peculiar halfspace-description
+<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
+is known as a ''linear matrix inequality''.
 == LMI Geometry ==

Linear matrix inequality

From Wikimization

Revision as of 14:35, 5 December 2008

Contents

Convexity of the LMI constraint

LMI Geometry

Applications

External links

Views

Personal tools

Navigation

Search

Toolbox