Week 1: Optimality Conditions Revisited

From training practice to optimality#

In intermediate Optimization, you trained models by running gradient descent until the gradient was "small enough." The loss curve flattened; you declared convergence and moved on. This practical stopping criterion — $\|\nabla f(x_k)\| \leq \varepsilon$ — works well in practice but dodges a deeper question: when is a point truly optimal?

This course asks that question rigorously. A point $x^*$ might satisfy $\nabla f(x^*) = 0$ and still fail to be a local minimum. A constrained problem might have a point where no feasible direction improves the objective, yet the point is not a KKTKarush–Kuhn–Tucker (optimality conditions) point because a constraint qualification fails. Knowing the difference between "gradient is small" and "$x^*$ is a local minimum" separates applied practitioners from those who can diagnose why an optimizer failed.

Consider a concrete distinction. You train logistic regression on a separable dataset. The loss keeps decreasing epoch after epoch, but the weights $\|w\|_2 \to \infty$ — the objective approaches its infimum asymptotically but never attains it on any finite $w$. No point satisfies $\nabla J(w) = 0$, yet the training procedure "converges" practically. This course gives you the language to describe that situation: the problem lacks an unconstrained minimizer, and even KKT may not apply without a constraint to bound the weights.

Unconstrained first-order conditions#

Let $f: \mathbb{R}^d \to \mathbb{R}$ be differentiable. Suppose $x^*$ is a local minimum: there exists a neighbourhood $\mathcal{N}$ of $x^*$ such that $f(x) \geq f(x^*)$ for all $x \in \mathcal{N}$.

Theorem (First-Order Necessary Condition): If $x^*$ is a local minimum and $f$ is differentiable at $x^*$, then

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

Proof sketch. For any direction $d \in \mathbb{R}^d$, the directional derivative

$f'(x^*; d) = \lim_{t \to 0^+} \frac{f(x^* + t d) - f(x^*)}{t}$

must be $\geq 0$ (otherwise points $x^* + td$ for small $t > 0$ would have lower function value). Repeating with $-d$ gives $f'(x^*; -d) \geq 0$, implying $f'(x^*; d) \leq 0$ by linearity. Thus $f'(x^*; d) = 0$ for all $d$, so $\nabla f(x^*) = 0$.

Points where $\nabla f(x^*) = 0$ are called stationary points or critical points. Not every stationary point is a local minimum — it could be a maximum or a saddle.

Worked example. Let $f(x) = x^4 - 2x^2$. The derivative is $f'(x) = 4x^3 - 4x = 4x(x-1)(x+1)$. Stationary points: $x \in \{-1, 0, 1\}$.

• $f(-1) = 1 - 2 = -1$ — local minimum (check $f''(-1) = 8 > 0$)
• $f(0) = 0$ — local maximum ($f''(0) = -4 < 0$)
• $f(1) = -1$ — local minimum

The stationary condition alone cannot distinguish them; we need second-order information.

When differentiability fails. If $f(x) = |x|$, then $x^* = 0$ is the global minimum but $\nabla f(0)$ does not exist. Subgradient methods (intermediate Optimization Week 10) and proximal methods (Week 7 of this course) handle the nondifferentiable case. The first-order necessary condition requires differentiability — lose it, and you need a different theory.

Second-order flavor#

With twice-differentiable $f$:

• Necessary: If $x^*$ is a local minimum, then $\nabla^2 f(x^*) \succeq 0$ (the Hessian is positive semidefinite, or PSD). Proof: a negative eigenvalue would produce a direction along which $f$ decreases quadratically.

• Sufficient: If $\nabla f(x^*) = 0$ and $\nabla^2 f(x^*) \succ 0$ (strictly positive definite), then $x^*$ is a strict local minimum. The quadratic Taylor approximation bounds the function from below in a neighbourhood.

The gap between necessary ($\succeq$) and sufficient ($\succ$) is the indefinite or semidefinite-at-zero case, e.g., $f(x) = x^3$ at $x = 0$: $f'(0) = 0$, $f''(0) = 0$, yet $x = 0$ is neither a minimum nor a maximum — it is an inflection point.

Strong convexity shortcut. If $f$ is $\mu$-strongly convex ($\nabla^2 f(x) \succeq \mu I$ for all $x$), then any stationary point is automatically the unique global minimum. This is the convex world intermediate Optimization operated in — a world where first-order is enough. This course spends its first seven weeks drilling into what else convex structure buys you beyond GD guarantees.

Worked numeric example. $f(x,y) = x^2 + 3y^2 + \sin(x+y)$. The gradient:

$\nabla f(x,y) = \begin{pmatrix} 2x + \cos(x+y) \\ 6y + \cos(x+y) \end{pmatrix}$

Setting $\nabla f = 0$ gives $2x = 6y$, so $x = 3y$. Substituting: $\cos(4y) = -6y$. This is a transcendental equation — no closed form. Numerical root finding (e.g., Newton on the scalar equation) is needed. The lesson: even smooth unconstrained problems quickly become analytically intractable; that is why iterative methods exist.

Constraints enter#

Real optimization problems rarely live unconstrained on all of $\mathbb{R}^d$. They come with equality and inequality constraints:

The set of points satisfying all constraints is the feasible set $\mathcal{F}$.

Active constraints. At a feasible point $x$, the inequality $h_j(x) \leq 0$ is active if $h_j(x) = 0$ (the constraint is binding — you are on the boundary) and inactive if $h_j(x) < 0$ (slack remains). Inactive constraints do not restrict local movement — you can wiggle a little and still satisfy them. Active ones matter for optimality because they define the local boundary of the feasible set.

Feasible directions. A vector $d \in \mathbb{R}^d$ is a feasible direction at $x \in \mathcal{F}$ if there exists $\bar{t} > 0$ such that $x + td \in \mathcal{F}$ for all $t \in [0, \bar{t}]$. Intuitively, you can take a small step along $d$ without leaving the feasible set.

First-order necessary condition (constrained). If $x^*$ is a local minimum of the constrained problem, then $\nabla f(x^*)^T d \geq 0$ for every feasible direction $d$. No feasible direction points strictly downhill.

For equality constraints $g_i(x) = 0$, the gradient $\nabla g_i(x^*)$ must be orthogonal to any feasible direction — otherwise you could move along the constraint surface and violate $g_i = 0$. This orthogonality is the geometric seed of Lagrange multipliers.

Worked example. $\min \; x^2 + y^2$ subject to $x + y = 2$.

The feasible set is a line; the objective contours are circles centred at the origin. Visually, the optimum is where the smallest circle touches the line — at $(1, 1)$, where the gradient $(2x, 2y) = (2, 2)$ is parallel to the constraint gradient $(1, 1)$. This parallelism $\nabla f = \nu \nabla g$ is exactly the Lagrange multiplier condition $\nabla \mathcal{L} = 0$ that Week 2 formalises.

Constraint qualifications (why KKT needs them)#

The geometric argument above — that at optimality, $\nabla f$ lies in the span of active constraint gradients — requires that the constraint gradients themselves be "well-behaved" at the candidate point. If the constraints are degenerate (e.g., redundant, or gradients are linearly dependent in a pathological way), the multipliers may not exist, or KKT may fail to hold at a genuine local minimum.

A constraint qualification (CQ) is a condition on the constraints that guarantees the existence of Lagrange multipliers at a local minimum. Several CQs exist; the two most common:

• LICQ (Linear Independence Constraint Qualification): The gradients of all active constraints (both equality and inequality) at $x^*$ are linearly independent. LICQ is the strongest commonly used CQ and the easiest to check.

• MFCQ (Mangasarian–Fromovitz CQ): The equality constraint gradients are linearly independent, and there exists a vector $d$ such that $\nabla g_i(x^*)^T d = 0$ for all equalities and $\nabla h_j(x^*)^T d < 0$ for all active inequalities. MFCQ is weaker than LICQ (it allows some dependence among inequality gradients) but still guarantees multiplier existence.

Why CQs matter in practice. Consider $\min_x \; x$ subject to $x^2 \leq 0$. The only feasible point is $x = 0$, which is trivially optimal. But the constraint gradient at $x = 0$ is $\nabla h(0) = 2x|_{x=0} = 0$ — it vanishes. LICQ fails (the "gradient" of the active constraint is the zero vector, trivially linearly dependent). KKT does not hold with finite multipliers: there is no $\lambda \geq 0$ such that $\nabla f(0) + \lambda \nabla h(0) = 0$ and $\lambda h(0) = 0$ simultaneously, because $\nabla h(0) = 0$ gives $1 + 0 = 0$, which is false.

This is a manufactured example, but real equivalents arise in control problems where constraints are implicitly redundant or gradients become near-parallel at the boundary. When an IPM solver (Week 6) reports "constraint qualification violation," this is what it means.

CQs are the legal fine print of optimality theory: they ensure the machinery of Lagrange multipliers and KKT actually applies. The good news: for most well-posed convex problems, Slater's condition (Week 2) provides a clean, easy-to-check alternative.

Knowledge Check#

Browser lab#

Plot a 2D function $f(x,y) = x^4 + y^4 - 2x^2 - 2y^2$ (the "Mexican hat" in each coordinate). Visualise stationary points: minima at $(\pm 1, \pm 1)$, a local maximum at $(0,0)$, and saddles at $(\pm 1, 0)$ and $(0, \pm 1)$. Overlay the gradient field.

import numpy as np
import matplotlib.pyplot as plt

def f(x, y):
    return x**4 + y**4 - 2*x**2 - 2*y**2

def grad(x, y):
    return np.array([4*x**3 - 4*x, 4*y**3 - 4*y])

xs = np.linspace(-1.8, 1.8, 300)
ys = np.linspace(-1.8, 1.8, 300)
X, Y = np.meshgrid(xs, ys)
Z = f(X, Y)

fig, ax = plt.subplots(figsize=(7, 6))
cont = ax.contourf(X, Y, Z, levels=30, cmap="coolwarm", alpha=0.85)
plt.colorbar(cont, ax=ax, label="f(x,y)")

# Mark stationary points
stationary = [(-1,-1), (-1,1), (1,-1), (1,1), (0,0), (-1,0), (1,0), (0,-1), (0,1)]
labels = ["min", "min", "min", "min", "max", "saddle", "saddle", "saddle", "saddle"]
colors = ["tab:green"]*4 + ["tab:red"] + ["tab:orange"]*4

for (sx, sy), lbl, clr in zip(stationary, labels, colors):
    ax.plot(sx, sy, "o", color=clr, markersize=8, markeredgecolor="black", markeredgewidth=0.5)

# Gradient field on a coarser grid
gx = np.linspace(-1.8, 1.8, 18)
gy = np.linspace(-1.8, 1.8, 18)
GX, GY = np.meshgrid(gx, gy)
U = np.zeros_like(GX)
V = np.zeros_like(GY)
for i in range(GX.shape[0]):
    for j in range(GX.shape[1]):
        gv = grad(GX[i,j], GY[i,j])
        nrm = np.linalg.norm(gv)
        if nrm > 0.01:
            U[i,j], V[i,j] = gv / nrm

ax.quiver(GX, GY, U, V, scale=30, alpha=0.5, color="black")

ax.set_xlabel("x")
ax.set_ylabel("y")
ax.set_title("Stationary points of $f(x,y)=x^4+y^4-2x^2-2y^2$")
ax.set_aspect("equal")
plt.show()

# Check gradient norms at stationary points
for (sx, sy), lbl in zip(stationary, labels):
    g = grad(sx, sy)
    print(f"Point ({sx:+.0f}, {sy:+.0f}) [{lbl:6s}]: gradient norm = {np.linalg.norm(g):.6f}")

print("Notice: every one of the nine marked points has gradient norm 0.000000: a vanishing gradient marks maxima, minima and saddles alike.")

Key takeaways#

• A small gradient is not optimality. The first-order condition $\nabla f(x^*) = 0$ is necessary only for differentiable unconstrained problems, and it marks maxima and saddles just as well as minima.
• The Hessian classifies stationary points: $\nabla^2 f(x^*) \succeq 0$ is necessary at a minimum, $\nabla^2 f(x^*) \succ 0$ is sufficient, and strong convexity makes any stationary point the unique global minimum.
• With constraints, "set the derivative to zero" becomes "no feasible direction descends": $\nabla f(x^*)^T d \geq 0$ for every feasible direction $d$.
• Active constraints are the ones that matter. Inactive constraints do not restrict local movement and will carry zero multiplier.
• KKT needs a constraint qualification. LICQ (active constraint gradients independent) and MFCQ are the standard ones; without a CQ a genuine local minimum can have no multipliers at all, as $\min x$ subject to $x^2 \leq 0$ shows.
• For convex problems, Slater's condition is the easy alternative to checking a CQ by hand.

Further reading#

• Jorge Nocedal & Stephen Wright, Numerical Optimization (2nd ed., Springer, 2006) — Chapter 2 states and proves the first- and second-order optimality conditions.
• Dimitri P. Bertsekas, Nonlinear Programming (3rd ed., Athena Scientific, 2016) — the rigorous theory of stationarity and constraint qualifications.
• Stephen Boyd & Lieven Vandenberghe, Convex Optimization (Cambridge University Press, 2004) — free online; the optimality-condition material for the convex case.