Week 11: Constraints: Projections and Penalties

Why Constraints Appear#

In many optimisation problems, parameters must satisfy hard constraints:

• Budget limits: $\sum_i w_i \leq B$ — total allocation cannot exceed a budget
• Physics: $\|u\|_2 \leq u_{\max}$ — a robot's control input is bounded
• Probability: $w_i \geq 0, \sum_i w_i = 1$ — weights must form a valid probability distribution (simplex)
• Box constraints: $w \in [a, b]$ — each parameter must lie in an interval
• Robustness: $\|w\|_2 \leq R$ — the model's parameter norm must be bounded

The constrained optimisation problem is:

$\min_x \; f(x) \quad \text{subject to } \; x \in C$

where $C$ is the feasible set (assumed convex for this week). GD alone ignores $C$ and may step outside it. We need mechanisms that respect the constraint.

Projected Gradient Descent#

The simplest approach: after each GD step, project the result back onto the feasible set:

$x_{k+1} = P_C\big(x_k - \eta \nabla f(x_k)\big)$

where $P_C(v) = \arg\min_{x \in C} \|x - v\|_2$ is the Euclidean projection onto $C$.

For convex $f$ and convex $C$, projected GD with $\eta = 1/L$ converges at the same $\mathcal{O}(1/K)$ rate as unconstrained GD. The projection step adds no asymptotic cost — its per-iteration cost depends on how fast we can project onto $C$.

When projection is cheap: A projection is fast if $C$ has a simple closed form. We need $P_C(v)$ to be computable in $\mathcal{O}(d)$ or $\mathcal{O}(d \log d)$ time.

Simple Projections#

$\ell_2$ ball of radius $R$: $C = \{x \mid \|x\|_2 \leq R\}$

$P_C(v) = v \cdot \min\!\left(1, \frac{R}{\|v\|_2}\right)$

If $v$ is already inside the ball ($\|v\| \leq R$), nothing changes. Otherwise, rescale $v$ to lie exactly on the sphere of radius $R$. Cost: $\mathcal{O}(d)$.

Box constraints $[a, b]$: $C = [a_1, b_1] \times \cdots \times [a_d, b_d]$

$P_C(v)_i = \text{clamp}(v_i, a_i, b_i) = \max(a_i, \min(v_i, b_i))$

Each coordinate is independently clamped to its interval. Cost: $\mathcal{O}(d)$.

Probability simplex: $C = \{x \mid \sum_i x_i = 1,\; x_i \geq 0\}$

The projection onto the simplex can be done in $\mathcal{O}(d \log d)$ via sorting (details in the browser lab code). This is more expensive than ball/box projections but still practical.

Worked example — ball projection:

Project $v = (5, 0)$ onto the $\ell_2$ ball of radius $R = 3$:

$\|v\|_2 = 5$, so rescale: $P_C(v) = \frac{3}{5} \cdot (5, 0) = (3, 0)$. The projected point lies on the boundary of the ball.

Soft Penalties#

An alternative to hard projection is to add a penalty term to the objective:

$\min_x \; f(x) + \mu \cdot p(x)$

where $p(x)$ measures how much $x$ violates the constraints. For example:

• $p(x) = \max(0, \|x\|_2 - R)^2$ — penalises being outside the $\ell_2$ ball
• $p(x) = \sum_i \max(0, b_i - x_i)^2 + \max(0, x_i - a_i)^2$ — penalises box violations

As $\mu \to \infty$, the penalty solution approaches the hard-constrained solution. Finite $\mu$ allows some violation — a "soft" constraint.

Tradeoff:

• Hard projection: exactly feasible at every step, but the projection itself can be expensive
• Soft penalty: simple GD on the augmented objective (no projection), but constraints are only approximately satisfied
• In practice: use hard projection for simple constraints (ball, box); soft penalty or augmented Lagrangian for complex constraints

Lagrange Multiplier Intuition#

For the problem $\min_{x} f(x)$ subject to $h(x) \leq 0$, the Lagrangian is:

$L(x, \lambda) = f(x) + \lambda h(x), \quad \lambda \geq 0$

The Lagrange multiplier $\lambda$ acts as a "price" for violating the constraint. If $\lambda$ is large, the penalty for $h(x) > 0$ is severe and the solver stays well inside the feasible region. If $\lambda$ is small, violation is cheap.

At the optimum $x^*$, complementary slackness holds: $\lambda^* h(x^*) = 0$. Either the constraint is active ($h(x^*) = 0$) or the multiplier is zero ($\lambda^* = 0$, the constraint costs nothing).

The optimal $\lambda^*$ also has a sensitivity interpretation: if we tighten the constraint by a small amount $\varepsilon$ (change $h(x) \leq 0$ to $h(x) \leq -\varepsilon$), the optimal objective value changes by approximately $\lambda^* \varepsilon$. The multiplier tells you how much you'd gain by relaxing the constraint.

This intuition is the gateway to duality (Week 12), where we solve the dual problem $\max_{\lambda \geq 0} \min_x L(x, \lambda)$ instead.

Browser lab#

Run projected GD to minimise $f(x) = \|x - x_0\|_2^2$ subject to $x$ being on the probability simplex. Plot the trajectory and observe the projection at each step.

import numpy as np
import matplotlib.pyplot as plt

def project_simplex(v):
    u = np.sort(v)[::-1]
    css = np.cumsum(u)
    rho = np.searchsorted((css - 1.0) / (np.arange(len(v)) + 1.0) < u, True) - 1
    r = rho + 1 if rho >= 0 else 0
    theta = (css[r-1] - 1.0) / r if r > 0 else 0
    return np.maximum(v - theta, 0)

x0 = np.array([2.0, -1.0, 0.5])
def f(x): return 0.5 * np.sum((x - x0)**2)
def grad(x): return x - x0

w = np.array([0.4, 0.3, 0.3])
eta = 0.5
K = 30
path = [w.copy()]; losses = [f(w)]

for _ in range(K):
    w = project_simplex(w - eta * grad(w))
    path.append(w.copy()); losses.append(f(w))

path = np.array(path)

fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(11, 4.5))
ax1.plot(path[:, 0], path[:, 1], "o-", markersize=3, label="Projected GD")
ax1.set_xlabel("x1"); ax1.set_ylabel("x2")
w_opt = project_simplex(x0)
ax1.plot(w_opt[0], w_opt[1], "kx", markersize=10, label="optimum on simplex")
ax1.plot(x0[0], x0[1], "rx", markersize=8, label="unconstrained target x0")
ax1.set_title("Iterates on the Simplex (x1–x2 plane)")
ax1.legend()
ax2.plot(losses)
ax2.set_xlabel("Iteration"); ax2.set_ylabel("f(x)")
ax2.set_title("Loss vs Iteration")
ax2.grid(True, alpha=0.3)
plt.tight_layout(); plt.show()

print(f"Final point on simplex: {np.round(path[-1], 4)}, sum={path[-1].sum():.6f}")