2. Math Toolkit I: Duality, LMIs & the S-Procedure

Try these before opening the answer. The review links lead to earlier material.

1. What is the derivative of $(x-2)^2$? Review gradients.
2. For $P=\operatorname{diag}(2,3)$, what is $x^\top Px$ at $x=(1,-1)^\top$? Review quadratic forms.
3. Does $x=0$ satisfy the constraint $x-1\le0$ strictly? Review feasibility.

(i) Concavity. For fixed $x$ the map $(\lambda,\nu)\mapsto L(x,\lambda,\nu)$ is affine (it is $f_0(x)$ plus a linear function of $(\lambda,\nu)$). Take $\theta\in[0,1]$ and two multiplier pairs $\mu=(\lambda,\nu)$, $\mu'=(\lambda',\nu')$. Then

because the infimum of a sum is at least the sum of the infima (each term is bounded below by its own infimum). A pointwise infimum of affine functions is concave; no property of $f_i$ was used.

(ii) Weak duality. Let $\tilde x$ be primal feasible. Since $\lambda_i\ge0$ and $f_i(\tilde x)\le0$ we have $\sum_i\lambda_if_i(\tilde x)\le0$, and $h_j(\tilde x)=0$ kills the equality terms, so $L(\tilde x,\lambda,\nu)\le f_0(\tilde x)$. Therefore

Taking the infimum over feasible $\tilde x$ gives $g(\lambda,\nu)\le p^\star$; maximising over $\lambda\ge0,\nu$ gives $d^\star\le p^\star$. The only place the sign $\lambda\ge0$ enters is the step $\lambda_if_i(\tilde x)\le0$, which is why dual variables of inequalities live on the nonnegative orthant while those of equalities are free. $\blacksquare$

Drop the equality constraints for readability and define the perturbation function $p^\star(u)=\inf\{f_0(x):f_i(x)\le u_i,\ i=1..m\}$, so $p^\star(0)=p^\star$. It is nonincreasing in $u$ (looser constraints, smaller minimum). The dual function is a Legendre-type transform (see Primer B) of it:

Proof. ($\ge$) For any $x\in\mathcal D$ put $u=f(x)$; then $x$ is feasible for the $u$-perturbed problem, so $f_0(x)\ge p^\star(f(x))$ and $L(x,\lambda)\ge p^\star(u)+\lambda^{\top}u\ge\inf_u[\cdot]$. Take the infimum over $x$. ($\le$) Fix $u$ and any $x$ with $f(x)\le u$; because $\lambda\ge0$, $L(x,\lambda)\le f_0(x)+\lambda^{\top}u$; take the infimum over such $x$ to get $g(\lambda)\le p^\star(u)+\lambda^{\top}u$, then over $u$. $\blacksquare$

So $g(\lambda)$ is the largest intercept $c$ such that the affine function $u\mapsto c-\lambda^{\top}u$ lies below the graph of $p^\star$ everywhere; $d^\star$ is the best such intercept over all slopes $-\lambda\le0$. Because $p^\star$ is nonincreasing (and the primal is feasible), affine minorants with other slopes add nothing, so $d^\star$ is the value at $u=0$ of the closed convex envelope of $p^\star$, the supremum of all its affine minorants. Zero duality gap means the graph of $p^\star$ meets this envelope at $u=0$. A finite optimal multiplier is a further requirement: given zero gap, it exists iff a non-vertical supporting line touches the graph at $u=0$; its slope is then $-\lambda^\star$, which gives the sensitivity interpretation $\lambda^\star_i=-\partial p^\star(0)/\partial u_i$ when $p^\star$ is differentiable. The two can come apart: for $\min x$ s.t. $x^2\le0$ we have $p^\star(u)=-\sqrt u$ for $u\ge0$ and $p^\star=d^\star=0$, but $g(\lambda)=-1/(4\lambda)$ only tends to $0$ as $\lambda\to\infty$, because the tangent at $u=0$ is vertical (exactly what Slater's condition rules out). For a non-convex primal the graph can have a dent at $u=0$; the envelope then passes strictly below and the gap $p^\star-d^\star$ is the depth of the dent. A finite dual optimum can still exist there, but its line supports the envelope at $(0,d^\star)$, below the graph, which is why the touching-line test above presumes zero gap: for $\min x$ over $x\in\{-1,1\}$ s.t. $-x\le0$ we have $p^\star=1$ and $g(\lambda)=-|1-\lambda|$, so $d^\star=0$ is attained at $\lambda^\star=1$ despite a gap of $1$. Dual ascent maximises $g$, which only sees the envelope, so it targets the multiplier of the convexified problem (and converges to it under the step-size conditions above, when it exists); but the primal minimisers $x(\lambda_k)$ need not converge and can oscillate between minimisers on either side of the dent (for one constraint, typically the two points whose mixture the envelope represents), none of which is both feasible and optimal. This "primal recovery" failure motivates the state-augmentation construction discussed in Module 8.

The $x^2\le0$ example in detail. For $\lambda\gt0$ complete the square: $x+\lambda x^2=\lambda\big(x+\tfrac{1}{2\lambda}\big)^2-\tfrac{1}{4\lambda}$, so $g(\lambda)=-1/(4\lambda)$; at $\lambda=0$, $g(0)=\inf_x x=-\infty$. The feasible set is $\{0\}$, so $p^\star=0=\sup_{\lambda\ge0}g(\lambda)=d^\star$, but no finite $\lambda$ attains the supremum.

The one non-convex problem that matters most here has no dent: Paternain et al., NeurIPS 2019 prove that a CMDP with bounded rewards and a Slater point has zero duality gap, because its perturbation function $P(\xi)=\max_\pi V_0(\pi)$ s.t. $V_i(\pi)\ge c_i+\xi_i$ is concave: the set of occupancy measures is convex (see Primer E), so any two feasible policies can be mixed at the level of occupancy measures, and the value is linear in the occupancy measure. Fenchel–Moreau then gives $P^\star=D^\star$ (their Theorem 1). This holds over the class of all policies; for an $\epsilon$-universal parameterised policy class their Theorem 2 only bounds how far the parameterised dual value $D^\star_\theta$ falls below the unrestricted optimum, $0\le P^\star-D^\star_\theta\le(B_{r_0}+\|\lambda^\star_\epsilon\|_1B_r)\,\Delta_\epsilon$, a term linear in $\epsilon$. Here $B_{r_i}$ bound the rewards, $B_r=\max_{i\ge1}B_{r_i}$, $\lambda^\star_\epsilon$ is the optimal multiplier of the unrestricted problem with every constraint tightened by $B_r\Delta_\epsilon$, and $\Delta_\epsilon=\epsilon/(1-\gamma)^2$ for the paper's unnormalised values (the paper prints $\epsilon/(1-\gamma)$, the right scale for returns normalised by $1-\gamma$). The parameterised problem's own duality gap $D^\star_\theta-P^\star_\theta$ is not bounded directly. This is the regime of Module 8, which derives the corrected constant.

Why occupancy measures form a convex set. For a finite discounted MDP with initial distribution $\mu$ and transition probabilities $P(s\mid s',a')$, let $d(s,a)=(1-\gamma)\sum_{t\ge0}\gamma^t\Pr(s_t=s,a_t=a)$. These nonnegative numbers satisfy the linear flow equations $\sum_a d(s,a)=(1-\gamma)\mu(s)+\gamma\sum_{s',a'}P(s\mid s',a')\,d(s',a')$, so a convex combination of two occupancy measures satisfies them too; conversely, every nonnegative solution is the occupancy measure of the stationary policy $\pi(a\mid s)=d(s,a)/\sum_bd(s,b)$ (any action where $\sum_bd(s,b)=0$). Values are linear in $d$: $V(\pi)=(1-\gamma)^{-1}\sum_{s,a}d(s,a)r(s,a)$. Mixing two policies at the level of $d$ therefore mixes their values linearly.

Proof of (ii). Write $\delta=B_r\Delta_\epsilon$, $D(\lambda)=\max_\pi\big[V_0(\pi)+\lambda^{\top}(V(\pi)-c)\big]$ and $P_\delta$ for the tightened optimum. The tightened problem has dual function $D(\lambda)-\delta\sum_i\lambda_i$, and it is again a linear program in $d$, so its gap is zero: $P_\delta=D(\lambda^\star_\epsilon)-\delta\|\lambda^\star_\epsilon\|_1\ge P^\star-\delta\|\lambda^\star_\epsilon\|_1$, using weak duality $D(\lambda)\ge P^\star$. Now approximate a tightened optimal policy by some $\pi_\theta$. By the return-error bound below, each value moves by at most $B_{r_i}\Delta_\epsilon$, so $\pi_\theta$ still satisfies $V_i\ge c_i$ and has $V_0(\pi_\theta)\ge P_\delta-B_{r_0}\Delta_\epsilon$. Because this $\pi_\theta$ is feasible, every $\lambda\ge0$ gives $\sup_\theta[\cdots]\ge V_0(\pi_\theta)$, hence $D^\star_\theta\ge P_\delta-B_{r_0}\Delta_\epsilon$; restricting the inner supremum to the class gives $D^\star_\theta\le D^\star=P^\star$. Combining the three inequalities gives the display. $\blacksquare$

Where $\epsilon/(1-\gamma)^2$ comes from. Run $\pi$ and $\pi_\theta$ from the same initial distribution and let $e_t$ be the $\ell_1$ distance between their state distributions at time $t$, so $e_0=0$. Adding and subtracting the joint law that pairs the first state distribution with the second policy shows that the state-action distributions differ by at most $e_t+\epsilon$. A transition kernel cannot increase $\ell_1$ distance: if $P_{ji}$ is the probability of moving to state $j$ from state-action pair $i$, then $\sum_j|\sum_iP_{ji}a_i|\le\sum_i|a_i|\sum_jP_{ji}=\sum_i|a_i|$. Hence $e_{t+1}\le e_t+\epsilon$, and by induction the time-$t$ state-action error is at most $(t+1)\epsilon$. With $|r|\le B_r$ the value error is at most $B_r\epsilon\sum_{t\ge0}(t+1)\gamma^t=B_r\epsilon/(1-\gamma)^2$, because $\big(\sum_{k\ge0}\gamma^k\big)^2$ contains each power $\gamma^t$ exactly $t+1$ times. For instance, $\gamma=0.9$, $B_r=1$, $\epsilon=0.01$ already allow a value error of $0.01/0.1^2=1$.

(a) Strong duality gives the chain

where the last step uses $\lambda^\star_i\ge0$, $f_i(x^\star)\le0$, $h_j(x^\star)=0$. The two ends are equal, so every inequality is an equality: $x^\star$ minimises $L(\cdot,\lambda^\star,\nu^\star)$ over the open set $\mathcal D$ (hence its gradient vanishes there: stationarity), and $\sum_i\lambda^\star_if_i(x^\star)=0$ with every term $\le0$ (hence each term is zero: complementary slackness).

(b) If the problem is convex, $L(\cdot,\lambda^\star,\nu^\star)$ is convex in $x$ and stationarity says $x^\star$ is its global minimiser, so $g(\lambda^\star,\nu^\star)=L(x^\star,\lambda^\star,\nu^\star)=f_0(x^\star)$ by complementary slackness. Weak duality closes the sandwich: $p^\star\ge d^\star\ge g(\lambda^\star,\nu^\star)=f_0(x^\star)\ge p^\star$. $\blacksquare$

Complementary slackness is the statement students most often misread: a multiplier can only be positive on an active constraint, and an inactive constraint has zero price. In the dual-ascent dynamics below this is exactly the "multiplier decays to zero while the constraint is slack" behaviour.

Problem (a quadratic program, see Primer B). $\min_{x\in\mathbb R^2}(x_1-2)^2+(x_2-1)^2$ subject to $x_1+x_2\le1$. Convex, and $x=0$ is strictly feasible, so strong duality holds.

KKT. With $f_1(x)=x_1+x_2-1$, stationarity reads $2(x_1-2)+\lambda=0$, $2(x_2-1)+\lambda=0$, i.e. $x_1=2-\lambda/2$, $x_2=1-\lambda/2$. Case $\lambda=0$: $x=(2,1)$, but $f_1=2\gt0$, infeasible. Case $\lambda\gt0$: complementary slackness forces $x_1+x_2=1$, i.e. $3-\lambda=1$, so $\lambda^\star=2$ and $x^\star=(1,0)$ with $p^\star=1+1=2$.

Dual function. Minimising the Lagrangian in closed form (same stationarity equations) gives

a concave parabola maximised at $\lambda=2$ with $d^\star=4-2=2=p^\star$: zero gap, as promised.

Shadow price. Perturb the constraint to $x_1+x_2\le1+u$. The optimum is the squared distance from $(2,1)$ to the line $x_1+x_2=1+u$, $p^\star(u)=(2-u)^2/2$ for $u\le2$, so $-\mathrm dp^\star/\mathrm du\,|_{u=0}=2=\lambda^\star$. Relaxing the constraint by one unit is worth two units of objective, at the margin.

Take the problem from Primer B's KKT examples: minimise $f_0(x)=(x_1-2)^2+(x_2-1)^2$ subject to $f_1(x)=x_1+x_2-1\le0$. Its optimum is $x^\star=(1,0)$ with $p^\star=2$.

Step 1: the Lagrangian. $L(x,\lambda)=(x_1-2)^2+(x_2-1)^2+\lambda(x_1+x_2-1)$.

Step 2: minimise over $x$, ignoring the constraint. Setting the gradient to zero, $2(x_1-2)+\lambda=0$ and $2(x_2-1)+\lambda=0$, gives $x_1=2-\lambda/2$ and $x_2=1-\lambda/2$.

Step 3: substitute back.

Step 4: read off the bounds. Every price gives a lower bound on $p^\star=2$: $g(0)=0$, $g(1)=1.5$, $g(3)=1.5$. The best price maximises $g$: $g'(\lambda)=2-\lambda=0$ gives $\lambda^\star=2$ and $d^\star=g(2)=2=p^\star$. The gap is zero, as the strong duality theorem promises for this convex problem with a strictly feasible point (for example $x=(0,0)$). The best price $\lambda^\star=2$ is exactly the KKT multiplier found in Primer B.

Duality gaps appear when the problem is not convex. Let the decision be yes or no, $x\in\mathcal D=\{0,1\}$, and minimise $f_0(x)=x$ subject to $f_1(x)=0.5-x\le0$. Only $x=1$ is feasible, so $p^\star=1$.

The dual function minimises $L(x,\lambda)=x+\lambda(0.5-x)$ over the two points of $\mathcal D$:

The first term rises with $\lambda$ and the second falls, so the best price is where they cross, $\lambda=1$, with $d^\star=0.5$. The gap is $p^\star-d^\star=0.5$. The dual answers the question as if $x=0.5$ were allowed: it only sees the convex relaxation $x\in[0,1]$ of the yes/no choice. The same mechanism gives a gap when constrained RL optimises over a restricted, non-convex policy class (Module 8).

Dualise $\min_x c^{\top}x$ s.t. $F(x)\succeq0$ exactly as in Section 1, but with a matrix multiplier $Z\in\mathbb S^n$ and the pairing $\operatorname{tr}(ZF)$: $L(x,Z)=c^{\top}x-\operatorname{tr}\big(ZF(x)\big)=\sum_ix_i\big(c_i-\operatorname{tr}(F_iZ)\big)-\operatorname{tr}(F_0Z)$. This is affine in $x$, so its infimum is $-\infty$ unless every coefficient vanishes, and the dual problem is

Weak duality in one line. For primal-feasible $x$ and dual-feasible $Z$: $c^{\top}x+\operatorname{tr}(F_0Z)=\sum_ix_i\operatorname{tr}(F_iZ)+\operatorname{tr}(F_0Z)=\operatorname{tr}\big(F(x)Z\big)=\operatorname{tr}\big(Z^{1/2}F(x)Z^{1/2}\big)\ge0$. The condition $Z\succeq0$ plays the role of $\lambda\ge0$: the PSD cone is self-dual ($\operatorname{tr}(FZ)\ge0$ for every $F\succeq0$ iff $Z\succeq0$). If the primal is strictly feasible and $p^\star$ is finite, then $p^\star=d^\star$ and the dual optimum is attained (Slater for generalized inequalities, Boyd & Vandenberghe Sec. 5.9, Example 5.11), and an optimal pair satisfies $\operatorname{tr}\big(F(x^\star)Z^\star\big)=0$, i.e. $F(x^\star)Z^\star=0$: complementary slackness as a matrix product.

The two missing steps. Self-duality, converse direction: if $\operatorname{tr}(FZ)\ge0$ for every $F\succeq0$, test with $F=vv^{\top}$ to get $\operatorname{tr}(Zvv^{\top})=v^{\top}Zv\ge0$ for every $v$, i.e. $Z\succeq0$. Complementary slackness: for $F,Z\succeq0$, cyclicity of the trace gives $\operatorname{tr}(FZ)=\operatorname{tr}\big((F^{1/2}Z^{1/2})(F^{1/2}Z^{1/2})^{\top}\big)=\|F^{1/2}Z^{1/2}\|_F^2$, the sum of squared entries (Frobenius norm). If this trace is zero then $F^{1/2}Z^{1/2}=0$, hence $FZ=F^{1/2}(F^{1/2}Z^{1/2})Z^{1/2}=0$.

Why it matters for certificates. Any dual-feasible $Z$ proves the lower bound $c^{\top}x\ge-\operatorname{tr}(F_0Z)$ without trusting the solver, and infeasibility has a certificate too: the strict LMI $F(x)\succ0$ is infeasible iff there is $Z\succeq0$, $Z\ne0$, with $\operatorname{tr}(F_iZ)=0$ for all $i$ and $\operatorname{tr}(F_0Z)\le0$ (Boyd & Vandenberghe, Example 5.14). The easy direction is the same trace argument: $F(x)\succ0$ and $Z\ne0$ would give $0\lt\operatorname{tr}(F(x)Z)=\operatorname{tr}(F_0Z)\le0$.

(ii) $\Rightarrow$ (i). Since $A^{\top}PA-P\prec0$ there is $\epsilon\gt0$ with $A^{\top}PA-P\preceq-\epsilon I$ (take $\epsilon$ the smallest eigenvalue of $P-A^{\top}PA$). Along a trajectory, $V(x_{t+1})-V(x_t)=x_t^{\top}(A^{\top}PA-P)x_t\le-\epsilon\|x_t\|^2\le-\tfrac{\epsilon}{\lambda_{\max}(P)}V(x_t)$, so $V(x_t)\le(1-\epsilon/\lambda_{\max}(P))^tV(x_0)\to0$ geometrically; because $V(x)\ge\lambda_{\min}(P)\|x\|^2$ with $\lambda_{\min}(P)\gt0$, every trajectory converges to $0$, which for a linear map means $\rho(A)\lt1$ (an eigenvector of an eigenvalue with $|\lambda|\ge1$ would not decay).

(i) $\Rightarrow$ (iii). If $\rho(A)\lt1$ the series $P=\sum_{k\ge0}(A^{\top})^kQA^k$ converges, is $\succeq Q\succ0$, and satisfies $A^{\top}PA-P=\sum_{k\ge1}(A^{\top})^kQA^k-\sum_{k\ge0}(A^{\top})^kQA^k=-Q$. Uniqueness: the linear map $P\mapsto A^{\top}PA-P$ has eigenvalues $\lambda_i\lambda_j-1$ ($\lambda_i$ eigenvalues of $A$), all nonzero when $\rho(A)\lt1$. Finally (iii) $\Rightarrow$ (ii) is immediate with $Q=I$. $\blacksquare$ The second interactive explorer solves exactly this Stein equation for a $2\times2$ system and draws the certificate.

Convergence and uniqueness without operator eigenvalues. For Schur-stable $A$ and any $q$ with $\rho(A)\lt q\lt1$ there is $c\ge1$ with $\|A^k\|_2\le c\,q^k$ (Primer D). Each summand therefore has norm $\|(A^{\top})^kQA^k\|_2\le c^2\|Q\|_2\,q^{2k}$, and the series converges by comparison with a geometric series. If $P_1,P_2$ both solve the Stein equation, $H=P_1-P_2$ satisfies $H=A^{\top}HA$; iterating gives $H=(A^{\top})^kHA^k\to0$, so $H=0$.

ADMM is the alternating direction method of multipliers. It keeps two copies of the variable, writes the task as $\min_{W,Z}\ell(W)+I_C(Z)$ subject to $W=Z$, where $I_C$ is zero on the certificate-feasible set $C$ and $+\infty$ outside it, and alternates three steps: minimise the loss plus an agreement penalty over $W$, project onto $C$ to update $Z$, and update a multiplier that accumulates the disagreement $W-Z$. This describes the training strategy; convergence guarantees for convex splitting do not automatically apply to a neural-network loss.

For example, with $C=[-1,1]$, the constrained copy of a scalar weight $2$ is pulled back to $1$. With penalty $r>0$ and scaled multiplier $u$, the agreement penalty is $(r/2)\|W-Z+u\|^2$; after the two minimisations, set $u^+=u+W-Z$. This split makes the certificate step explicit.

Consider the LMI in two unknowns $x$ and $y$:

A symmetric $2\times2$ matrix is positive semidefinite exactly when both diagonal entries and the determinant are nonnegative. Here that means $x\ge0$, $y\ge0$ and $xy-1\ge0$. The solution set is the region on and above the hyperbola $y=1/x$ in the first quadrant. It is convex, but its boundary is curved, so finitely many linear inequalities could not describe it.

• $(x,y)=(2,0.5)$: $xy=1$, on the boundary. The matrix has eigenvalues $0$ and $2.5$.
• $(x,y)=(2,0.4)$: $xy=0.8\lt1$, outside. The determinant is $-0.2$, so one eigenvalue is negative.
• $(x,y)=(0.5,3)$: $xy=1.5$, inside.

Averaging the two feasible points $(2,0.5)$ and $(0.5,3)$ gives $(1.25,1.75)$, with $xy=2.19\ge1$: feasible again, as convexity guarantees.

The system $x_{t+1}=Ax_t$ with $A=\begin{bmatrix}0.5&1\\0&0.5\end{bmatrix}$ is stable: both eigenvalues are $0.5$, so $\rho(A)=0.5\lt1$ and every trajectory goes to zero. The Lyapunov LMI asks for $P\succ0$ with $A^{\top}PA-P\prec0$, so that $V(x)=x^{\top}Px$ decreases at every step.

The obvious guess fails. With $P=I$, $V(x)=\|x\|^2$ is the squared length. But from $x_0=(0,1)$ the first step gives $x_1=(1,0.5)$, with $\|x_1\|=1.118\gt1$: the length grows before it shrinks. Correspondingly, $A^{\top}A-I$ has a positive eigenvalue, so $P=I$ is not a certificate.

Solving for $P$. Solve the Stein equation $A^{\top}PA-P=-I$, which is linear in the three unknown entries of $P$:

So $P\succ0$ and $A^{\top}PA-P=-I\prec0$: a valid certificate. Along the same trajectory $V(x_0)=4.2963$ and $V(x_1)=3.2963$. $V$ drops by exactly $\|x_0\|^2=1$, because $V(x_{t+1})-V(x_t)=x_t^{\top}(A^{\top}PA-P)x_t=-\|x_t\|^2$. A tilted ellipse measures progress where the round circle could not.

Assume $C\succ0$ and define the invertible block-triangular matrix $R=\begin{bmatrix}I&-BC^{-1}\\0&I\end{bmatrix}$. Multiply out, one factor at a time:

So $RMR^{\top}=\mathrm{blkdiag}(S,C)$. By the congruence fact of Section 2 with the invertible $R^{\top}$, $M\succeq0\iff RMR^{\top}\succeq0\iff S\succeq0$ and $C\succeq0$; the second condition is given, so $M\succeq0\iff S\succeq0$. The strict version is identical with $\succ$. Swapping the roles of the blocks (conjugate with $\begin{bmatrix}I&0\\-B^{\top}A^{-1}&I\end{bmatrix}$) gives the second bullet, and applying the first bullet to $-M$ gives the negative form. $\blacksquare$

The scalar picture. For vectors $x,y$ the identity behind the algebra is completing the square:

Minimising over $y$ kills the first term (choose $y=-C^{-1}B^{\top}x$), so the quadratic form is nonnegative for all $(x,y)$ iff its minimum over $y$, the Schur-complement form, is nonnegative in $x$.

Write $\delta x=x-x_*$ and $v_i-v_{*,i}=W_i\delta x$. To guarantee $\underline v_i\le v_i\le\bar v_i$, define $m_i=\min\{\bar v_i-v_{*,i},v_{*,i}-\underline v_i\}>0$. It suffices to require $|W_i\delta x|\le m_i$ throughout $\delta x^TP\delta x\le1$, equivalently $\begin{bmatrix}m_i^2&W_i\\W_i^T&P\end{bmatrix}\succeq0$. Using only $\bar v_i-v_{*,i}$ assumes this is the smaller available margin.

Testing a matrix. Is $M=\begin{bmatrix}2&1\\1&1\end{bmatrix}$ positive definite? The top-left block $A=2$ is positive, and its Schur complement is $C-B^{\top}A^{-1}B=1-1\cdot\tfrac12\cdot1=0.5\gt0$. So $M\succ0$. Check: the eigenvalues are $(3\pm\sqrt5)/2$, about $0.382$ and $2.618$, both positive.

Turning a nonlinear condition into an LMI. The condition $\|x\|^2\le t$ is quadratic in $x$. With $C=I\succ0$, the Schur complement theorem gives

and the matrix on the left is affine in the unknowns $(t,x)$: an LMI. For $x=(3,4)$ we have $\|x\|^2=25$, and the block matrix is positive semidefinite for $t=25$ (on the boundary) and $t=26$, but not for $t=24$.

Sufficiency. Take $\xi$ with $\sigma_i(\xi)\ge0$ for all $i$. Since $\tau_i\ge0$, $\sum_i\tau_i\sigma_i(\xi)\ge0$, and the premise gives $\sigma_0(\xi)\ge\sum_i\tau_i\sigma_i(\xi)\ge0$. $\blacksquare$ Compare with weak duality: the multipliers price the constraints and the premise says the priced objective is nonnegative everywhere; the conclusion follows on the feasible set because the prices are nonnegative.

Homogenisation. Write $\sigma(\xi)=\begin{bmatrix}\xi\\1\end{bmatrix}^{\top}N\begin{bmatrix}\xi\\1\end{bmatrix}$ with $N=\begin{bmatrix}A&b\\b^{\top}&c\end{bmatrix}$. If $N\succeq0$ then clearly $\sigma\ge0$. Conversely, if $\sigma(\xi)\ge0$ for all $\xi$, then for $t\ne0$, $\begin{bmatrix}\xi\\t\end{bmatrix}^{\top}N\begin{bmatrix}\xi\\t\end{bmatrix}=t^2\sigma(\xi/t)\ge0$, and the case $t=0$ follows by continuity; so $N\succeq0$. $\blacksquare$

The proof rests on a classical fact about pairs of real quadratic forms: by Dines, Bull. AMS 1941, the joint range $K=\{(\xi^{\top}A\xi,\ \xi^{\top}B\xi):\xi\in\mathbb R^n\}\subset\mathbb R^2$ is a convex cone. (This is false for three forms in general, which is one reason the S-lemma stops at one constraint.)

Assume the implication holds. Then no $\xi$ has $\xi^{\top}A\xi\ge0$ and $\xi^{\top}B\xi\lt0$, so $K$ does not meet the open convex quadrant $\mathcal M=\{(u,v):u\gt0,\ v\lt0\}$. By the separating-hyperplane theorem of Section 1 (which needs no closedness of $K$, because $\mathcal M$ is open) there are $(p,q)\ne0$ and $c$ with $pu+qv\ge c$ on $K$ and $pu+qv\le c$ on $\mathcal M$; and $c=0$, since $0\in K$ gives $c\le0$ while points of $\mathcal M$ arbitrarily close to the origin give $c\ge0$. So $pu+qv\ge0$ on $K$ and $pu+qv\le0$ on $\mathcal M$. On $\mathcal M$, letting $u\to\infty$ forces $p\le0$ and letting $v\to-\infty$ forces $q\ge0$. On $K$ the inequality reads $p\,\xi^{\top}A\xi+q\,\xi^{\top}B\xi\ge0$ for all $\xi$.

If $q\gt0$, divide by $q$ and set $\tau=-p/q\ge0$: $\xi^{\top}(B-\tau A)\xi\ge0$ for all $\xi$, i.e. $B-\tau A\succeq0$. If $q=0$ then $p\lt0$ and the inequality says $\xi^{\top}A\xi\le0$ for all $\xi$, contradicting the strictly feasible $\bar\xi$. So $q\gt0$ and the multiplier exists. $\blacksquare$ Strict feasibility is used exactly once, to exclude the degenerate separating line $u=0$.

Claim: if $x^2\le1$, then $2-x-x^2\ge0$. In S-procedure form, $\sigma_1(x)=1-x^2\ge0$ should imply $\sigma_0(x)=2-x-x^2\ge0$. (The claim is true, because $2-x-x^2=(1-x)(2+x)$ is nonnegative on $[-1,1]$.)

Step 1: the certificate condition. We need $\tau\ge0$ with $\sigma_0(x)-\tau\sigma_1(x)\ge0$ for all real $x$:

Step 2: when is a quadratic nonnegative everywhere? Its leading coefficient must be positive, $\tau\gt1$, and its discriminant must be at most zero: $1-4(\tau-1)(2-\tau)\le0$. Expanding gives $4\tau^2-12\tau+9\le0$, that is, $(2\tau-3)^2\le0$, so $\tau=1.5$ exactly.

Step 3: the certificate. With $\tau=1.5$ the difference is $0.5x^2-x+0.5=0.5(x-1)^2\ge0$, a perfect square. So for every $x$ with $1-x^2\ge0$ we get $2-x-x^2\ge1.5\,(1-x^2)\ge0$. Any other $\tau$, for example $1.4$ or $1.6$, makes the difference negative somewhere. The S-lemma guaranteed that this search would succeed, because the constraint is strictly feasible ($\sigma_1(0)=1\gt0$) and the implication is true.

A discrete-time map $F$ is a contraction in a chosen norm if $\|F(x)-F(y)\|\le q\|x-y\|$ for all $x,y$ with a fixed $q\lt1$. Iteration then gives $\|x_t-y_t\|\le q^t\|x_0-y_0\|$ for any two trajectories $x_{t+1}=F(x_t)$, $y_{t+1}=F(y_t)$. An incremental QC can help prove such a bound, but a finite Lipschitz constant greater than or equal to one does not establish contraction.

For $F(x)=x/2$, two initial points a distance $8$ apart are distances $4,2,1$ apart after one, two and three steps. A weighted norm $\|x\|_P=\sqrt{x^TPx}$ with $P\succ0$ is a constant contraction metric when the same shrinking inequality holds in it. This is stronger than merely bounding a network output difference.

Here $j^2=-1$, $\hat v(j\omega)$ is the Fourier transform of the time signal $v$, and $M^*=\overline M^T$ is conjugate transpose. A Hermitian matrix satisfies $M=M^*$; its quadratic form $z^*Mz$ is real, and $M\succeq0$ means this is nonnegative for every complex vector $z$. Thus complex congruence $R^*MR$ plays the same role as real congruence $R^TMR$.

For example, $z=(1,j)^T$ gives $z^*z=2$, whereas $z^Tz=0$: conjugation is essential to energy. Also $e^{j\theta}=\cos\theta+j\sin\theta$, and $\overline{a+jb}=a-jb$. The largest singular value of $G$ is $\sqrt{\lambda_{\max}(G^*G)}$. These are the complex versions of the real matrix operations used above.

With plant $\dot x=Ax+Bw$, $v=Cx+Dw$, split the filter input blocks as $B_\psi=[B_v\ B_w]$, $D_\psi=[D_v\ D_w]$, where the filter is $\dot\eta=A_\psi\eta+B_\psi[v;w]$, $r=C_\psi\eta+D_\psi[v;w]$, and put $\chi=(x,\eta)$. Substituting $v=Cx+Dw$ into the filter equations gives

Use zero initial plant and filter states for the transfer-function identity. This triangular $A_a$ is Hurwitz when $A$ and $A_\psi$ are Hurwitz. In the strict frequency test $X$ is only required to be symmetric; a direct storage proof must separately justify its terminal sign.

Take the one-neuron network $f(x)=w_2\,\mathrm{ReLU}(w_1x)$ with $w_1=2$ and $w_2=3$. Its true Lipschitz constant is $|w_1w_2|=6$, the slope where the neuron is on. Can the quadratic-constraint machinery find it without knowing where the neuron is on or off?

Step 1: the fact. ReLU is slope-restricted in $[0,1]$. Let $\Delta v=w_1\Delta x$ be the pre-activation increment and $\Delta z$ the neuron's output increment. The incremental QC of the lemma above, with $\alpha=0$ and $\beta=1$, reads $2\lambda\,\Delta z\,(w_1\Delta x-\Delta z)\ge0$ for any $\lambda\ge0$.

Step 2: what we want. $|\Delta f|\le L\,|\Delta x|$, that is, $L^2\Delta x^2-w_2^2\Delta z^2\ge0$ for all increments the neuron can produce.

Step 3: the S-procedure. It suffices that

Step 4: solve. The $2\times2$ test needs $2\lambda-9\ge0$ and a nonnegative determinant, $L^2(2\lambda-9)-4\lambda^2\ge0$. At $\lambda=9/2$ the determinant is $-4\lambda^2\lt0$ whatever $L$ is, so $\lambda\gt9/2$, and then $L^2\ge4\lambda^2/(2\lambda-9)$. Minimising over $\lambda$ gives $\lambda=9$ and $L^2=36$: $L=6$, the exact constant. The matrix is then $\begin{bmatrix}36&-18\\-18&9\end{bmatrix}$, with eigenvalues $0$ and $45$.

Any other admissible multiplier, $\lambda\gt9/2$, still gives a valid bound, just a looser one: $\lambda=12$ gives $L\approx6.20$. Choosing the multipliers well is exactly what the SDP in LipSDP does, for thousands of neurons at once (Module 12).

Let $\chi$ be the combined plant/filter state with $\chi^+=A_{\rm tot}\chi+B_{\rm tot}w$, let $r=C_{\rm tot}\chi+D_{\rm tot}w$ be the filter output, and let $V(\chi)=\chi^{\top}X\chi$. The dot in the certificate repeats the left factor $H=\begin{bmatrix}I&0\\A_{\rm tot}&B_{\rm tot}\\C_{\rm tot}&D_{\rm tot}\end{bmatrix}$, and $H(\chi,w)=(\chi,\chi^+,r)$, so

Hence $H^{\top}\mathrm{diag}(-X,X,P)H\prec0$ says $V(\chi^+)-V(\chi)\lt-r^{\top}Pr$ for every nonzero $(\chi,w)$: a dissipation inequality with supply $-r^{\top}Pr$. Summed over time, the IQC makes $\sum_tr_t^{\top}Pr_t\ge0$, so the storage must decrease; this is how the multiplier enters the stability proof.

Fix $\omega$ and write $\Phi(\omega)=\begin{bmatrix}(j\omega I-A)^{-1}B\\I\end{bmatrix}$. Multiply (ii) from the left by $\Phi^{*}$ and from the right by $\Phi$ (congruence, Section 2, so $\preceq0$ is preserved). The $M$-term becomes the left-hand side of (i). For the $P$-term, put $X=(j\omega I-A)^{-1}B$, so that $j\omega X=AX+B$, and compute

So the $P$-term contributes nothing and (i) follows. $\blacksquare$ The same cancellation, in the time domain, is the statement that a quadratic storage function integrates to zero along a periodic (sinusoidal) steady state. The hard direction (i) $\Rightarrow$ (ii) is what makes SDP-based robust control complete rather than merely sufficient; Rantzer's proof is a separation argument on a convex set, in the same spirit as the S-lemma proof of Section 4. For the discrete-time version (no eigenvalues of $A$ on the unit circle) replace $(j\omega I-A)^{-1}$ by $(e^{j\omega}I-A)^{-1}$, $\omega\in[0,2\pi)$, and the whole $P$-term by $\begin{bmatrix}A^{\top}PA-P&A^{\top}PB\\B^{\top}PA&B^{\top}PB\end{bmatrix}$, the storage block of the discrete-time dissipativity LMI above (replacing only the $(1,1)$ block would be wrong). The easy direction is the same computation: with $z=e^{j\omega}$ and $X=(zI-A)^{-1}B$ we have $zX=AX+B$, so the $P$-term contributes $(AX+B)^{*}P(AX+B)-X^{*}PX=(|z|^2-1)X^{*}PX=0$.

Suppose $A^{\top}P+PA\preceq0$ (the $(1,1)$ block of (ii) when the $(1,1)$ block of $M$ is $\succeq0$, as for the gain and passivity supplies) and set $Q=-(A^{\top}P+PA)\succeq0$. Along the unforced system $x(t)=e^{At}x_0$, $\tfrac{d}{dt}\,x^{\top}Px=x^{\top}(A^{\top}P+PA)x=-x^{\top}Qx$. Because $A$ is Hurwitz, $x(t)\to0$, and integrating from $0$ to $\infty$ gives $x_0^{\top}Px_0=\int_0^\infty x(t)^{\top}Qx(t)\,dt\ge0$ for every $x_0$, so $P\succeq0$.

System: $x_{t+1}=0.5\,x_t+w_t$ with output $z_t=x_t$. Try storage $V(x)=p\,x^2$ with supply rate $s(w,z)=\gamma^2w^2-z^2$. The dissipation inequality $p(0.5x+w)^2-px^2\le\gamma^2w^2-x^2$ must hold for all $x$ and $w$. Collecting terms gives

For a $2\times2$ matrix to be $\preceq0$, both diagonal entries must be $\le0$ and the determinant $\ge0$. The diagonal gives $p\ge4/3$, but at $p=4/3$ the determinant is $-4/9\lt0$, so $p\gt4/3$. The determinant condition then becomes $\gamma^2\ge p+p^2/(3p-4)$. The right side is smallest at $p=2$, where it equals $4$. So $\gamma=2$, certified by $V(x)=2x^2$. The matrix is then $\begin{bmatrix}-0.5&1\\1&-2\end{bmatrix}$, with eigenvalues $0$ and $-2.5$.

Sanity check. A constant input $w_t=1$ settles at $x=0.5x+1$, that is, $x=2$: the output is twice the input. The frequency response $G(e^{j\omega})=1/(e^{j\omega}-0.5)$ has its largest magnitude at $\omega=0$, also $1/(1-0.5)=2$. The storage-function LMI found the exact gain, as the KYP lemma promises for linear systems.

The button approximately maximises $h(\tau)=\lambda_{\min}(B-\tau A)=\min_{\|u\|=1}(u^TBu-\tau u^TAu)$. This is concave because it is an infimum of affine functions of $\tau$. Ternary search (see Primer B) compares two interior points and discards a third of the interval that cannot contain a better value. For these sliders (eigenvalues in $[-3,3]$ in steps of $0.1$), strict feasibility gives $\lambda_{\max}(A)\ge0.1$ and $\|B\|_2\le3$, so $h(\tau)\le3-0.1\tau$, while $h(0)\ge-3$; hence $h(\tau)\lt h(0)$ for $\tau\gt60$, and no maximiser lies above 60.

Automatic maximisation is disabled when $A\preceq0$: then every $u^{\top}Au\le0$, so $h(\tau)$ is nondecreasing and it may grow without bound, approach an unattained limit, or attain a maximum. For example, when $A=0$, it is constant and every $\tau\ge0$ is a maximiser. The current multiplier can still be checked directly.

Write $A=\begin{bmatrix}a&b\\c&d\end{bmatrix}$ and $P=\begin{bmatrix}p&q\\q&r\end{bmatrix}$. Matching the three independent entries of $A^TPA-P=-I$ gives $(a^2-1)p+2acq+c^2r=-1$, $abp+(ad+bc-1)q+cdr=0$, and $b^2p+2bdq+(d^2-1)r=-1$. Gaussian elimination solves for $(p,q,r)$. Positive definiteness then requires $p\gt0$ and $pr-q^2\gt0$. If elimination meets a pivot below its numerical threshold, the explorer reports that no reliable unique solution was found. In exact arithmetic the Stein map $P\mapsto A^{\top}PA-P$ is singular iff $\lambda_i\lambda_j=1$ for some pair of eigenvalues of $A$, which rules out Schur stability; a tiny pivot is only numerical evidence of (near-)singularity, not a proof.

The slider controls the ellipse parameter $\theta$: if $P$ has eigenvalues $\mu_1,\mu_2\gt0$ with orthonormal eigenvectors $u_1,u_2$, then $x_0=\frac{\cos\theta}{\sqrt{\mu_1}}u_1+\frac{\sin\theta}{\sqrt{\mu_2}}u_2$. This guarantees $x_0^TPx_0=1$ but generally differs from the polar angle of $x_0$. Without a positive definite $P$, the initial point is instead chosen on a circle of radius 0.6. Hollow eigenvalue markers indicate values beyond the plotting range.