Linear matrix inequality

From Wikimization

Jump to: navigation, search

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

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

where

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

This linear matrix inequality specifies a convex constraint on y.

Contents

[edit] Convexity of the LMI constraint

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, x\succeq0):

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

\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

  • 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),
  • A_0=\mathbf{0} is assumed without loss of generality.

\mathcal{K} is a convex cone because

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:

\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:

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

This leads directly to an equally peculiar halfspace-description

\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.

[edit] LMI Geometry

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

Provided the Aj matrices are linearly independent, then relative interior = interior

\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 \,A\, has no nullspace, on the other hand, then \,A\,\textrm{svec}X\, is an isomorphism in \,X\, between the positive semidefinite cone \mathbb{S}_+^n and range \,\mathcal{R}(A)\, of matrix \,A.

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

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

and boundary

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


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

Inverse image of the positive semidefinite cone under \,g(y)\, must therefore have dimension m.

In that circumstance, the dual cone interior is nonempty

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

having boundary

\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_{}\}

[edit] Applications

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

[edit] External links

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