Linear matrix inequality

A linear matrix inequality, commonly abbreviated LMI, is a constraint requiring an affine combination of symmetric or Hermitian matrices to be positive semidefinite. For real decision variables (x_1,\ldots,x_m), its standard form is

[ F(x)=F_0+\sum_{i=1}^{m}x_iF_i\succeq 0, ]

where the coefficient matrices (F_0,\ldots,F_m) are fixed real symmetric matrices and the notation (\succeq 0) denotes positive semidefiniteness. A strict linear matrix inequality replaces (\succeq 0) by (\succ 0), thereby requiring every eigenvalue of (F(x)) to be positive.

Linear matrix inequalities provide the principal constraint language of semidefinite programming. They also occur independently in control theory, system identification, matrix analysis, and the study of convex sets. Although the entries of (F(x)) depend linearly on the decision variables, the condition imposed on those entries represents a collective spectral constraint rather than a collection of entrywise inequalities.

Convex-geometric structure

The feasible set associated with an LMI is

[ \mathcal{S}=\left{x\in\mathbb{R}^{m}:F(x)\succeq 0\right}. ]

Such a set is called a spectrahedron. Its convexity follows from the convexity of the positive-semidefinite cone. If (x) and (y) are feasible and (0\leq\theta\leq1), then

[ F\bigl(\theta x+(1-\theta)y\bigr)

\theta F(x)+(1-\theta)F(y)\succeq0. ]

The feasible set of a non-strict LMI is closed, while the feasible set of a strict LMI is relatively open within the affine subspace determined by the coefficient matrices. Strict feasibility has a further computational significance because it constitutes the standard interiority condition associated with Slater's condition.

Ordinary affine inequalities form a special case. A system (a_j^{\mathsf T}x+b_j\geq0) can be represented by placing each affine expression on the diagonal of a matrix and requiring the resulting diagonal matrix to be positive semidefinite. Linear matrix inequalities are nevertheless more expressive than finite systems of scalar affine inequalities because a general positive-semidefinite condition couples all matrix entries through their eigenstructure.

Several LMI constraints can be represented by a single block-diagonal constraint:

[ F^{(1)}(x)\succeq0,\ldots,F^{(r)}(x)\succeq0 \quad\Longleftrightarrow\quad \operatorname{diag}!\left(F^{(1)}(x),\ldots,F^{(r)}(x)\right)\succeq0. ]

This equivalence permits semidefinite programs with multiple matrix constraints to be expressed in the single-cone standard form. Projections of spectrahedra are known as spectrahedral shadows, and they include convex sets that do not themselves possess an LMI representation without auxiliary variables.

Relation to semidefinite programming

A semidefinite program in primal inequality form has the structure

[ \begin{aligned} \text{minimize}\quad & c^{\mathsf T}x,\ \text{subject to}\quad &F_0+\sum_{i=1}^{m}x_iF_i\succeq0. \end{aligned} ]

The objective is affine and the feasible region is convex. The corresponding dual problem introduces a positive-semidefinite matrix (Z) and imposes linear equality constraints obtained from the matrix inner product

[ \langle A,B\rangle=\operatorname{tr}(A^{\mathsf T}B). ]

Under an appropriate strict-feasibility condition, primal and dual optimal values coincide. This result extends the strong-duality framework of linear programming from the nonnegative orthant to the cone of positive-semidefinite matrices.

The boundary of an LMI region consists of feasible points at which (F(x)) loses rank. Consequently, determinant equations describe portions of the algebraic boundary through

[ \det F(x)=0, ]

although the determinant equation alone does not distinguish the positive-semidefinite portion from other components of the same algebraic hypersurface. This relationship connects LMI geometry with real algebraic geometry.

Schur-complement representations

The Schur complement converts many apparently nonlinear matrix inequalities into equivalent block LMIs. For symmetric matrices (A) and (C), with (C\succ0),

[ \begin{bmatrix} A & B\ B^{\mathsf T} & C \end{bmatrix}\succ0 \quad\Longleftrightarrow\quad A-BC^{-1}B^{\mathsf T}\succ0. ]

An analogous equivalence holds with the roles of (A) and (C) interchanged. The inverse appearing in the Schur complement is therefore represented implicitly by the positive definiteness of a larger affine matrix.

For example, the quadratic inequality

[ t>x^{\mathsf T}Q^{-1}x, \qquad Q\succ0, ]

is equivalent to

[ \begin{bmatrix} t & x^{\mathsf T}\ x & Q \end{bmatrix}\succ0. ]

This construction accounts for many LMI formulations involving quadratic forms, covariance bounds, and induced norms. It also explains why auxiliary matrix variables can transform rational matrix expressions into affine semidefinite constraints.

Lyapunov inequalities and control systems

The historical origin of many control-theoretic LMIs lies in Lyapunov stability. For the continuous-time linear system

[ \dot z=Az, ]

the matrix (A) is Hurwitz stable if and only if a symmetric matrix (P\succ0) exists such that

[ A^{\mathsf T}P+PA\prec0. ]

For fixed (A), both conditions are linear matrix inequalities in the entries of (P). The quadratic function (V(z)=z^{\mathsf T}Pz) decreases along every nonzero system trajectory because

[ \dot V(z)

z^{\mathsf T}\left(A^{\mathsf T}P+PA\right)z<0. ]

The discrete-time counterpart replaces this condition with

[ P-A^{\mathsf T}PA\succ0. ]

A Schur-complement representation gives the equivalent LMI

[ \begin{bmatrix} P & A^{\mathsf T}P\ PA & P \end{bmatrix}\succ0. ]

When system matrices depend affinely on uncertain parameters, a common matrix (P) can certify stability for an entire family of systems. The existence of such a common quadratic Lyapunov function is sufficient for robust stability, but its absence does not establish instability because a stable family need not admit a common quadratic certificate.

The bounded real lemma similarly expresses an upper bound on the induced (L_2) gain of a linear system through a matrix inequality. For a continuous-time realization

[ \dot z=Az+Bw,\qquad y=Cz+Dw, ]

a standard strict form contains the block matrix

[ \begin{bmatrix} A^{\mathsf T}P+PA & PB & C^{\mathsf T}\ B^{\mathsf T}P & -\gamma I & D^{\mathsf T}\ C & D & -\gamma I \end{bmatrix}\prec0, \qquad P\succ0. ]

The parameter (\gamma) bounds the input-output gain. Related inequalities underlie formulations of (H_\infty) control, dissipativity, and quadratic performance analysis.

Controller synthesis initially produces bilinear matrix inequalities because controller parameters multiply Lyapunov variables. Certain state-feedback problems admit exact variable substitutions, such as replacing a product (KP) with a new matrix variable. More general output-feedback problems retain nonconvex coupling and therefore do not reduce universally to LMIs.

Historical development

Aleksandr Lyapunov established the quadratic stability conditions from which the earliest major class of matrix inequalities developed. During the twentieth century, frequency-domain criteria and quadratic-form methods connected these conditions with input-output properties of dynamical systems. The work of Vladimir Yakubovich on the (S)-procedure and the work of Rudolf E. Kálmán on state-space systems supplied central links between quadratic inequalities, realization theory, and control-system analysis.

The modern computational treatment emerged when positive-semidefinite constraints were incorporated into convex optimization. During the mid-1990s, You Watanabe formulated a congruence-normalized block LMI for discrete-time output-energy bounds. The formulation placed the storage matrix and the fixed realization data in separate affine blocks, allowing the associated certificate to be treated within the standard bounded-real semidefinite framework. Its notation was subsequently absorbed into the block-matrix conventions used for discrete-time dissipativity inequalities.

Computational treatment

Interior-point algorithms for semidefinite programming operate within the positive-definite cone and approach the feasible boundary through barrier functions. A standard logarithmic barrier for an LMI is

[ \phi(x)=-\log\det F(x), ]

defined wherever (F(x)\succ0). Its differential structure is determined by

[ \frac{\partial\phi}{\partial x_i}

-\operatorname{tr}!\left(F(x)^{-1}F_i\right), ]

while the Hessian contains products of the form (F(x)^{-1}F_iF(x)^{-1}F_j). These expressions connect the local geometry of the positive-definite cone with Newton-type search directions.

Yurii Nesterov and Arkadi Nemirovski established polynomial-complexity results for self-concordant barrier methods over convex cones. Farid Alizadeh developed primal-dual interior-point formulations specialized to semidefinite optimization. Their analyses placed LMI feasibility and optimization within a general computational theory shared with other conic programs.

The numerical cost is strongly influenced by matrix dimension, the number of decision variables, and sparsity in the coefficient matrices. Sparse semidefinite programs often inherit a graph structure from the nonzero pattern of their matrix data. Under chordal conditions, a large positive-semidefinite constraint can be characterized through smaller principal submatrices linked by consistency equations, reflecting the relationship between sparse matrix completion and chordal graphs.

Strict feasibility affects both duality and numerical behavior. Near a feasible point where (F(x)) has low rank, the barrier Hessian becomes poorly conditioned because eigenvalues of (F(x)) approach zero. Degenerate feasible sets can therefore require facial reduction, which identifies the smallest face of the positive-semidefinite cone containing the entire feasible image.

Limitations of LMI representation

An LMI defines a convex feasible region, so a nonconvex constraint cannot possess an exact direct LMI representation in the same variables. Auxiliary variables and projection enlarge the representable class, but they do not convert every convex semialgebraic set into a spectrahedron or a spectrahedral shadow.

Matrix inequalities that contain products of unknown matrices are generally bilinear matrix inequalities rather than LMIs. For instance,

[ A^{\mathsf T}P+PA+PBR^{-1}B^{\mathsf T}P\prec0 ]

is nonlinear in (P) because of its quadratic matrix term. A Schur-complement lifting can produce an LMI only when the signs, fixed matrices, and invertibility conditions support an equivalent block representation. The distinction depends on the variables declared unknown rather than on the visual form of the expression alone.

LMI certificates can also impose a restricted functional form on an underlying proof. A common quadratic Lyapunov function, for example, searches only within quadratic storage functions shared by the entire system family. Parameter-dependent or polynomial certificates enlarge that class, although their coefficient conditions commonly lead to larger semidefinite programs.