Week 1: Optimality Conditions Revisited — Adv. Optimization

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 KKT 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:

\min_x &\quad f(x) \\ \text{s.t.} &\quad g_i(x) = 0, \quad i = 1, \ldots, m \quad (\text{equalities}) \\ &\quad h_j(x) \leq 0, \quad j = 1, \ldots, p \quad (\text{inequalities}) \end{aligned}$$ 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. <Exercise type="fill-blank" question="For smooth unconstrained $f$, a first-order necessary condition at a local minimum is that the gradient equals ____." correctAnswer="0" explanation="$\nabla f(x^*) = 0$ is the first-order necessary condition for an unconstrained local minimum when $f$ is differentiable." /> <Quiz questions={[ { type: "fill-blank", question: "A point where $\nabla f(x) = 0$ is called a ____ point.", correctAnswer: "stationary", explanation: "Stationary (or critical) points satisfy the first-order necessary condition but are not guaranteed to be minima." }, { type: "multiple-choice", question: "Which of the following is a necessary condition for $x^*$ to be a local minimum of a twice-differentiable function?", options: ["$\nabla^2 f(x^*) \succ 0$", "$\nabla^2 f(x^*) \succeq 0$", "$\nabla^2 f(x^*) = 0$", "$\nabla f(x^*) \succ 0$"], correctIndex: 1, explanation: "PSD Hessian is necessary ($\succeq 0$). Strictly PD ($\succ 0$) is sufficient but not necessary — $f(x)=x^4$ at $x=0$ has $f''(0)=0$ yet is a minimum." }, { type: "multiple-choice", question: "An inequality constraint $h_j(x) \leq 0$ is called inactive at $x$ when:", options: ["$h_j(x) = 0$", "$h_j(x) > 0$", "$h_j(x) < 0$", "$h_j(x)$ is undefined"], correctIndex: 2, explanation: "Inactive means $h_j(x) < 0$ — slack remains and the constraint does not restrict local movement. Active means $h_j(x) = 0$ (binding)." }, { type: "multiple-choice", question: "LICQ (Linear Independence Constraint Qualification) requires the gradients of which constraints to be linearly independent?", options: ["All constraints, active and inactive", "Only equality constraints", "Only the active constraints at the point", "Only inequality constraints"], correctIndex: 2, explanation: "LICQ requires linear independence of the gradients of all active constraints (both equality and inequality) at the candidate point." } ]} /> ## 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. ```python 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}") ```

Week 2: Lagrangian Duality in Depth

From Training Practice to Optimality#

Unconstrained First-Order Conditions#

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}$

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.

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.

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}$

Constraints Enter#

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

\min_x &\quad f(x) \\ \text{s.t.} &\quad g_i(x) = 0, \quad i = 1, \ldots, m \quad (\text{equalities}) \\ &\quad h_j(x) \leq 0, \quad j = 1, \ldots, p \quad (\text{inequalities}) \end{aligned}$$ 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. <Exercise type="fill-blank" question="For smooth unconstrained $f$, a first-order necessary condition at a local minimum is that the gradient equals ____." correctAnswer="0" explanation="$\nabla f(x^*) = 0$ is the first-order necessary condition for an unconstrained local minimum when $f$ is differentiable." /> <Quiz questions={[ { type: "fill-blank", question: "A point where $\nabla f(x) = 0$ is called a ____ point.", correctAnswer: "stationary", explanation: "Stationary (or critical) points satisfy the first-order necessary condition but are not guaranteed to be minima." }, { type: "multiple-choice", question: "Which of the following is a necessary condition for $x^*$ to be a local minimum of a twice-differentiable function?", options: ["$\nabla^2 f(x^*) \succ 0$", "$\nabla^2 f(x^*) \succeq 0$", "$\nabla^2 f(x^*) = 0$", "$\nabla f(x^*) \succ 0$"], correctIndex: 1, explanation: "PSD Hessian is necessary ($\succeq 0$). Strictly PD ($\succ 0$) is sufficient but not necessary — $f(x)=x^4$ at $x=0$ has $f''(0)=0$ yet is a minimum." }, { type: "multiple-choice", question: "An inequality constraint $h_j(x) \leq 0$ is called inactive at $x$ when:", options: ["$h_j(x) = 0$", "$h_j(x) > 0$", "$h_j(x) < 0$", "$h_j(x)$ is undefined"], correctIndex: 2, explanation: "Inactive means $h_j(x) < 0$ — slack remains and the constraint does not restrict local movement. Active means $h_j(x) = 0$ (binding)." }, { type: "multiple-choice", question: "LICQ (Linear Independence Constraint Qualification) requires the gradients of which constraints to be linearly independent?", options: ["All constraints, active and inactive", "Only equality constraints", "Only the active constraints at the point", "Only inequality constraints"], correctIndex: 2, explanation: "LICQ requires linear independence of the gradients of all active constraints (both equality and inequality) at the candidate point." } ]} /> ## 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. ```python 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}") ```

Week 2: Lagrangian Duality in Depth