09. Optimality Conditions — Identifying Where to Stop

// CORE 3/7 — first-order condition, second-order condition, positive definiteness

Optimization algorithms move iteratively. When should they stop? Optimality conditions are criteria for judging whether "this point can be a minimum."

First-order condition

Consider an unconstrained smooth problem:

$$\min_x f(x).$$

If a point $x^\ast$ is a local minimum, its gradient must be zero:

$$\nabla f(x^\ast)=0.$$

This condition is necessary because, if the gradient is nonzero, moving slightly in the opposite direction can reduce the value.

But a zero gradient does not always indicate a minimum. Maxima and saddle points may also have zero gradients.

Second-order condition

The second-order condition uses the Hessian to distinguish the character of a point further.

If, at $x^\ast$,

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

and the Hessian is positive semidefinite, the point is a candidate local minimum:

$$p^\top \nabla^2 f(x^\ast)p\ge 0\quad\text{for all }p.$$

A positive-definite Hessian is stronger:

$$p^\top \nabla^2 f(x^\ast)p>0\quad\text{for all }p\ne 0.$$

Then $x^\ast$ is a strict local minimum.

Positive definiteness

Positive definiteness means that second-order curvature is positive in every direction. This is analogous to the one-dimensional condition $f''(x)>0$ producing a bowl-shaped function.

In terms of the Hessian's eigenvalues:

Hessian state	Interpretation of the point
Every eigenvalue positive	Strict local minimum
Every eigenvalue negative	Strict local maximum
Mixed positive and negative	Saddle point
Includes a zero eigenvalue	Further analysis required

Meaning for convex problems

For a convex function, the first-order condition is much stronger. If

$$\nabla f(x^\ast)=0,$$

then $x^\ast$ is a global minimum. For a constrained convex problem, the KKT conditions play the same role.

Practical stopping criteria

Real code does not wait for exact zero. Instead, it uses a condition such as

$$\|\nabla f(x_k)\|\le \epsilon.$$

It may also inspect changes in function value and variables, as well as constraint violation.

Criterion	Meaning
Small gradient norm	Close to the first-order condition
Small step size	Unable to move farther
Small objective decrease	Almost no improvement
Small constraint violation	Close to feasible

Next: Gradient Descent and Line Search