Stay feasible after a gradient step
An unconstrained gradient step may leave the feasible set. Projected gradient returns the step to that set and admits a quantitative objective bound under appropriate assumptions.
Let be nonempty, closed and convex. Let be convex and differentiable, with -Lipschitz gradient for some . Assume a minimizer exists.
Definition 8.1.1
(Euclidean projection and projected gradient)
For , the projection is the unique point of closest to in the Euclidean norm. For and a fixed step , the projected gradient method sets
Closedness and convexity ensure existence and uniqueness of the closest point; the constraint is part of the optimization problem, not an afterthought.
Projection and a three-point estimate
The projection is characterized by an inequality rather than a formula.
Lemma 8.1.2
(Variational inequality for the projection)
Let and . Then if and only if for every .
Proof
(Differentiate along a feasible segment)
Suppose and . The segment is feasible for ; the right derivative at zero of its squared distance to , namely , cannot be negative. Conversely, if the inequality holds, then for every , expanding shows that is a closest point.
In particular, for differentiable convex , a feasible point minimizes over exactly when for all . With this is the variational inequality, so optimality is equivalent to
for any . This condition allows at the boundary.
Theorem 8.1.3
(One projected step)
For , and every ,
Proof
(Three inequalities and a polarization identity)
Put and . The smoothness inequality and give . Convexity gives . Their sum is at most . Apply the projection inequality with point , projection and feasible point :
Finally use . The last squared term cancels the smoothness term.
Proof X-ray
Where the step-size condition is spent
The proof combines three inequalities, and each hypothesis is used exactly once. Smoothness gives an upper model of at ; convexity compares with through a linearization at ; the projection inequality is the only place the set enters, and it applies because the comparison point is feasible. The key move is the polarization identity, which converts the inner product produced by the projection into a difference of squared distances to minus the extra term . That extra term cancels the smoothness penalty, which is at most exactly when ; this is where is spent. With a longer step a positive leftover would remain on the right. The resulting right-hand side is a difference of consecutive distances, which is what makes the next proof telescope.
A finite-iteration guarantee
Theorem 8.1.4
(Objective gap)
For every integer ,
Proof
(Monotonicity and telescoping)
Taking in the one-step inequality shows . Taking and summing from to telescopes the squared distances. Every objective gap in that sum is at least the final gap because the values are nonincreasing; each gap is nonnegative because minimizes over . Divide by .
The theorem bounds the last iterate's objective gap. It assumes an attained minimizer and exact projection.
Common mistake
(Reading the rate as more than an objective bound)
The theorem does not give the same rate for distance to a unique solution, a stopping rule under roundoff, or an inexact projection. It also counts iterations, not wall-clock time: projection cost can dominate an iteration.
Worked example 8.1.5
(An optimum at the boundary)
Take , , and . Since , the step is allowed. The unprojected step is , so . The next unprojected step is and projects back to . This is the constrained minimizer even though , because the direction that would decrease is infeasible.
Common mistake
(Expecting the gradient to vanish at the solution)
A constrained minimizer on the boundary need not be a stationary point of , as above shows. The correct test is the fixed-point condition , equivalently for every feasible . A stopping rule based on would never stop here.
On a box the projection acts coordinatewise, and each coordinate can reach its bound at a different time.
Worked example 8.1.6
(Projection onto a box)
Take and , so and . Use and . Projection onto the box clips each coordinate to .
- , so .
- , so .
- , the unprojected point is , and .
The point is the constrained minimizer, with ; there , so the first coordinate is held by its bound while the second is unconstrained-stationary. Check the theorem: , so the bound is , while the actual gaps are and .
Assumptions do work
Counterexample mode
Closed feasible sets need not contain an optimizer
On , is convex with globally Lipschitz gradient, since , but its infimum is zero and is not attained at any finite . Closedness and convexity of therefore do not imply that exists. Separately, a nonconvex set can have multiple closest points: for , both points project the origin.
The step-size condition is sufficient, not a claim that every larger step fails.
Worked example 8.1.7
(Steps longer than 1/L)
Let , and , so and . With the iterates alternate as and grows. With , which also violates , the iterates are and converge to the minimizer . The theorem simply does not cover such steps; for this quadratic, convergence holds exactly when .
Exercises
Quick check
(In the boundary example, compute and and explain why a nonzero derivative is consistent with constrained optimality.)
Solution · Answer
Both are . The feasible directions at the right endpoint do not point toward larger , where this objective decreases.
Quick check
(What does the objective-gap bound become for , and ?)
Solution · Answer
It is at most .
Quick check
(Why is existence of stated as an assumption?)
Solution · Answer
The smooth convex softplus example has a finite infimum but no minimizing point on the closed set .
Quick check
(Why does convexity of matter for a uniquely defined Euclidean projection?)
Solution · Answer
Together with closedness and nonemptiness, convexity gives a unique closest point; shows uniqueness can fail without it.
Further reading
MIT OpenCourseWare, Projected Gradient Descent and Mirror Descent discusses projected methods.