Existence of a Minimum

Understanding when a function reaches a minimum at a given point is crucial in optimization. These conditions are divided into necessary and sufficient conditions, classified based on the first-order and second-order derivatives of the function.

First-Order Necessary Condition (FONC)

If a function $f$ is continuously differentiable and has a local minimum at $x^{*}$ , then its gradient must satisfy:

d^{T} \nabla f (x^{*}) \geq 0

for any feasible (possible) direction $d$ at $x^{*}$ . This condition ensures that the function does not decrease in any feasible direction.

Special Case: Interior Minimum

If $x^{*}$ is an interior point of the domain $Ω$ , then the condition simplifies to:

\nabla f (x^{*}) = 0

This means that at a local minimum in an unconstrained setting, the gradient must be zero.

Second-Order Necessary Condition (SONC)

If $f$ is twice continuously differentiable and $x^{*}$ is a local minimizer, then:

The first-order condition holds: $d^{T} \nabla f (x^{*}) = 0$
The Hessian (second derivative test) must be positive semidefinite: $d^{T} H_{f} (x^{*}) d \geq 0$

where $H_{f} (x^{*})$ is the Hessian matrix of $f$ . This ensures that the function is not curving downward in any feasible direction at $x^{*}$ .

Special Case: Interior Minimum

If $x^{*}$ is an interior point, then:

The gradient must be zero: $\nabla f (x^{*}) = 0$
The Hessian must be positive semidefinite: $d^{T} H_{f} (x^{*}) d \geq 0 \forall d \in R^{n} .$

This means the function curves upward or remains flat in all directions at $x^{*}$ .

Second-Order Sufficient Condition (SOSC). Interior Case

For $x^{*}$ to be a strict local minimizer, a stronger condition must hold:

Gradient is zero: $\nabla f (x^{*}) = 0$
Hessian is positive definite: $H_{f} (x^{*}) > 0.$

This ensures that the function strictly curves upwards, confirming $x^{*}$ as a strict local minimum.

Examples and Counterexamples

$f (x) = x^{3}$ at $x = 0$

Satisfies FONC and SONC, but is not a minimum!

FONC and SONC 1.png

$f (x_{1}, x_{2}) = x_{1}^{2} - x_{2}^{2}$ at $(0, 0)$

Satisfies FONC but not SONC, meaning $(0, 0)$ is not a minimum!

FONC and SONC 2.png

$f (x_{1}, x_{2}) = x_{1}^{2} + x_{2}^{2}$ at $(0, 0)$

Satisfies FONC and SOSC, making $(0, 0)$ a strict local minimum!

Summary

Condition	Formula	Interpretation
FONC (First-order necessary)	$d^{T} \nabla f (x^{*}) \geq 0$	Ensures no descent direction at $x^{*}$ .
SONC (Second-order necessary)	$d^{T} H_{f} (x^{*}) d \geq 0$	Ensures function is not curving downward.
SOSC (Second-order sufficient)	$H_{f} (x^{*}) > 0$	Ensures strict local minimum.

These conditions form the foundation of optimization theory, guiding both theoretical analysis and practical algorithms. 🚀