First-Order Methods for Constrained Optimization
Stub. Extending descent methods to problems with an explicit constraint set: optimality conditions at a constrained minimum, Euclidean projection onto the feasible set, the projected gradient algorithm (short-step and backtracking variants, the smooth strongly convex case, momentum variants, alternative search directions), and the conditional gradient (Frank-Wolfe) method, which avoids projection entirely by solving a linear subproblem over the constraint set each step.
Corresponds to Chapter 7. When is constrained to a set , an ordinary gradient step can leave entirely, so the two standard fixes are projection (move in the gradient direction, then snap back to the nearest feasible point via Euclidean projection, giving the projected gradient algorithm, whose step-size rules and momentum variants mirror the unconstrained case) and the conditional gradient (Frank-Wolfe) method, which instead solves a linear minimization over each iteration and moves partway toward that solution — never leaving at all, and avoiding projection’s cost when is complex but linear optimization over it is cheap (e.g. the simplex or a norm ball). Optimality conditions for the constrained problem (a stationary point of the Lagrangian, previewing duality-and-lagrangian-methods) ground both approaches.
Outline (TODO — flesh out each)
- Optimality conditions for constrained optimization
- Euclidean projection
- The projected gradient algorithm — short-step and backtracking
- The smooth strongly convex case
- Momentum variants; alternative search directions
- The conditional gradient (Frank-Wolfe) method