Linear Matrix Inequalities
DefinitionPositive Semi-Definite MatricesRecall from here that a symmetric matrix is positive semi-definite (PSD) if and only if every one of its eigenvalues is non-negative. We use the notation to mean that is PSD. An alternative condition for to be PSD is that the associated quadratic form is non-negative: The set of PSD matrices is convex, since the conditions above represent (an infinite number of) ordinary linear inequalities on the elements of the matrix . Examples:
Standard formA linear matrix inequality is a constraint of the form where the matrices are symmetric.
The matrices are referred to as the coefficient matrices. Sometimes, these matrices are not explicitly defined. That is, if is an affine map that takes its values in the set of symmetric matrices of order , then is an LMI. An alternate form for LMIs is as the intersection of the positive semi-definite cone with an affine set: where is affine. The form we have seen before, and the above one, are equivalent, in the sense that we can always transform one into the other (at the expense possibly of adding new variables and constraints). LMIs and Convex SetsLet us denote by the set of points that satisfy the above LMI. The set is convex. Indeed, we have if and only if Since with , , we obtain that the condition on : can be represented as an intersection of (an infinite number of) half-space conditions.
Multiple LMIsWe can combine multiple LMIs into one. Consider two affine maps from to a space of symmetric matrices of order , , . Then the two LMIs are equivalent to one LMI, involving a larger matrix of size : This corresponds to intersecting the two LMI sets. Special CasesLMIs include as special cases the following. Ordinary affine inequalitiesConsider single affine inequality in : where , . (The above set describes a half-space.) The above is a trivial special case of LMI, where the coefficient matrices are scalar: , , . Using the result above on multiple LMIs, we obtain that the set of ordinary affine inequalities can be cast as a single LMI , where Second-order cone inequalitiesSecond-order cone (SOC) inequalities can be represented as LMIs. To see this, let us start with the ‘‘basic’’ SOC , with and . The SOC can be represented as Indeed, we check that for every , , we have if and only if . More generally, a second-order cone inequality of the form with , , , , can be written as the LMI The proof relies on the Schur complement lemma. |