What an LMI is, why control engineers fell in love with them, and the machinery — semidefinite programming — that solves them. Written for an engineer who is comfortable with linear algebra and wants the mechanism, not just recipes.
Here is the single most basic question in control theory. You have a linear dynamical system
where \(x\) is the state vector and \(\dot{x}\) its time derivative. Does \(x(t)\to 0\) as \(t\to\infty\), no matter where it starts? You could answer this by computing eigenvalues of \(A\): the system is stable exactly when every eigenvalue has negative real part. Fine — for analysis.
But engineers mostly face the design question: choose a feedback gain \(K\) so that \(\dot{x} = (A+BK)x\) is stable, and some energy cost is small, and the closed loop tolerates model uncertainty, and actuator effort stays bounded. Eigenvalues stop being a usable design handle: you cannot write "all eigenvalues of \(A+BK\) in the left half-plane" as a condition you can optimize over \(K\). It is a horribly nonconvex constraint.
In 1890 Lyapunov gave a different characterization of stability — through an "energy-like" function — and in the 1990s the control community realized that Lyapunov's condition, and dozens of conditions like it (performance, robustness, filtering), can be massaged into one canonical shape:
a symmetric matrix that depends affinely on decision variables \(x_1,\dots,x_m\), required to be positive semidefinite. This is a linear matrix inequality (LMI).
Why is this shape so valuable? Because its feasible set is convex, and convex problems admit algorithms with proofs: polynomial time, no local minima, a definite yes/no answer. The 1994 book of Boyd, El Ghaoui, Feron and Balakrishnan showed that an enormous slice of control design reduces to LMIs, and interior-point solvers arriving at the same moment made them computable. This artifact explains every piece of that sentence.
Everything rests on one generalization: what does it mean for a matrix to be positive? Scalars are easy: \(a > 0\). A matrix has no total order, but a symmetric matrix \(P = P^\top \in \mathbb{R}^{n\times n}\) has the next best thing — a sign test that works in every direction at once.
A symmetric matrix \(P\) is positive definite, written \(P \succ 0\), if
It is positive semidefinite, \(P \succeq 0\), if "\(>\)" is replaced by "\(\ge\)". The scalar quantity \(x^\top P x\) is called the quadratic form of \(P\).
Why this definition? Think of \(V(x) = x^\top P x\) as an energy function: a scalar that assigns a "height" to every state. Requiring \(P \succ 0\) says the energy is positive everywhere except at the origin — a bowl with its bottom exactly at \(x=0\). That is precisely the raw material for Lyapunov's argument in Section 5.
Symmetric matrices have a complete set of real eigenvalues \(\lambda_1,\dots,\lambda_n\) with orthonormal eigenvectors \(v_1,\dots,v_n\), and \(P = \sum_i \lambda_i v_i v_i^\top\). Decompose any vector as \(x = \sum_i c_i v_i\); then
a weighted sum of squares. This is positive for all \(x\neq 0\) exactly when every weight is positive:
So "positive definite matrix" = "all eigenvalues positive." The quadratic form also has a beautiful geometry: the level set \(\{x : x^\top P x = 1\}\) is an ellipsoid whose axes point along the eigenvectors, with semi-axis lengths \(1/\sqrt{\lambda_i}\). Small eigenvalue → long axis → the bowl is shallow in that direction.
Concrete numbers. Take \(P = \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}\). Its eigenvalues solve \((2-\lambda)^2 - 1 = 0\), giving \(\lambda_1 = 3\), \(\lambda_2 = 1\), with eigenvectors \(v_1 = (1,1)/\sqrt{2}\), \(v_2 = (1,-1)/\sqrt{2}\). Both eigenvalues are positive, so \(P \succ 0\): indeed \(x^\top P x = 2x_1^2 + 2x_1 x_2 + 2x_2^2 = x_1^2 + x_2^2 + (x_1+x_2)^2 > 0\). Change the \(1\)'s to \(3\)'s and the eigenvalues become \(5\) and \(-1\): indefinite — the "bowl" is a saddle.
One caution: positive entries are neither necessary nor sufficient — the matrix above with \(3\)'s has all entries positive yet is indefinite. Definiteness is a property of the eigenvalues, i.e. of the geometry, not the entries.
Positivity of scalars has geometry: the nonnegative numbers form a ray \([0,\infty)\), and rays are convex cones — closed under positive scaling and addition. Positive semidefinite matrices have exactly the same geometry, one dimension of abstraction up.
The set of all symmetric PSD \(n\times n\) matrices, called the PSD cone \(\mathcal{S}_+^n\), is a convex cone in the vector space of symmetric matrices:
Both steps use nothing but linearity of the quadratic form. That is the whole proof, and it is why the notation \(P \succeq Q\) (meaning \(P - Q \succeq 0\)) deserves the inequality-looking symbol: \(\succeq\) is a partial order with a convex "nonnegative orthant," exactly like \(\ge\) on \(\mathbb{R}\).
What does this cone look like? For \(2\times2\) symmetric matrices we can draw it. Parametrize \(M = \begin{bmatrix} a & b \\ b & c \end{bmatrix}\) by the point \((a,b,c)\in\mathbb{R}^3\). The eigenvalues are nonnegative iff their sum and product are: \(a + c \ge 0\) and \(ac - b^2 \ge 0\), which (given \(ac \ge b^2 \ge 0\)) collapses to
The boundary \(b^2 = ac\) is a cone you may recognize: with \(a+c\) as "height" and \(b,\, a-c\) as cross-sectional coordinates, \(b^2 = ac\) becomes \(b^2 + \tfrac14(a-c)^2 = \tfrac14(a+c)^2\) — a circular ice-cream cone. The PSD cone is literally a round cone (up to a linear change of coordinates), and the boundary consists of the rank-one matrices (one eigenvalue exactly \(0\)): the "just barely semidefinite" ones.
An LMI in the variable \(x\in\mathbb{R}^m\) is a constraint
where \(F_0, F_1, \dots, F_m\) are given symmetric \(n\times n\) matrices. Strict versions use \(\succ 0\). Read it as: "move around in matrix space along the affine directions \(F_1,\dots,F_m\), starting from \(F_0\); stay inside the PSD cone."
Two features deserve slow reading:
The map \(x \mapsto F(x)\) is affine, and the PSD cone is convex. The preimage of a convex set under an affine map is convex: if \(F(x)\succeq 0\) and \(F(y)\succeq 0\), then for \(\theta\in[0,1]\),
where the equality is affinity and the inequality is convexity of the cone (Section 3). Geometrically: the feasible set is the intersection of an affine subspace with the PSD cone, pulled back to \(x\)-space. Such sets are called spectrahedra — curved, always-convex generalizations of polyhedra.
A baby example. One scalar variable, \(2\times2\) matrices:
By Section 3's test (\(a\ge0,\ ac\ge b^2\)) this holds iff \(x^2 \le 1\), i.e. \(x\in[-1,1]\): an interval. Convex, as promised — but note the boundary is where an eigenvalue vanishes, not where an entry does.
Two more structural facts you get for free:
Back to the opening question: is \(\dot{x} = Ax\) stable? Lyapunov's theorem says the origin is asymptotically stable if and only if there exists a symmetric \(P \succ 0\) with
Why does this condition work? Use \(V(x) = x^\top P x\) as an energy function and differentiate along trajectories (chain rule, then substitute \(\dot x = Ax\)):
If \(A^\top P + PA \prec 0\), then \(\dot V < 0\) whenever \(x\neq 0\): energy strictly drains along every trajectory, and since \(V \ge 0\) is a bowl bottomed at the origin (Section 2), the state must slide to \(x=0\). No eigenvalues of \(A\) were computed — the condition is a certificate: exhibit one \(P\) and stability is proved.
Take \(A = \begin{bmatrix} -1 & 2 \\ 0 & -3 \end{bmatrix}\) and parametrize the unknown as \(P = \begin{bmatrix} p & q \\ q & r \end{bmatrix}\), three scalar decision variables. Multiplying out,
Every entry is affine in \((p,q,r)\) — that is the point. The strict-LMI feasibility problem is:
where the second matrix is \(-\!(A^\top P + PA)\), flipped so both constraints read \(\succ 0\). Try the simplest candidate, \(P = I\) (i.e. \(p=r=1,\ q=0\)): then \(A^\top + A = \begin{bmatrix} -2 & 2 \\ 2 & -6 \end{bmatrix}\), with eigenvalues \(-4 \pm 2\sqrt{2} \approx \{-1.17,\, -6.83\}\) — both negative. Certificate found: the system is stable, proved by exhibiting \(P=I\). If \(P=I\) had failed, the LMI machinery would have searched the whole convex set of candidates instead of one guess.
Real design problems rarely arrive already affine. The Schur complement is the single most-used device for converting quadratic matrix inequalities into LMIs. It rests on one idea: completing the square, in blocks.
Partition a symmetric matrix and its argument conformably:
and expand the quadratic form: \(x^\top A x + 2\,x^\top B y + y^\top C y\). For fixed \(x\), minimize over \(y\): since \(C\succ0\) the form is strictly convex in \(y\), and setting the gradient \(2B^\top x + 2Cy = 0\) to zero gives the minimizer \(y^\star = -C^{-1}B^\top x\). Substituting back (the cross terms collapse because \(B^\top x = -Cy^\star\)):
Now \(M \succ 0\) means the form is positive for all \((x,y)\neq0\). Since \(y\) is free, the form is positive everywhere iff its minimum over \(y\) is positive for all \(x\neq0\) — which is exactly the condition \(A - BC^{-1}B^\top \succ 0\). Hence:
The matrix \(A - BC^{-1}B^\top\) is the Schur complement of \(C\). (The same statement holds with \(\succeq\).) Geometrically it is the matrix version of the scalar test \(c > 0,\ a > b^2/c\) — the very test from Section 3.
Suppose a design condition gives you (such inequalities appear in quadratic optimal control and \(H_\infty\) design):
The term \(PBB^\top P\) is quadratic in \(P\) — not an LMI as written. But watch the Schur complement run in reverse. With the identifications "\(A\)" \(\leftrightarrow A^\top P + PA + Q\), "\(B\)" \(\leftrightarrow PB\), and a "\(C\)" block of \(-I\) under the negative-definite sign convention:
(Taking the Schur complement of the \(-I\) block, \(A^\top P + PA + Q - (PB)(-I)^{-1}(B^\top P) = A^\top P + PA + Q + PBB^\top P\), returns exactly the original inequality.) Every entry of this block matrix is affine in \(P\) — an LMI! The nonlinearity was not eliminated; it was lifted into a higher-dimensional matrix where it appears linearly. This is the paradigmatic LMI maneuver: when stuck with a product of variables, build a block matrix whose Schur complement is that product.
If \(M \prec 0\) and \(W\) is any invertible matrix, then \(W^\top M W \prec 0\): substituting \(y = Wx\) gives \(x^\top W^\top M W x = y^\top M y < 0\) for all \(y \neq 0\), since \(W\) invertible means \(y\) ranges over all nonzero vectors. Multiplying an inequality on both sides by \(W^\top\) and \(W\) (a congruence transformation) preserves definiteness while changing what the entries look like. This is the legal way to "multiply both sides" of a matrix inequality — one-sided multiplication by a non-symmetric matrix would break the symmetry that \(\succeq\) requires.
The flagship example. Design a state feedback \(u = Kx\) so that \(\dot x = (A + BK)x\) is stable. Lyapunov on the closed loop:
As an inequality in the unknowns \((P, K)\) this is bilinear: it contains the product \(PBK\). Not an LMI — yet. Apply congruence with \(W = P^{-1}\), and write \(Q = P^{-1}\) (note \(Q \succ 0 \iff P \succ 0\)):
Now the substitution: define the new variable \(Y = KQ\). Since \(Q \succ 0\) is invertible, \(K \mapsto Y\) is a bijection — any pair \((Q,Y)\) recovers a gain via \(K = YQ^{-1}\). The condition becomes
an LMI in \((Q, Y)\) — purely affine. Solve it, then set \(K = YQ^{-1}\). The recipe was: congruence to bring the product into a renameable form, then rename the product.
An LMI feasibility problem generalizes naturally to optimization: minimize a linear objective over an LMI constraint. This is a semidefinite program (SDP):
LP is the special case where all \(F_i\) are diagonal — a diagonal matrix is PSD iff its diagonal entries are nonnegative, so LMIs strictly contain linear programs. The feasible set is the spectrahedron of Figure 3, and we optimize a linear function over it.
The workhorse algorithms (Nesterov–Nemirovskii, early 1990s — the same era as the LMI control revolution, and not a coincidence) handle the constraint \(F(x) \succeq 0\) with a logarithmic barrier. Replace
Why \(-\log\det\)? On the strict interior \(F(x)\succ0\) all eigenvalues are positive and \(\det F(x) = \prod_i \lambda_i > 0\). Approach the boundary and some eigenvalue \(\lambda_i \to 0^+\), so \(-\log\det F(x) = -\sum_i \log\lambda_i \to +\infty\): the barrier is an infinitely steep smooth wall exactly at the cone boundary. It is also convex in \(x\) (a nontrivial, beautiful theorem: \(X \mapsto -\log\det X\) is convex on the PSD cone), so each barrier subproblem is an unconstrained convex minimization, solvable by Newton's method with quadratic convergence. Increase \(t\), trace the "central path" with Newton steps, and you converge to the optimum.
Consequences that made the 1990s control community take notice:
In practice you never write \(F_0 + \sum x_i F_i\) by hand. Modeling layers — YALMIP or CVX (MATLAB), cvxpy (Python), JuMP (Julia) — let you type \(A^\top P + PA \preceq -I\) almost verbatim and compile it to canonical SDP form; solvers such as MOSEK, SDPT3, SeDuMi, or SCS do the interior-point (or first-order) work.
Conceptually and historically, LMIs connect several worlds:
Honest limitations, so the picture stays balanced: LMI conditions derived from a single quadratic Lyapunov function can be conservative for uncertain or nonlinear systems (the certificate is sufficient, not always necessary); problem sizes grow quickly since an \(n\times n\) symmetric matrix carries \(O(n^2)\) scalars; and strict LMIs in practice mean "feasible with a small margin," because solvers live on closures. The frontier — sum-of-squares programming, moment relaxations — is largely about managing that conservatism with bigger, structured LMIs.
Drag the sliders to choose \(M = \begin{bmatrix} a & b \\ b & c \end{bmatrix}\). The plot shows the level set \(\{x : x^\top M x = 1\}\) (Figure 1, live): an ellipse exactly when \(M \succ 0\), degenerating as an eigenvalue crosses zero. Watch the eigenvalues, and notice the boundary \(\det M = 0\) is where the ellipse's long axis blows up to infinity — the matrix becomes merely semidefinite, then indefinite.
Dashed circle: the unit ball, for scale. Colored curve: \(x^\top M x = 1\), drawn with semi-axes \(1/\sqrt{\lambda_i}\) along the eigenvectors (clipped when an axis would be enormous). Red dashed lines appear when \(M\) leaves the PSD cone: they are the asymptote directions of the hyperbola the level set becomes.