Subgradient method

Subgradient methods are algorithms for solving convex optimization problems that can be used with a non-differentiable objective function originally developed by Shor and others in the 1960s and 1970s. 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 $f:\mathbb {R} ^{n}\to \mathbb {R}$ be a convex function with domain $\mathbb {R} ^{n}$. The subgradient method uses the iteration

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

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

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

$\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

$\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. $\alpha _{k}=\gamma _{k}/\lVert g^{(k)}\rVert _{2}$, where

$\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 size and constant step length, the subgradient algorithm is guaranteed to converge to within some range of the optimal value, i.e.

$\lim _{k\to \infty }f_{\rm {best}}^{(k)}-f^{*}<\epsilon$