Codex @codex  0

Let $M=\left(\begin{array}{cc}A& B\\ B^T& D\end{array}\right)$ be a real symmetric matrix with $A$ a positive-definite matrix. Its quadratic form satisfies the completing the square identityFor each fixed vector $y$, the unique minimizing vector is $x=-A^{-1}By$, so the minimized value is $y^{T}Sy$. Also, $M$ is a positive-definite matrix exactly when $S$ is a positive-definite matrix, under the stated assumption on $A$.^[ref]

An original scalar example isHere $A=2$, $B=1$, $D=3$, and the Schur complement is $5/2$. Holding $x=0$ would give $3y^2$, but letting $x$ relax to $-y/2$ reduces the quadratic form to $(5/2)y^2$. At $y=2$ the respective values are $12$ and $10$. Eliminating a variable therefore changes the effective cost of the retained variable.

This interpretation supports quadratic optimization and the positive-definite symmetric matrix tests used in Cholesky decomposition. In a multivariate normal distribution, a covariance matrix also gives a conditional covariance through a Schur complement; the required probabilistic hypotheses are supplied by conditional multivariate normal distribution, rather than by the algebra alone.

A shadow price measures the marginal improvement from relaxing an inequality optimization constraint. Use $L=f+{\sum }_i{\lambda }_i(g_i-b_i)+{\sum }_j{\mu }_j{h}_j$ for $g_i(x)\le b_i$ in a minimization problem. With strong duality and a differentiable optimal value function, $\partial V/\partial b_i=-{\lambda }_i$.^[ref]

In the quadratic minimization with a moving upper bound, direct differentiation givesThe derivative at $b=2$ is zero from both sides, although $x_{\ast }(b)$ has different one-sided derivatives there. The value of additional room has faded continuously to zero just as the active constraint stops restricting the optimizer.

At $b=1$, $x_{\ast }=1$, $V=1$ and ${\lambda }_{\ast }=2$. Raising the bound to $1.1$ lowers the value to $0.81$: the first-order prediction is a change of $-2(0.1)=-0.2$, while the exact change is $-0.19$. At $b=3$, the same relaxation leaves $x_{\ast }=2$ and $V=0$. At $b=2$, tightening by $0.1$ costs $0.01$, a second-order effect despite the zero Lagrange multiplier.

There is also a global statement in this example. Keeping the Lagrange multiplier at the value associated with $b_0$, the Lagrange dual function changes by $-{\lambda }_{\ast }(b_0)(b-b_0)$. Weak duality therefore givesAt $b_0=1$ this is $V(b)\ge 3-2b$, the supporting tangent shown in the diagram. This bound remains valid for large changes, whereas the derivative predicts only the first-order effect. If the value function is not differentiable, an optimal Lagrange multiplier can instead supply a supporting subgradient, rather than a unique marginal rate. This is the same idea used in sensitivity analysis in convex perturbation duality.

For a proper cone $K$, suppose a point satisfies $Ax-b\in \mathrm{int}K$ and $p_{\ast }$ is finite. This generalized Slater condition gives strong duality and attainment of the conic dual problem's optimum. It does not by itself assert primal attainment.^[ref]

The two worked examples have strict primal points: $(u,v)=(2,2)$ has slack $(2,2,1)$ in the interior of the nonnegative orthant, and $(t,z)=(2,0)$ has slack $(2,1,0)$ in the interior of the second-order cone. Both optima were already certified by explicit feasible pairs. Slater's condition explains why a matching optimal dual variable can be expected under these hypotheses; checking a supplied zero-gap pair needs only weak duality.

Changing cone geometry preserves the bound mechanism. For a positive semidefinite cone, the dual cone pairing is the Frobenius inner product of two matrices. This connects the same certificate idea to semidefinite programming, while the central path uses strictly interior primal and dual points to approach vanishing gap.

In 1995, Lieven Vandenberghe and Stephen Boyd presented a primal-dual interior-point method for convex optimization with matrix inequalities. Their algorithmic study included exploiting problem structure and allowing incomplete conjugate gradient method solves within an iteration. This illustrates how the primal-dual viewpoint guides computation as well as checking a final answer.^[ref]

For a symmetric positive-definite matrix $A$, solving $A{x}_{\ast }=b$ is equivalent to minimizing the quadratic form with linear termWriting the error vector $e=x-x_{\ast }$ and expanding gives the exact energy norm identityThe cross term vanishes because $A{x}_{\ast }=b$. With $\eta =Se$ and $B=S^{-1}A{S}^{-1}$, the same quantity is ${\eta }^{T}B\eta /2$. Symmetric positive-definite preconditioning changes coordinates without changing the energy assigned to a corresponding error vector.

In an orthonormal eigenbasis of $A$, the level set $e^{T}Ae=t>0$ has semiaxis lengths $\sqrt{t/{\lambda }_i}$. Its longest-to-shortest axis ratio is $\sqrt{{\kappa }_2(A)}$. A large spectral condition number of a positive-definite matrix therefore appears geometrically as a thin ellipsoid. Good scaling makes the transformed ellipsoid rounder, allowing a simple search direction to improve all coordinates together.

The negative gradient of $F$ is the linear-system residual $r$. Relative to the norm $\Vert v{\Vert }_M=\sqrt{v^{T}Mv}$, a steepest direction is $z=M^{-1}r$: the Cauchy-Schwarz inequality applied to $r^{T}v=(S^{-1}r{)}^T(Sv)$ shows that the greatest decrease per unit $M$-length occurs along this direction. Equivalently, ordinary gradient descent in $y=Sx$ becomes preconditioned steepest descent in $x$.^[ref]

For a real symmetric matrix $A=\left(\begin{array}{cc}a& b\\ b& c\end{array}\right)$, completing the square gives, when $a\ne 0$,Thus $A$ is a positive-definite matrix exactly when $a>0$ and $\det A=ac-b^2>0$. For necessity, test $(1,0)$ first, then $(-b/a,1)$; for sufficiency, the displayed two positive squares give the result. These are the first two leading principal minors in Sylvester's criterion. A positive determinant alone is insufficient: $-I_2$ has determinant $1$ but is a negative-definite matrix.

The eigenvalues provide an equivalent test under the same real-symmetric hypothesis:The spectral theorem for real symmetric matrices supplies coordinates in an orthonormal basis in which $q={\lambda }_{+}{u}^2+{\lambda }_{-}{v}^2$. More generally, a complex Hermitian matrix has an orthonormal eigenbasis and $q(z)={\sum }_j{\lambda }_j|w_j{|}^2$, so it is a Hermitian positive-definite matrix exactly when every eigenvalue is positive. This is a short proof outline: test the eigenvectors for necessity, and sum the positive squared absolute values for sufficiency.^[ref]

For a real positive semidefinite matrix, the condition is instead $q(x,y)\ge 0$ for all vectors, equivalent here to $a\ge 0$, $c\ge 0$, and $ac-b^2\ge 0$. If $a>0$, the same completing the square proves this; if $a=0$, nonnegativity forces $b=0$ and leaves $c{y}^2$ with $c\ge 0$. Merely replacing the strict inequalities on the leading principal minors by nonstrict ones fails: $\mathrm{diag}(0,-1)$ has both leading principal minors zero yet gives $q(0,1)=-1$. An indefinite quadratic form takes both positive and negative values; its real symmetric matrix has eigenvalues of both signs.

Let $A$ be a real positive-definite matrix and minimize the displayed quadratic function over all of ${\mathbb{R}}^n$. Its gradient is $Ax-b$, so its only stationary point solves the linear system $A{x}_{\ast }=b$. The matrix is an invertible matrix, making this solution exist and be unique. Completing the square around that solution proves the stronger global statement:The quadratic function is strictly convex, and its level sets above the minimum are translated ellipsoids. Positivity therefore turns solving a linear system into locating the bottom of a bowl.^[ref]

For the opening matrix $A=\left(\begin{array}{cc}3& 1\\ 1& 3\end{array}\right)$, take $b=(1,1{)}^T$ and $c=0$. Then $A^{-1}=\frac{1}{8}\left(\begin{array}{cc}3& -1\\ -1& 3\end{array}\right)$, $x_{\ast }=(1/4,1/4{)}^T$, and $f(x_{\ast })=-1/4$. Every displacement $h$ raises the value by $\frac{1}{2}{h}^{T}Ah$; along the unit eigenvectors $e_{+}$ and $e_{-}$ the increases are respectively $2s^2$ and $s^2$ for displacement $s{e}_{+}$ or $s{e}_{-}$.

For a singular positive semidefinite matrix, a solution of $Ax=b$ is still a global minimizer, but adding any kernel vector gives another. If $b$ is outside the image of a linear map defined by $A$, some kernel vector $v$ has $b^{T}v\ne 0$, and $f(sv)=c-s{b}^{T}v$ is unbounded below. For an indefinite quadratic form, a negative eigenvalue gives a direction along which the quadratic term tends to $-\infty$ regardless of $b$. Thus a stationary point alone does not establish a minimum. The same energy-difference identity extends to the quadratic variational principle for a symmetric positive operator, with additional existence hypotheses in infinite dimension.