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.

Although subgradient methods can be much slower than interior-point methods and Newton's method in practice, they can be immediately applied to a far wider variety of problems and require much less memory. Moreover, by combining the subgradient method with primal or dual decomposition techniques, it is sometimes possible to develop a simple distributed algorithm for a problem.

Basic subgradient update

Let ${\displaystyle f:\mathbb {R} ^{n}\to \mathbb {R} }$  be a convex function with ___domain ${\displaystyle \mathbb {R} ^{n}}$ . The subgradient method uses the iteration

${\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, 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 in the subgradient method. Five basic step size rules for which convergence is guaranteed are:

• 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 .}$ 

Notice that the step sizes listed above are determined before the algorithm is run and do not depend on any data computed during the algorithm. This is very different from the step size rules found in standard descent methods, which depend on the current point and 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]

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.

• 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