📂Optimization

Second Order Necessary/Sufficient Conditions for the Extreme Values of Multivariable Functions

Theorem¹

Let’s say the function $f : \mathbb{R}^{n} \to \mathbb{R}$ is given. $\nabla f$, $\nabla^{2}f$ are the gradient and Hessian of $f$, respectively.

• Second-order necessary conditions

  If $x^{\ast}$ is a local optimizer and $\nabla^{2}f$ exists and is continuous in the neighborhood of $x^{\ast}$,

  $$\nabla f(x^{\ast}) = 0$$

  and $\nabla^{2} f(x^{\ast})$ is positive semidefinite.

  Note that $0$ is not the number zero, but the zero vector.

• Second-order sufficient conditions

  In the neighborhood of $x^{\ast}$, if $\nabla^{2}f$ is continuous, $\nabla f (x^{\ast}) = 0$, and $\nabla f(x^{\ast})$ is positive definite, then $x^{\ast}$ is a strict local optimizer.

Explanation

The necessary condition talks about the properties of $f$ when $x^{\ast}$ is an extremum. The sufficient condition discusses whether $x^{\ast}$ is an extremum based on certain properties of $f$.

Proof

Second-order necessary conditions

It is true that $\nabla f(x^{\ast})$ holds by the first-order necessary conditions.

The rest of the proof is by contradiction. Assume that $\nabla^{2} f(x^{\ast})$ is not positive semidefinite. Then, choose some vector $p$ that satisfies $p^{t} \nabla^{2}f(x^{\ast}) p \lt 0$. Here, $p^{t}$ is the transpose matrix. Thus, since $\nabla^{2}f$ is continuous near $x^{\ast}$, for some $s \gt 0$, the following holds.

$$\begin{equation} p^{t} \nabla^{2}f(x^{\ast} + \xi p) p \lt 0,\quad \forall \xi \in [0, s] \end{equation}$$

Also, by the Taylor expansion formula for multivariable functions,

$$\begin{equation} f(x^{\ast} + \xi p) = f (x^{\ast}) + \xi p^{t} \nabla f(x^{\ast}) + \dfrac{1}{2}\xi^{2} p^{t} \nabla^{2} f(x^{\ast} + \bar{\xi} p)p,\quad \text{for some } \bar{\xi} \in (0, \xi) \end{equation}$$

Then, since $\nabla f(x^{\ast}) = 0$, by $(1)$ and $(2)$, we get the following.

$$f(x^{\ast} + \xi p) \lt f (x^{\ast}), \qquad \forall \xi \in [0, s]$$

This contradicts the fact that $x^{\ast}$ is a local minimizer. Therefore, the assumption is wrong, and $\nabla^{2} f (x^{\ast})$ is a positive semidefinite matrix.

■

Second-order sufficient conditions

Since the Hessian $\nabla^{2}f$ at $x^{\ast}$ is continuous and positive definite, an open ball $B_{r} = \left\{ x : \left\| x - x^{\ast} \right\| \lt r \right\}$ can be selected so that $\nabla^{2}f (x)$ is positive definite for all $x \in B$.

$$p^{t}\nabla^{2} f(x) p \gt 0,\quad \forall p \in \mathbb{R}^{n}$$

Now, for some vector $p$ that is not $0$ and satisfies $\left\| p \right\| \lt r$, by the Taylor expansion formula for multivariable functions, we get the following.

$$\begin{align*} f(x^{\ast} + p) &= f(x^{\ast}) + p^{t}\nabla f(x^{\ast}) + \dfrac{1}{2}p^{t} \nabla^{2} f(x + \xi p) p,\quad \xi \in (0, 1) \\ &= f(x^{\ast}) + \dfrac{1}{2}p^{t} \nabla^{2} f(x + \xi p) p \end{align*}$$

Here, since $x^{\ast} + \xi p \in B$,

$$f(x^{\ast} + p) \gt f(x^{\ast})$$

Therefore, $x^{\ast}$ is a local minimizer.

■

See also

• First-order necessary conditions