Let be a nonempty closed convex set in a real finite-dimensional Euclidean space, and let be a differentiable convex function. A projected gradient descent step isThe Euclidean projection onto a convex set is single-valued under these assumptions and restores feasibility after the unconstrained gradient descent step. Closedness matters: the nearest point to zero in the convex set does not exist.
This is the proximal gradient method with nonsmooth term equal to the indicator functional of a constraint set, whose proximal operator is . If is -Lipschitz continuous, a standard choice gives the usual convex objective-error bound relative to an existing minimizer.[ref]
Proximal Algorithms by Neal Parikh and Stephen Boyd. sections1.2 and4.2, projected-gradient specialization, printed pp125–126 and149
For , . Minimizing from with gives , the constrained optimum.
The projected subgradient method minimizes a possibly nonsmooth convex function over a closed convex set by iterating with . Nonexpansiveness of Euclidean projection onto a convex set and the subgradient inequality give its basic convergence bound.
If and , thenIt follows by expanding the squared distance after each projected step, using nonexpansiveness of projection, summing the resulting inequalities, and applying convexity.
Articles by others on the same topic
There are currently no matching articles.