Subgradient method

Subgradient methods are iterative methods for solving convex minimization problems. 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 steepest 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 enormomous dimensions, subgradient-projection methods are suitable, because of 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 ${\displaystyle f:\mathbb {R} ^{n}\to \mathbb {R} }$  be a convex function with ___domain ${\displaystyle \mathbb {R} ^{n}}$ . A classical subgradient method iterates

${\displaystyle x^{(k+1)}=x^{(k)}-\alpha _{k}g^{(k)}\ }$ 

where ${\displaystyle g^{(k)}}$  denotes a subgradient of ${\displaystyle f\ }$  at ${\displaystyle x^{(k)}\ }$ . If ${\displaystyle f\ }$  is differentiable, then its only subgradient is the gradient vector ${\displaystyle \nabla f}$  itself. It may happen that ${\displaystyle -g^{(k)}}$  is not a descent direction for ${\displaystyle f\ }$  at ${\displaystyle x^{(k)}}$ . We therefore maintain a list ${\displaystyle f_{\rm {best}}\ }$  that keeps track of the lowest objective function value found so far, i.e.

${\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, ${\displaystyle \alpha _{k}=\alpha .}$ 
• Constant step length, ${\displaystyle \alpha _{k}=\gamma /\lVert g^{(k)}\rVert _{2}}$ , which gives ${\displaystyle \lVert x^{(k+1)}-x^{(k)}\rVert _{2}=\gamma .}$ 
• Square summable but not summable step size, i.e. any step sizes satisfying

${\displaystyle \alpha _{k}\geq 0,\qquad \sum _{k=1}^{\infty }\alpha _{k}^{2}<\infty ,\qquad \sum _{k=1}^{\infty }\alpha _{k}=\infty .}$ 

• Nonsummable diminishing, i.e. any step sizes satisfying

${\displaystyle \alpha _{k}\geq 0,\qquad \lim _{k\to \infty }\alpha _{k}=0,\qquad \sum _{k=1}^{\infty }\alpha _{k}=\infty .}$ 

• Nonsummable diminishing step lengths, i.e. ${\displaystyle \alpha _{k}=\gamma _{k}/\lVert g^{(k)}\rVert _{2}}$ , where

${\displaystyle \gamma _{k}\geq 0,\qquad \lim _{k\to \infty }\gamma _{k}=0,\qquad \sum _{k=1}^{\infty }\gamma _{k}=\infty .}$ 

For all five rules, the step-sizes are determined "off-line", before the method is iterated; the step-sizes do not depend on preceding iterations. This "off-line" property of subgradient methods differs from the "on-line" step-size rules used for descent methods for differentiable functions: Many methods for minimizing differentiable functions satisfy Wolfe's sufficient conditions for convergence, where step-sizes typically depend on the current point and the current search-direction.

Convergence results

For constant step-length and scaled subgradients having Euclidean norm equal to one, the subgradient method converges to an arbitrarily close approximation to the minimum value, that is

${\displaystyle \lim _{k\to \infty }f_{\rm {best}}^{(k)}-f^{*}<\epsilon }$  by a result of Shor.^[1]

These classical subgradient methods have poor performance and are no longer recommended for general use.

Subgradient-projection methods

During the 1970s, Claude Lemaréchal and Phil. Wolfe developed bundle methods of descent for problems of convex minimization. These bundle methods are related to the subgradient projection methods of Boris Polyak (1966).^[2] On some problems, subgradient-projection methods are surprisingly competitive with proximal-bundle methods of descent; both subgradient-projection methods and contemporary bundle-methods often use "ballstep" rules for choosing step-sizes.^[3]

Constrained optimization

Projected subgradient

One extension of the subgradient method is the projected subgradient method, which solves the constrained optimization problem

minimize ${\displaystyle f(x)\ }$  subject to

${\displaystyle x\in {\mathcal {C}}}$ 

where ${\displaystyle {\mathcal {C}}}$  is a convex set. The projected subgradient method uses the iteration

${\displaystyle x^{(k+1)}=P\left(x^{(k)}-\alpha _{k}g^{(k)}\right)}$ 

where ${\displaystyle P}$  is projection on ${\displaystyle {\mathcal {C}}}$  and ${\displaystyle g^{(k)}}$  is any subgradient of ${\displaystyle f\ }$  at ${\displaystyle x^{(k)}.}$ 

General constraints

The subgradient method can be extended to solve the inequality constrained problem

minimize ${\displaystyle f_{0}(x)\ }$  subject to

${\displaystyle f_{i}(x)\leq 0,\quad i=1,\dots ,m}$ 

where ${\displaystyle f_{i}}$  are convex. The algorithm takes the same form as the unconstrained case

${\displaystyle x^{(k+1)}=x^{(k)}-\alpha _{k}g^{(k)}\ }$ 

where ${\displaystyle \alpha _{k}>0}$  is a step size, and ${\displaystyle g^{(k)}}$  is a subgradient of the objective or one of the constraint functions at ${\displaystyle x.\ }$  Take

${\displaystyle g^{(k)}={\begin{cases}\partial f_{0}(x)&{\text{ if }}f_{i}(x)\leq 0\;\forall i=1\dots m\\\partial f_{j}(x)&{\text{ for some }}j{\text{ such that }}f_{j}(x)>0\end{cases}}}$ 

where ${\displaystyle \partial f}$  denotes the subdifferential of ${\displaystyle f\ }$ . If the current point is feasible, the algorithm uses an objective subgradient; if the current point is infeasible, the algorithm chooses a subgradient of any violated constraint.

References

1. The approximate convergence of the constant step-size (scaled) subgradient method is stated as Exercise 6.3.14(a) in Bertsekas (page 636): Bertsekas, Dimitri P. (1999). Nonlinear Programming (Second ed.). Cambridge, MA.: Athena Scientific. ISBN 1-886529-00-0. On page 636, Bertsekas attributes this result to Shor: Shor, Naum Z. (1985). Minimization Methods for Non-differentiable Functions. Springer-Verlag. ISBN 0-387-12763-1.
2. Bertsekas, Dimitri P. (1999). Nonlinear Programming (Second ed.). Cambridge, MA.: Athena Scientific. ISBN 1-886529-00-0.
3. Claude Lemaréchal "Lagrangian Relaxation", Combinatorial Optimization, Lecture Notes in Computer Science, Springer Verlag.

• Bertsekas, Dimitri P. (1999). Nonlinear Programming. Cambridge, MA.: Athena Scientific. ISBN 1-886529-00-0.

• Shor, Naum Z. (1985). Minimization Methods for Non-differentiable Functions. Springer-Verlag. ISBN 0-387-12763-1.

External links

• EE364 and EE364b, a Stanford course homepage