# Linear matrix inequality

### From Wikimization

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\\\vdots\\\langle A_m\;,\,X^{}\rangle\end{array}\right]|~X\!\succeq_{\!}0\right\}\subseteq_{}\ | + | \!\!&=\left\{\left[\begin{array}{c}\langle A_1\,,\,X^{}\rangle\\\vdots\\\langle A_m\;,\,X^{}\rangle\end{array}\right]|~X\!\succeq_{\!}0\right\}\subseteq_{}\mathbb{R}^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\}\\\\ | &=\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_{}\} | &:=\;\{A\,\textrm{svec}X~|~X\!\succeq_{\!}0_{}\} | ||

Line 39: | Line 39: | ||

<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\,\textrm{svec}X\,,~X\succeq0_{}\right\}\\ | &=_{}\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 A\,\textrm{svec}X\,,~y_{}\rangle\geq_{}0\,~\textrm{for\,all}~\,X\!\succeq_{_{}\!}0_{}\right\}\\ | ||

Line 74: | Line 74: | ||

That is sufficient for [[Convex cones|convex cone]] <math>\,\mathcal{K}\,</math> to be closed, and necessary to have relative boundary | 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\,\textrm{svec}X~|~X\!\succeq_{\!}0\,,~X\!\ | + | <math>\textrm{rel}\,\partial^{}\mathcal{K}=\{A\,\textrm{svec}X~|~X\!\succeq_{\!}0\,,~X\!\not\succ_{\!}0_{}\}.</math> |

<br> | <br> | ||

Line 86: | Line 86: | ||

and relative boundary | 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\ | + | <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\succ_{}0_{}\}.</math> |

When this dimension is <math>\,m\,</math>, the dual cone interior is nonempty | When this dimension is <math>\,m\,</math>, the dual cone interior is nonempty |

## Revision as of 13:42, 19 November 2011

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