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 (developed in Robot Learning Week 3: Control Fundamentals)
• 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.

Knowledge check#

Browser lab: projected GD on the simplex#

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]
    cssv = np.cumsum(u)
    rho = np.nonzero(u * np.arange(1, len(v) + 1) > (cssv - 1))[0][-1]
    theta = (cssv[rho] - 1.0) / (rho + 1.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}")
print("Notice: every iterate stays on the simplex — the projection enforces the constraint exactly at each step.")

Key takeaways#

• Projected gradient descent takes the usual step and projects back onto the feasible set, and it matches unconstrained GD's rate when $f$ and $C$ are both convex.
• The projection has to be cheap to be useful: the $\ell_2$ ball rescales, the box clamps, and the simplex sorts, all $\mathcal{O}(d)$ or $\mathcal{O}(d \log d)$.
• Soft penalties replace the hard constraint with a penalty in the objective; finite $\mu$ permits some violation, and $\mu \to \infty$ recovers the constrained solution.
• The Lagrange multiplier is the shadow price of the constraint: $\lambda^*$ is the marginal change in the optimal objective when the constraint is tightened.
• Complementary slackness $\lambda_i h_i(x) = 0$ says an inactive constraint has zero price, while a binding one can have a positive price.
• Hard projection for simple sets, penalties or augmented Lagrangians for complex ones. The multiplier intuition is the doorway to Week 12.

Further reading#

• Stephen Boyd & Lieven Vandenberghe, Convex Optimization (Cambridge University Press, 2004). §4.2 develops projection onto convex sets and gives the ball, box, and simplex formulas.
• Dimitri P. Bertsekas, Nonlinear Programming (3rd ed., Athena Scientific, 2016). Chapter 3 covers projection and penalty methods for constrained problems.
• Neal Parikh & Stephen Boyd, Proximal Algorithms (Foundations and Trends in Optimization, 2014). Section 6 treats projection as the proximal operator of an indicator function.