# Linear matrix inequality

(Difference between revisions)
 Revision as of 03:51, 9 November 2007 (edit) (→Convexity of the LMI constraint)← Previous diff Revision as of 01:40, 24 October 2008 (edit) (undo)Next diff → Line 66: Line 66: $\textrm{rel\,int}\mathcal{K}=\textrm{int}\mathcal{K}$ $\textrm{rel\,int}\mathcal{K}=\textrm{int}\mathcal{K}$ - meaning, the cone interior is nonempty; implying, the dual cone is pointed (Dattorro, ch.2). + meaning, the cone interior is nonempty; implying, the dual cone is pointed ([http://meboo.convexoptimization.com/BOOK/convexgeometry.pdf Dattorro, ch.2]). If matrix $\,A\,$ has no nullspace, on the other hand, then If matrix $\,A\,$ has no nullspace, on the other hand, then

## Revision as of 01:40, 24 October 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.

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