First- and Second-Order Conditions for Matrix Objectives

Why First- and Second-Order Conditions Matter

Matrix objectives often depend on many entries at once, but their local behavior can be examined by perturbing the entire matrix in a direction. The gradient describes the first-order change. If that change vanishes in every direction, the Hessian describes the leading possible change. These facts yield useful tests for local optima, provided we distinguish what a test requires from what it actually guarantees.

This tutorial considers an unconstrained scalar objective on a matrix space. The conditions below concern local optima in the full space, not optima restricted to a constraint set. In particular, they apply at an interior point of the objective's domain; equality and inequality constraints require additional conditions.

Gradients, Hessians, and Directional Changes

Let $\mathcal{D}$ be an open subset of $\mathbb{R}^{m\times n}$, and let $f:\mathcal{D}\to\mathbb{R}$. We use the Frobenius inner product $\langle A,B\rangle_F=\operatorname{tr}(A^{\mathsf T}B)$. A perturbation $\Delta\in\mathbb{R}^{m\times n}$ points from $X$ to a nearby matrix $X+\Delta$.

Definition: If $f$ is differentiable at $X$, its matrix gradient $\nabla f(X)$ is the unique matrix satisfying $$ df(X)[\Delta]=\langle \nabla f(X),\Delta\rangle_F $$ for every perturbation $\Delta$. If $f$ is twice continuously differentiable, its second differential $d^2f(X)[\Delta,\Delta]$ is a quadratic form in $\Delta$. Equivalently, there is a linear operator $\mathcal{H}_X$ such that $$ d^2f(X)[\Delta,\Delta]=\langle \Delta,\mathcal{H}_X[\Delta]\rangle_F. $$ This quadratic form is the Hessian form of $f$ at $X$.

With a fixed orthonormal basis for the matrix space, the gradient can be represented as a vector and the Hessian form by a symmetric matrix. The quadratic form does not depend on which orthonormal basis is used. The second-order Taylor expansion, for $f$ twice continuously differentiable near $X$, is

f(X+\Delta)=f(X)+\langle \nabla f(X),\Delta\rangle_F +\frac{1}{2}\langle \Delta,\mathcal{H}_X[\Delta]\rangle_F +o(\|\Delta\|_F^2) \quad\text{as }\|\Delta\|_F\to 0.

The final term is a remainder whose ratio to $\|\Delta\|_F^2$ tends to zero. This expansion explains the sequence of tests: first ask whether the linear term vanishes in all directions, then inspect the sign of the quadratic term.

Worked Example: A Quadratic With a Unique Minimum

Let $B\in\mathbb{R}^{m\times n}$ be fixed and define $f(X)=\frac{1}{2}\|X-B\|_F^2$. Find and classify its stationary point.

For any perturbation $\Delta$, $$ f(X+t\Delta)=\frac{1}{2}\|X-B+t\Delta\|_F^2 =f(X)+t\langle X-B,\Delta\rangle_F+\frac{t^2}{2}\|\Delta\|_F^2. $$ Thus $\nabla f(X)=X-B$, and the Hessian form is $d^2f(X)[\Delta,\Delta]=\|\Delta\|_F^2$.

Stationarity requires $X-B=0$, so the only stationary point is $X=B$. For every nonzero $\Delta$, the Hessian form is strictly positive. Indeed, $$ f(B+\Delta)-f(B)=\frac{1}{2}\|\Delta\|_F^2>0. $$ Therefore $B$ is a strict local minimum, and the displayed identity also verifies that it is the unique global minimum.

First-Order Condition: Stationarity

A local minimum at an interior point cannot have a direction in which the objective initially decreases. Since both positive and negative small steps along any direction remain in the open domain, this forces the directional derivative to vanish in every direction.

Theorem: Suppose $f$ is differentiable on an open set $\mathcal{D}\subseteq\mathbb{R}^{m\times n}$. If $X_*\in\mathcal{D}$ is a local minimum or local maximum of $f$, then $$ \nabla f(X_*)=0. $$ This is a necessary condition, not in general a sufficient one.

To prove the claim, suppose instead that $\nabla f(X_*)\ne 0$. Choose the direction $\Delta=-\nabla f(X_*)$. The directional derivative at $X_*$ is $$ df(X_*)[\Delta]=\langle \nabla f(X_*),-\nabla f(X_*)\rangle_F =-\|\nabla f(X_*)\|_F^2<0. $$ By differentiability, for all sufficiently small positive $t$, $f(X_*+t\Delta)<f(X_*)$. This contradicts a local minimum. For a local maximum, use $\Delta=\nabla f(X_*)$, which gives a strictly positive directional derivative and the corresponding contradiction. Hence the gradient must be zero. $\square$

Worked Example: An Interior Point That Is Not Stationary

For $X\in\mathbb{R}^{2\times 2}$, let $f(X)=\|X\|_F^2-2X_{11}$. Determine whether the zero matrix can be a local optimum.

The differential is $df(X)[\Delta]=2\langle X,\Delta\rangle_F-2\Delta_{11}$, so the gradient is $2X-2E_{11}$, where $E_{11}$ has a 1 in its upper-left entry and zeros elsewhere. At $X=0$, the gradient is $-2E_{11}\ne 0$; the first-order condition rules out a local optimum.

Directly, take $\Delta=E_{11}$. For $t>0$, $f(tE_{11})=t^2-2t<0=f(0)$ whenever $0<t<2$. In the opposite direction, $f(-tE_{11})=t^2+2t>0$. Thus arbitrarily close values are both below and above $f(0)$.

Second-Order Conditions at a Stationary Point

At a stationary point the first-order term disappears. For a twice continuously differentiable objective, a negative second-order change in any direction would then contradict local minimality. The result is a necessary semidefinite condition.

Theorem: Suppose $f$ is twice continuously differentiable on an open set $\mathcal{D}\subseteq\mathbb{R}^{m\times n}$, and $X_*\in\mathcal{D}$ is a local minimum. Then $$ \langle \Delta,\mathcal{H}_{X_*}[\Delta]\rangle_F\ge 0 \quad\text{for every }\Delta\in\mathbb{R}^{m\times n}. $$ That is, the Hessian form is positive semidefinite. At a local maximum it is negative semidefinite.

For the minimum case, stationarity has already established that $\nabla f(X_*)=0$. Fix any direction $\Delta$ and consider the one-variable function $g(t)=f(X_*+t\Delta)$, which is defined for all sufficiently small $t$ because $\mathcal{D}$ is open. Its second-order expansion is $$ g(t)-g(0)=\frac{t^2}{2}\langle\Delta,\mathcal{H}_{X_*}[\Delta]\rangle_F+o(t^2). $$ If the Hessian form were negative for this $\Delta$, the remainder divided by $t^2$ would tend to zero, so $g(t)-g(0)<0$ for sufficiently small nonzero $t$. That contradicts a local minimum. The form must therefore be nonnegative in every direction. For a maximum, applying the same argument to $-f$ gives a negative-semidefinite Hessian. $\square$

Positive semidefiniteness is not, by itself, enough to establish a minimum. When the Hessian is positive definite, however, it does give a sufficient condition for a strict local minimum.

Theorem: Suppose $f$ is twice continuously differentiable on an open set containing $X_*$, $\nabla f(X_*)=0$, and $$ \langle\Delta,\mathcal{H}_{X_*}[\Delta]\rangle_F>0 \quad\text{for every nonzero }\Delta. $$ Then $X_*$ is a strict local minimum.

For a complete justification, the unit sphere of matrix perturbations is compact. The continuous Hessian form therefore has a minimum there; positive definiteness means this minimum is some $\lambda>0$. By scaling, for every $\Delta$, $$ \langle\Delta,\mathcal{H}_{X_*}[\Delta]\rangle_F\ge \lambda\|\Delta\|_F^2. $$ The Taylor remainder is $o(\|\Delta\|_F^2)$, so for all sufficiently small $\Delta$ its absolute value is at most $\frac{\lambda}{4}\|\Delta\|_F^2$. Using stationarity in the expansion gives $$ f(X_*+\Delta)-f(X_*)\ge \frac{\lambda}{2}\|\Delta\|_F^2-\frac{\lambda}{4}\|\Delta\|_F^2 =\frac{\lambda}{4}\|\Delta\|_F^2>0 $$ for every sufficiently small nonzero $\Delta$. This is precisely a strict local minimum. Reversing the signs gives the corresponding sufficient condition for a strict local maximum. $\square$

Worked Example: An Indefinite Hessian Gives a Saddle

Write $X=[a\ b]\in\mathbb{R}^{1\times 2}$, and let $f(X)=a^2-b^2$. At $X=0$, the gradient is zero. In the coordinates $(a,b)$, the Hessian is $$ \begin{pmatrix}2&0\\0&-2\end{pmatrix}. $$ Its quadratic form on a perturbation $\Delta=[u\ v]$ is $2u^2-2v^2$, which is positive for $[1\ 0]$ and negative for $[0\ 1]$.

The two paths verify the consequence directly: $f([t\ 0])=t^2>0$ and $f([0\ t])=-t^2<0$ for every $t\ne 0$. Thus every neighborhood of zero contains points with both higher and lower objective values. The stationary point is a saddle, not a local minimum or maximum.

Worked Example: A Semidefinite Hessian Is Inconclusive

For $X\in\mathbb{R}^{2\times 2}$, consider $$ f(X)=X_{11}^3+X_{12}^2+X_{21}^2+X_{22}^2. $$ At the zero matrix the gradient is zero. In the coordinate order $(X_{11},X_{12},X_{21},X_{22})$, the Hessian there is $\operatorname{diag}(0,2,2,2)$, which is positive semidefinite but not positive definite.

Along $\Delta=tE_{11}$, $f(\Delta)=t^3$. This is positive for $t>0$ and negative for $t<0$, with both signs occurring arbitrarily close to zero. Therefore zero is neither a local minimum nor a local maximum. The necessary semidefinite test holds, but does not settle the classification.

Using the Conditions Correctly

The practical distinction is between necessary and sufficient conditions. At an unconstrained interior local minimum, the gradient must vanish and the Hessian must be positive semidefinite. These tests can rule out a minimum when either condition fails. A positive-definite Hessian at a stationary point establishes a strict local minimum. A merely positive-semidefinite Hessian leaves the question open: higher-order terms may produce a minimum, a maximum, or neither.

Nonzero gradient: the point cannot be an interior local minimum or maximum.
Zero gradient and an indefinite Hessian: the point is neither a local minimum nor a local maximum.
Zero gradient and a positive-definite Hessian: the point is a strict local minimum.
Zero gradient and a positive-semidefinite, non-definite Hessian: the second-order test is inconclusive.

A frequent error is to call every stationary point with a positive-semidefinite Hessian a minimum. The cubic example shows why that reasoning fails: along a direction where the quadratic term is zero, a higher-order term can change sign. A second common error is to apply the unconstrained gradient condition to a point on a constraint set. The proof of stationarity used perturbations in every direction, which may not be feasible under constraints. These conditions are for the full open matrix domain; constrained optimization requires accounting for the feasible directions.

Key takeaway: First check stationarity. At a stationary point, a negative Hessian direction rules out a local minimum, while positive definiteness guarantees a strict one. Positive semidefiniteness is necessary at a local minimum but is not, on its own, a proof of one.

Check Your Understanding

Use the distinction between necessary and sufficient conditions to answer these questions.

Why must the gradient vanish at an unconstrained local minimum in an open matrix domain?
What Hessian condition is necessary at a twice-differentiable local minimum?
A stationary point has a positive-definite Hessian form. What does this imply, and why?
Can a stationary point with a positive-semidefinite Hessian fail to be a local minimum? Explain using a direction or an example.
Why do the unconstrained first-order conditions not directly apply at an equality-constrained optimum?