Proof of First- and Second-Order Conditions at a Local Extremum of a Function of Class $C^2$

Notation. For $y,h\in\mathbb{R}^n$ write $y+h$ for the point of $\mathbb{R}^n$ whose $i$th coordinate is $y_i+h_i$; this is the coordinatewise addition used in Second-Order Taylor Expansion with Peano Remainder. For $t\in\mathbb{R}$ and $z\in\mathbb{R}^n$ write $tz$ for the point whose $i$th coordinate is $tz_i$, and write $-z$ for $(-1)z$. For $y\in\mathbb{R}^n$ write $\lVert y\rVert=d_E(y,0_{\mathbb{R}^n})$, as in Second-Order Taylor Expansion with Peano Remainder. Write $t^2$ for $t\cdot t$.

Using the partial derivative notation and the second-order notation of C^2 Real-Valued Map on an Open Subset of Euclidean Space, set

$$\alpha_i=\frac{\partial w}{\partial x_i}(x),\qquad \beta_{ij}=\frac{\partial^2 w}{\partial x_i\,\partial x_j}(x)\qquad (i,j\in\{1,\dots,n\}),$$

and for $z=(z_1,\dots,z_n)\in\mathbb{R}^n$ set

$$L(z)=\sum_{i=1}^n \alpha_i z_i,\qquad Q(z)=2^{-1}\sum_{i=1}^n\sum_{j=1}^n \beta_{ij}z_iz_j .$$

By the definition of the gradient and the definition of the dot product, $L(z)=Dw(x)\cdot z$. By the definition of the Hessian matrix, the definition of the matrix-vector product and the definition of the dot product,

$$z\cdot\bigl(D^2w(x)z\bigr)=\sum_{i=1}^n z_i\sum_{j=1}^n \beta_{ij}z_j=\sum_{i=1}^n\sum_{j=1}^n \beta_{ij}z_iz_j,$$

so $Q(z)=2^{-1}\,z\cdot(D^2w(x)z)$. By distributivity in the field $\mathbb{R}$ we have, for all $t\in\mathbb{R}$ and $z\in\mathbb{R}^n$,

$$L(tz)=tL(z),\qquad Q(tz)=t^2Q(z),$$

and in particular $L(-z)=-L(z)$; also $L(0_{\mathbb{R}^n})=0$ and $Q(0_{\mathbb{R}^n})=0$.

Step 0 (elementary facts). References to numbered claims below are to Elementary Order Arithmetic in an Ordered Field unless another item is named.

(a) For every $y\in\mathbb{R}^n$, $0\le\lVert y\rVert$ and $\lVert y\rVert^2=\sum_{i=1}^n y_i^2$. Indeed, by the definition of the Euclidean distance, $\lVert y\rVert$ is the nonnegative square root of $\sum_{i=1}^n (y_i-0)^2=\sum_{i=1}^n y_i^2$, so this holds by Existence and Uniqueness of the Nonnegative Square Root.

(b) For all $y,h\in\mathbb{R}^n$, $d_E(y,y+h)=\lVert h\rVert$. Indeed $(y_i-(y_i+h_i))^2=(-h_i)\cdot(-h_i)=h_i^2$ for every $i$, so both sides are the nonnegative square root of $\sum_{i=1}^n h_i^2$.

(c) If $z\ne 0_{\mathbb{R}^n}$ then $0<\lVert z\rVert$ and $0<\lVert z\rVert^2$. Indeed $d_E$ is a metric by Euclidean Distance is a Metric on $\mathbb{R}^n$, so by the definition of a metric space $\lVert z\rVert=d_E(z,0_{\mathbb{R}^n})=0$ would force $z=0_{\mathbb{R}^n}$; with (a) this gives $0<\lVert z\rVert$, and then $0<\lVert z\rVert\cdot\lVert z\rVert=\lVert z\rVert^2$ by claim 5.

(d) If $0<t$ and $z\in\mathbb{R}^n$ then $\lVert tz\rVert=t\lVert z\rVert$. Indeed by (a) and field arithmetic $\lVert tz\rVert^2=\sum_{i=1}^n (tz_i)^2=t^2\sum_{i=1}^n z_i^2=t^2\lVert z\rVert^2=(t\lVert z\rVert)^2$. Both $\lVert tz\rVert$ and $t\lVert z\rVert$ are nonnegative: the first by (a), and for the second, either $\lVert z\rVert=0$ and then $t\lVert z\rVert=0$, or $0<\lVert z\rVert$ and then $0<t\lVert z\rVert$ by claim 5. Claim 3 of Monotonicity of Squaring on the Nonnegative Elements of an Ordered Field now gives the asserted equality.

(e) If $p\le q$ and $0<c$ then $cp\le cq$. Indeed, if $p=q$ this is an equality, and if $p<q$ then $cp<cq$ by claim 10.

(f) If $p\le q$ and $r\le s$ then $p+r\le q+s$. This follows from the compatibility of $\le$ with addition in an ordered field, which gives $p+r\le q+r$ and $q+r\le q+s$, together with transitivity of $\le$.

Step 1 (the basic inequality). Assume that $w$ has a local maximum at $x$ relative to $U$. Then for every $\varepsilon\in\mathbb{R}$ with $0<\varepsilon$ and every $z\in\mathbb{R}^n$ with $z\ne 0_{\mathbb{R}^n}$ there is $\tau\in\mathbb{R}$ with $0<\tau$ such that

$$L(z)+tQ(z)\le \varepsilon\, t\,\lVert z\rVert^2\qquad\text{for every } t\in\mathbb{R}\text{ with } 0<t<\tau .$$

By the definition of a local maximum relative to $U$ there is $\delta_1\in\mathbb{R}$ with $0<\delta_1$ such that every $y\in U$ with $d_E(x,y)<\delta_1$ satisfies $w(y)\le w(x)$. Let $\varepsilon$ be given with $0<\varepsilon$. By Second-Order Taylor Expansion with Peano Remainder, applied to $w$ at $x$, there is $\delta_2\in\mathbb{R}$ with $0<\delta_2$ such that every $h\in\mathbb{R}^n$ with $\lVert h\rVert<\delta_2$ satisfies $x+h\in U$ and

$$\bigl|\,w(x+h)-w(x)-L(h)-Q(h)\,\bigr|\le\varepsilon\lVert h\rVert^2,$$

where $|\cdot|$ is the absolute value on $\mathbb{R}$; the two sums appearing in that theorem are exactly $L(h)$ and $Q(h)$. By claim 9 let $\delta_3$ be the smaller of $\delta_1$ and $\delta_2$, so $0<\delta_3$.

Let $z\ne 0_{\mathbb{R}^n}$. By (c), $0<\lVert z\rVert$, so by claim 7 the inverse $\lVert z\rVert^{-1}$ exists and is positive, and by claim 5 the element $\tau=\delta_3\lVert z\rVert^{-1}$ satisfies $0<\tau$. Let $t\in\mathbb{R}$ with $0<t<\tau$ and put $h=tz$. By claim 10, $\lVert z\rVert t<\lVert z\rVert\delta_3\lVert z\rVert^{-1}=\delta_3$, so by (d) we get $\lVert h\rVert=t\lVert z\rVert<\delta_3$, whence $\lVert h\rVert<\delta_1$ and $\lVert h\rVert<\delta_2$ by claim 2.

Since $\lVert h\rVert<\delta_2$, we have $x+h\in U$ and the displayed Taylor estimate holds for this $h$. Since $d_E(x,x+h)=\lVert h\rVert<\delta_1$ by (b), the choice of $\delta_1$ gives $w(x+h)\le w(x)$, hence $w(x+h)-w(x)\le 0$ by claim 1.

Put $R=w(x+h)-w(x)-L(h)-Q(h)$. From $|R|\le\varepsilon\lVert h\rVert^2$ and claim 6 of Properties of the Absolute Value in an Ordered Field we get $-\varepsilon\lVert h\rVert^2\le R$, hence $-R\le\varepsilon\lVert h\rVert^2$ by claim 4. Since $L(h)+Q(h)=\bigl(w(x+h)-w(x)\bigr)+(-R)$, (f) gives

$$L(h)+Q(h)\le 0+\varepsilon\lVert h\rVert^2=\varepsilon\lVert h\rVert^2 .$$

By (d) and (a), $\lVert h\rVert^2=(t\lVert z\rVert)^2=t^2\lVert z\rVert^2$, while $L(h)=tL(z)$ and $Q(h)=t^2Q(z)$. Thus

$$tL(z)+t^2Q(z)\le \varepsilon\,t^2\lVert z\rVert^2 .$$

Since $0<t$, claim 7 gives $0<t^{-1}$, so multiplying by $t^{-1}$ and simplifying by field arithmetic, using (e), yields $L(z)+tQ(z)\le\varepsilon\,t\,\lVert z\rVert^2$. This proves Step 1.

Step 2 (the gradient vanishes). Keep the hypothesis of claim 1 and let $z\ne 0_{\mathbb{R}^n}$. Apply Step 1 with $\varepsilon=1$, which is admissible since $0<1$ by claim 6, and let $\tau$ be as there. Adding $-tQ(z)$ to both sides of the inequality of Step 1 (compatibility of $\le$ with addition in an ordered field) gives

$$L(z)\le t\,\bigl(\lVert z\rVert^2-Q(z)\bigr)\qquad\text{for every } t\text{ with } 0<t<\tau .$$

Write $M=\lVert z\rVert^2-Q(z)$ and suppose, for contradiction, that $0<L(z)$.

If $M\le 0$, take $t=\tau\cdot 2^{-1}$, which satisfies $0<t<\tau$ by claim 8. Then $tM\le t\cdot 0=0$ by (e), so $L(z)\le 0$ by transitivity of $\le$, contradicting $0<L(z)$.

If $0<M$, then $M^{-1}$ exists and $0<M^{-1}$ by claim 7, and $0<L(z)M^{-1}\cdot 2^{-1}$ by claims 5 and 8. By claim 9 let $t$ be the smaller of $\tau\cdot 2^{-1}$ and $L(z)M^{-1}\cdot 2^{-1}$; then $0<t$ and $t\le\tau\cdot 2^{-1}<\tau$, so $t$ is admissible by claim 2. By (e), $tM\le L(z)M^{-1}\cdot 2^{-1}\cdot M=L(z)\cdot 2^{-1}$, and $L(z)\cdot 2^{-1}<L(z)$ by claim 8. Hence $L(z)\le tM\le L(z)\cdot2^{-1}<L(z)$, so $L(z)<L(z)$ by claim 2, which is impossible.

Therefore $L(z)\le 0$ for every $z\ne 0_{\mathbb{R}^n}$; and $L(0_{\mathbb{R}^n})=0\le 0$. So $L(z)\le0$ for every $z\in\mathbb{R}^n$. Applying this to $-z$ and using $L(-z)=-L(z)$ gives $-L(z)\le 0$, hence $0\le L(z)$ by claim 4. Since $\le$ is a total order and therefore antisymmetric, $L(z)=0$ for every $z\in\mathbb{R}^n$.

For $i\in\{1,\dots,n\}$ let $e_i\in\mathbb{R}^n$ be the point whose $i$th coordinate is $1$ and whose other coordinates are $0$. Then $L(e_i)=\alpha_i$, so $\alpha_i=0$. By the definition of the gradient, $Dw(x)=(\alpha_1,\dots,\alpha_n)=0_{\mathbb{R}^n}$.

Step 3 (the Hessian is negative semidefinite). Keep the hypothesis of claim 1, let $z\ne 0_{\mathbb{R}^n}$ and let $\varepsilon\in\mathbb{R}$ with $0<\varepsilon$. Let $\tau$ be as in Step 1 for this $\varepsilon$ and $z$, and take $t=\tau\cdot 2^{-1}$, so $0<t<\tau$ by claim 8. By Step 2 we have $L(z)=0$, so Step 1 gives $tQ(z)\le\varepsilon\,t\,\lVert z\rVert^2$. Multiplying by $t^{-1}$, which is positive by claim 7, and using (e) and field arithmetic, we get

$$Q(z)\le\varepsilon\lVert z\rVert^2 .$$

Suppose, for contradiction, that $0<Q(z)$. By (c), $0<\lVert z\rVert^2$, so $(\lVert z\rVert^2)^{-1}$ exists and is positive by claim 7, and $\varepsilon_0=Q(z)\,(\lVert z\rVert^2)^{-1}\cdot 2^{-1}$ satisfies $0<\varepsilon_0$ by claims 5 and 8. Applying the previous inequality with $\varepsilon_0$ in place of $\varepsilon$ gives $Q(z)\le Q(z)\cdot 2^{-1}$, while $Q(z)\cdot2^{-1}<Q(z)$ by claim 8; by claim 2 this yields $Q(z)<Q(z)$, which is impossible. Hence $Q(z)\le 0$ for every $z\ne0_{\mathbb{R}^n}$, and $Q(0_{\mathbb{R}^n})=0\le0$, so $Q(z)\le0$ for every $z\in\mathbb{R}^n$.

Since $Q(z)=2^{-1}\,z\cdot(D^2w(x)z)$ and $0<2$ by claim 8, multiplying by $2$ and using (e) gives $z\cdot(D^2w(x)z)\le 0$ for every $z\in\mathbb{R}^n$. By the definition of the matrix-vector product, $(0_nz)_i=\sum_{j=1}^n 0\cdot z_j=0$ for every $i$, so $0_nz=0_{\mathbb{R}^n}$ and, by the definition of the dot product, $z\cdot(0_nz)=0$. Hence $z\cdot(D^2w(x)z)\le z\cdot(0_nz)$ for every $z\in\mathbb{R}^n$, which by the definition of the positive semidefinite ordering says $D^2w(x)\preceq 0_n$. Together with Step 2 this proves claim 1.

Step 4 (the local minimum case). Assume now that $w$ has a local minimum at $x$ relative to $U$. Let $k_0:U\to\mathbb{R}$ be the function with constant value $0$. By claim 2 of Differences and Constants for Functions of Class $C^2$ on a Euclidean Open Set, $k_0$ is of class $C^2$ on $U$ with $Dk_0(y)=0_{\mathbb{R}^n}$ and $D^2k_0(y)=0_n$ for every $y\in U$. By claim 1 of that lemma the function $v=k_0-w$, whose value at $y\in U$ is $0-w(y)=-w(y)$, is of class $C^2$ on $U$, and for every $y\in U$

$$Dv(y)=0_{\mathbb{R}^n}-Dw(y),\qquad D^2v(y)=0_n-D^2w(y).$$

By the definition of a local minimum relative to $U$ there is $\delta\in\mathbb{R}$ with $0<\delta$ such that every $y\in U$ with $d_E(x,y)<\delta$ satisfies $w(x)\le w(y)$; by claim 4 this gives $-w(y)\le -w(x)$, that is, $v(y)\le v(x)$. Hence $v$ has a local maximum at $x$ relative to $U$.

Applying claim 1, already proved, to $v$ in place of $w$ gives $Dv(x)=0_{\mathbb{R}^n}$ and $D^2v(x)\preceq 0_n$. By the definition of the difference of points of $\mathbb{R}^n$, the $i$th coordinate of $Dv(x)$ is $0-\partial w/\partial x_i(x)$; since it is $0$, we get $\partial w/\partial x_i(x)=0$ for every $i$, and hence $Dw(x)=0_{\mathbb{R}^n}$ by the definition of the gradient.

By the definition of the difference of real matrices, $(D^2v(x))_{ij}=0-(D^2w(x))_{ij}$, so by the definitions of the matrix-vector product and of the dot product, together with distributivity in $\mathbb{R}$,

$$z\cdot\bigl(D^2v(x)z\bigr)=-\bigl(z\cdot(D^2w(x)z)\bigr)\qquad\text{for every } z\in\mathbb{R}^n .$$

Since $D^2v(x)\preceq 0_n$ and $z\cdot(0_nz)=0$, this gives $-\bigl(z\cdot(D^2w(x)z)\bigr)\le 0$, hence $0\le z\cdot(D^2w(x)z)$ by claim 4, that is, $z\cdot(0_nz)\le z\cdot(D^2w(x)z)$ for every $z\in\mathbb{R}^n$. By the definition of the positive semidefinite ordering, $0_n\preceq D^2w(x)$. This proves claim 2.