Optimization

Projected Gradient Descent

Take a gradient step, then project back onto the feasible set, a simple and effective method for constrained problems with easy projections.

Step, then project

Projected gradient descent handles the constraint set C by alternating two operations: take an ordinary gradient step, then project the result back onto C. The update is x_{k+1} = Proj_C(x_k - a * grad f(x_k)), where Proj_C(y) returns the closest point in C to y. This keeps every iterate feasible.

When it is practical

The method is efficient only when the projection onto C is cheap. Simple sets have closed-form projections: box constraints clip each coordinate to its bounds, the nonnegative orthant sets negatives to zero, and a ball scales the vector to its radius. For complex feasible sets the projection can be as hard as the original problem.

Convergence

For convex f and convex C, projected gradient descent converges at the same rates as unconstrained gradient descent.
Strong convexity gives linear convergence; smoothness with a suitable step gives O(1/k).
The projection is a nonexpansive operation, so it does not spoil the descent guarantees.

Relation to proximal methods

Projection onto C is exactly the proximal operator of the indicator function of C (zero on C, infinity outside). So projected gradient descent is a special case of the proximal gradient method, which handles more general nonsmooth terms such as L1 regularization.

Variants

Accelerated projected gradient adds Nesterov momentum for an O(1/k^2) rate. The conditional gradient (Frank-Wolfe) method avoids projection entirely by solving a linear subproblem over C, useful when linear optimization over C is cheaper than projection, as for the trace-norm ball.

python

def proj_box(y, lo, hi):
    return np.clip(y, lo, hi)
for _ in range(iters):
    x = proj_box(x - lr*grad(x), lo, hi)

Projected gradient methods enforce simple physical bounds during design optimization at almost no extra cost per step.