Skip to content
Tutorials Center
My learning

Topics

Lesson 18 of 38 · Constrained Optimization and Lagrange

Projected Gradient Descent

Handle simple constraints by projecting after each gradient step. Learn projections onto boxes, balls and the simplex, and run a complete example in Python.

Lagrange multipliers solve constraints with algebra. Often you want something simpler: take your usual gradient descent loop and just force the iterate back into the feasible set after each step. That is projected gradient descent. It works whenever you can compute the projection onto the feasible set quickly, which is true for many useful sets.

Projection

Given a closed convex set C, the Euclidean projection of a point z onto C is the closest point of C to z:

Text
P_C(z) = argmin over x in C of ‖x - z‖

For convex C this point exists and is unique. If z is already in C, then P_C(z) = z.

The algorithm

Text
x_{k+1} = P_C( x_k - t ∇f(x_k) )

Take an ordinary gradient step (which may leave the set), then project back. For a convex L-smooth f and step t = 1/L, the convergence rate matches the unconstrained case: O(1/k) in general and linear for strongly convex f. A point x* is a fixed point of the update exactly when it satisfies the optimality condition from the chapter on convex problems.

Projections you can write in one line

Set C Projection of z
Box l ≤ x ≤ u clip each coordinate: min(max(zᵢ, lᵢ), uᵢ)
Ball ‖x - c‖ ≤ r if ‖z - c‖ ≤ r keep z; else c + r·(z - c)/‖z - c‖
Non-negative orthant max(zᵢ, 0)
Hyperplane aᵀx = b z - ((aᵀz - b)/‖a‖²)·a
Simplex (xᵢ ≥ 0, Σxᵢ = 1) a short sorting algorithm (below)

Example 1: bounds

Minimize f(x) = ‖x - c‖² where c = (2, -1, 4) subject to 0 ≤ xᵢ ≤ 1. The answer is the clipped target (1, 0, 1).

Python Projected gradient with box constraints

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Example 2: the unit ball

Fit a vector inside the unit ball: minimize ½‖Ax - b‖² subject to ‖x‖ ≤ 1.

Python Ball-constrained least squares

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The final norm is 1: the unconstrained answer lies outside the ball, so the constraint is active and the solution sits on the sphere.

Example 3: the probability simplex

Portfolio weights and probabilities must be non-negative and add to 1. Projecting onto this simplex uses a sorting trick: sort z in decreasing order u₁ ≥ u₂ ≥ ..., find the largest ρ with u_ρ - (1/ρ)(Σ_{i≤ρ} uᵢ - 1) > 0, set θ = (Σ_{i≤ρ} uᵢ - 1)/ρ, and return max(z - θ, 0).

Python Simplex projection and a small problem

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

All projected points are non-negative and sum to 1. The solution for the last problem is (0.65, 0.35, 0): shift c down equally until the positive parts add to 1.

Illustrating the zigzag with the wall

Python Projected path hits the boundary

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Projection is cheap for boxes, balls and the simplex, but hard for general polyhedra (it is itself a quadratic program). When projection is costly, other methods such as Frank-Wolfe or interior-point methods are used.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. Projected gradient descent updates x by

    Take a gradient step, then project the result back onto the feasible set.
  2. 2. The projection of z onto the box 0 ≤ x ≤ 1 is obtained by

    For a box, the closest point is found coordinate by coordinate.
  3. 3. Projecting z = (3, 4) onto the unit ball gives

    ‖z‖ = 5 > 1, so z is rescaled by 1/5.
  4. 4. Projected gradient descent is practical when

    Each iteration calls the projection, so it needs to be fast.

Summary

  • Projected gradient descent takes a gradient step and projects back onto the feasible set.
  • For convex sets the projection is unique; boxes, balls, hyperplanes and the simplex have simple formulas.
  • Convergence rates match unconstrained gradient descent.
  • It is the go-to method when the constraints are simple and the projection is cheap.

Next: Penalty and Barrier Methods