Positive-Semidefinite Order in Optimization

Why Matrix Inequalities Matter

In matrix optimization, an inequality between matrices is not interpreted entry by entry. Instead, it expresses a relationship between the quadratic forms generated by the matrices. This perspective is useful because quadratic forms appear directly in quadratic objectives, and Hessians describe how those objectives curve in different directions.

The positive-semidefinite order, also called the Loewner order, packages these comparisons into a single notation. It lets us compare quadratic objectives, derive bounds from eigenvalues, and establish curvature bounds without examining every direction separately.

Definition: A real square matrix $A$ is symmetric positive semidefinite if $A=A^T$ and $x^TAx\ge 0$ for every real vector $x$ of the appropriate dimension. Write $A\succeq 0$. It is positive definite, written $A\succ 0$, if $x^TAx>0$ for every nonzero $x$. For symmetric matrices $A$ and $B$ of the same size, define $A\preceq B$ to mean $B-A\succeq 0$, and write $B\succeq A$ equivalently.

The symmetry requirement is part of the definition: the Loewner order applies to symmetric matrices. It is reflexive and transitive, and if both $A\preceq B$ and $B\preceq A$, then $A=B$. But two symmetric matrices need not be comparable. In particular, $A\preceq B$ does not mean that each entry of $A$ is less than or equal to the corresponding entry of $B$.

Quadratic Forms and Eigenvalue Bounds

The defining condition gives an immediate way to interpret the order. For symmetric $A$ and $B$, the assertion $A\preceq B$ says that the quadratic form from $B$ is at least as large as the one from $A$, in every direction.

Theorem: For symmetric $A$ and $B$ of the same size, $A\preceq B$ if and only if $x^TAx\le x^TBx$ for every vector $x$.

Proof. By definition, $A\preceq B$ exactly when $B-A\succeq 0$. The latter means $x^T(B-A)x\ge 0$ for every $x$. Expanding this expression gives $x^TBx-x^TAx\ge 0$, which is the stated quadratic-form inequality. Each step is reversible, so the converse holds as well. $\square$

For a symmetric matrix $A$, denote its smallest and largest eigenvalues by $\lambda_{\min}(A)$ and $\lambda_{\max}(A)$. The spectral theorem gives the Rayleigh-quotient characterization: over unit vectors $x$, the minimum of $x^TAx$ is $\lambda_{\min}(A)$, and the maximum is $\lambda_{\max}(A)$. Thus the extreme eigenvalues give uniform bounds over all directions.

Theorem: If $A$ is symmetric, then $$ \lambda_{\min}(A)I\preceq A\preceq \lambda_{\max}(A)I. $$ If $A\preceq B$ for symmetric $A,B$, then $$ \lambda_{\min}(A)\le\lambda_{\min}(B) \quad\text{and}\quad \lambda_{\max}(A)\le\lambda_{\max}(B). $$

Proof. For any $x$, the Rayleigh-quotient bounds give $ \lambda_{\min}(A)\|x\|^2\le x^TAx\le\lambda_{\max}(A)\|x\|^2 $. Since $x^TIx=\|x\|^2$, the quadratic-form characterization proves the first pair of matrix inequalities.

Now suppose $A\preceq B$. For every unit vector $x$, $x^TAx\le x^TBx$. Taking maxima over unit vectors gives $\lambda_{\max}(A)\le\lambda_{\max}(B)$. For the minimum-eigenvalue inequality, choose a unit eigenvector $v$ of $B$ for $\lambda_{\min}(B)$. Then $\lambda_{\min}(A)\le v^TAv\le v^TBv=\lambda_{\min}(B)$. This proves both claims. $\square$

Worked Example: Checking an Order and Its Eigenvalue Bounds

Let $A=\begin{pmatrix}2&1\\1&2\end{pmatrix}$ and $B=3I$. Determine whether $A\preceq B$, then bound the quadratic form $x^TAx$.

Subtract the matrices: $B-A=\begin{pmatrix}1&-1\\-1&1\end{pmatrix}$. Its eigenvalues are $0$ and $2$, so it is positive semidefinite and $A\preceq B$. The eigenvalues of $A$ are $1$ and $3$, so the eigenvalue bounds also give $I\preceq A\preceq 3I$.

Consequently, for every $x\in\mathbb{R}^2$, $ \|x\|^2\le x^TAx\le3\|x\|^2 $. For $x=(1,2)^T$, $\|x\|^2=5$, $Ax=(4,5)^T$, and $x^TAx=1(4)+2(5)=14$. The bound checks numerically: $5\le14\le15$.

The order is only partial. For example, $A=\operatorname{diag}(2,1)$ and $B=\operatorname{diag}(1,2)$ are not ordered either way: $B-A=\operatorname{diag}(-1,1)$ and $A-B=\operatorname{diag}(1,-1)$ each have a negative eigenvalue. Neither difference is positive semidefinite.

Comparing Quadratic and Trace Objectives

For a fixed vector $x$, $A\preceq B$ directly compares the quadratic objectives $x^TAx$ and $x^TBx$. A related comparison applies to weighted trace objectives. If $C\succeq0$, then $A\preceq B$ implies $\operatorname{tr}(CA)\le\operatorname{tr}(CB)$. The weight $C$ can emphasize some directions more than others.

Theorem: If $A\preceq B$ and $C\succeq0$ are symmetric matrices of the same size, then $\operatorname{tr}(CA)\le\operatorname{tr}(CB)$.

Proof. The spectral theorem gives a symmetric positive-semidefinite square root $C^{1/2}$. Since $B-A\succeq0$, the matrix $C^{1/2}(B-A)C^{1/2}$ is positive semidefinite: for every $x$, $x^TC^{1/2}(B-A)C^{1/2}x=(C^{1/2}x)^T(B-A)(C^{1/2}x)\ge0$. A positive-semidefinite matrix has nonnegative eigenvalues and hence nonnegative trace. By the cyclic property of trace, $\operatorname{tr}(C^{1/2}(B-A)C^{1/2})=\operatorname{tr}(C(B-A))=\operatorname{tr}(CB)-\operatorname{tr}(CA)\ge0$. Rearranging proves the result. $\square$

Worked Example: Comparing Weighted Trace Values

Let $A=\begin{pmatrix}1&0\\0&2\end{pmatrix}$, $B=\begin{pmatrix}3&0\\0&4\end{pmatrix}$, and $C=\begin{pmatrix}2&0\\0&1\end{pmatrix}$. Verify the order and compare the weighted trace objectives.

The difference is $B-A=\begin{pmatrix}2&0\\0&2\end{pmatrix}=2I\succeq0$, so $A\preceq B$. Also $C\succeq0$, because its diagonal entries, and thus its eigenvalues, are $2$ and $1$.

Direct multiplication gives $CA=\begin{pmatrix}2&0\\0&2\end{pmatrix}$, so $\operatorname{tr}(CA)=4$. It gives $CB=\begin{pmatrix}6&0\\0&4\end{pmatrix}$, so $\operatorname{tr}(CB)=10$. The computed values satisfy $4\le10$, as the theorem predicts.

Matrix Bounds as Curvature Bounds

A twice-differentiable scalar function $f$ has a symmetric Hessian $\nabla^2 f(x)$. Its quadratic form in a direction $d$ gives the second derivative of $f$ along that direction. Therefore, matrix bounds on the Hessian give lower and upper bounds on directional curvature.

Theorem: Let $D$ be a convex open subset of $\mathbb{R}^p$, and let $f:D\to\mathbb{R}$ be twice continuously differentiable. Suppose that for all $z\in D$, $mI\preceq\nabla^2 f(z)\preceq MI$, where $m$ and $M$ are real constants. Then for all $x,y\in D$, $$ f(x)+\nabla f(x)^T(y-x)+\frac{m}{2}\|y-x\|^2 \le f(y)\le f(x)+\nabla f(x)^T(y-x)+\frac{M}{2}\|y-x\|^2. $$

Proof. Set $d=y-x$ and $g(t)=f(x+td)$ for $0\le t\le1$. Convexity of $D$ ensures the segment lies in $D$. The chain rule gives $g'(0)=\nabla f(x)^Td$ and $g''(t)=d^T\nabla^2f(x+td)d$. The assumed matrix bounds imply $m\|d\|^2\le g''(t)\le M\|d\|^2$. Twice applying the fundamental theorem of calculus gives $g(1)=g(0)+g'(0)+\int_0^1(1-t)g''(t)\,dt$. Since $\int_0^1(1-t)\,dt=1/2$, inserting the lower and upper bounds on $g''$ yields the two claimed inequalities. $\square$

Worked Example: Bounding the Curvature of a Quadratic

Consider $f(x)=\frac12x^THx+b^Tx$ on $\mathbb{R}^2$, where $H=\begin{pmatrix}4&1\\1&3\end{pmatrix}$ and $b=(1,-2)^T$. Establish usable lower and upper curvature bounds.

The Hessian is the constant matrix $H$. To show $2I\preceq H$, check $H-2I=\begin{pmatrix}2&1\\1&1\end{pmatrix}$. Its leading diagonal entry is $2>0$ and its determinant is $2(1)-1=1>0$, so it is positive definite. To show $H\preceq5I$, check $5I-H=\begin{pmatrix}1&-1\\-1&2\end{pmatrix}$. Its leading diagonal entry is $1>0$ and its determinant is $2-1=1>0$, so it too is positive definite. Thus $2I\preceq H\preceq5I$.

For every direction $d$, the second directional derivative is $d^THd$, and the matrix bounds give $2\|d\|^2\le d^THd\le5\|d\|^2$. In fact, for any $x,y$, the quadratic expansion is exact: $f(y)=f(x)+\nabla f(x)^T(y-x)+\frac12(y-x)^TH(y-x)$. Therefore its final term lies between $\|y-x\|^2$ and $\frac52\|y-x\|^2$. The linear term $b^Tx$ changes the gradient but not the curvature, since its Hessian is zero.

Common Mistakes and Practical Use

Positive-semidefinite order is useful whenever an argument needs to hold in every direction, rather than for one chosen vector. Eigenvalue bounds can turn a matrix comparison into a scalar bound on the size of a quadratic objective. Hessian bounds similarly quantify how rapidly a function can curve, which is useful for understanding objective behavior and for controlling approximations.

Comparing entries instead of quadratic forms. Entrywise inequalities do not define the Loewner order. Check whether the difference $B-A$ is positive semidefinite.
Assuming every pair is ordered. The order is partial. Two matrices can have differences that are both indefinite, as the diagonal example above shows.
Forgetting symmetry. The Loewner order is defined for symmetric matrices; positive semidefiniteness is not an entrywise property of an arbitrary matrix.
Using a trace comparison with an indefinite weight. The theorem requires $C\succeq0$. Without that condition, the trace inequality need not hold.
Confusing semidefinite with definite. A zero eigenvalue is allowed for positive semidefiniteness, but not for positive definiteness. For example, $2I\preceq H$ gives a strict positive lower curvature bound here because $2>0$.

Key takeaway: Read $A\preceq B$ as “$B$ has at least as large a quadratic form as $A$ in every direction.” That single interpretation supports eigenvalue bounds, objective comparisons, and quantitative curvature statements.

Check Your Understanding

Use the quadratic-form interpretation of the order to answer these questions.

What condition on $B-A$ defines $A\preceq B$, and how does that condition compare $x^TAx$ and $x^TBx$?
If $A\preceq B$, what inequalities follow for their smallest and largest eigenvalues?
Why does $A\preceq B$ and $C\succeq0$ imply $\operatorname{tr}(CA)\le\operatorname{tr}(CB)$?
What do the bounds $mI\preceq\nabla^2f(z)\preceq MI$ imply about the second derivative along a direction $d$?
Can two symmetric matrices be incomparable in Loewner order? Give the criterion for checking a proposed order.