Subgradient methods are convex optimization methods which use subderivatives. Originally developed by Naum Z. Shor and others in the 1960s and 1970s, subgradient methods are convergent when applied even to a non-differentiable objective function. When the objective function is differentiable, subgradient methods for unconstrained problems use the same search direction as the method of gradient descent. Subgradient methods are slower than Newton's method when applied to minimize twice continuously differentiable convex functions. However, Newton's method fails to converge on problems that have non-differentiable kinks. In recent years, some interior-point methods have been suggested for convex minimization problems, but subgradient projection methods and related bundle methods of descent remain competitive. For convex minimization problems with very large number of dimensions, subgradient-projection methods are suitable, because they require little storage. Subgradient projection methods are often applied to large-scale problems with decomposition techniques. Such decomposition methods often allow a simple distributed method for a problem.
Classical subgradient rules Let f : R n → R {\displaystyle f:\mathbb {R} ^{n}\to \mathbb {R} } be a convex function with domain R n . {\displaystyle \mathbb {R} ^{n}.}
A classical subgradient method iterates
x ( k + 1 ) = x ( k ) − α k g ( k ) {\displaystyle x^{(k+1)}=x^{(k)}-\alpha _{k}g^{(k)}\ }
where g ( k ) {\displaystyle g^{(k)}} denotes any subgradient of f {\displaystyle f\ } at x ( k ) , {\displaystyle x^{(k)},\ } and x ( k ) {\displaystyle x^{(k)}} is the k t h {\displaystyle k^{th}} iterate of x . {\displaystyle x.} If f {\displaystyle f\ } is differentiable, then its only subgradient is the gradient vector ∇ f {\displaystyle \nabla f} itself. It may happen that − g ( k ) {\displaystyle -g^{(k)}} is not a descent direction for f {\displaystyle f\ } at x ( k ) . {\displaystyle x^{(k)}.} We therefore maintain a list f b e s t {\displaystyle f_{\rm {best}}\ } that keeps track of the lowest objective function value found so far, i.e.
f b e s t ( k ) = min { f b e s t ( k − 1 ) , f ( x ( k ) ) } . {\displaystyle f_{\rm {best}}^{(k)}=\min\{f_{\rm {best}}^{(k-1)},f(x^{(k)})\}.}
Step size rules Many different types of step-size rules are used by subgradient methods. This article notes five classical step-size rules for which convergence proofs are known:
Constant step size, α k = α . {\displaystyle \alpha _{k}=\alpha .}
Constant step length, α k = γ / ‖ g ( k ) ‖ 2 , {\displaystyle \alpha _{k}=\gamma /\lVert g^{(k)}\rVert _{2},} which gives ‖ x ( k + 1 ) − x ( k ) ‖ 2 = γ . {\displaystyle \lVert x^{(k+1)}-x^{(k)}\rVert _{2}=\gamma .}
… excerpt ends here. Continue reading the full article.
