Added to Favorites

Popular Searches

Definitions

Nearby Words

Subgradient methods are algorithms for solving convex optimization problems. Originally developed by Naum Z. Shor and others in the 1960s and 1970s, subgradient methods can be used with 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.## Basic subgradient update

### Step size rules

### Convergence results

## Constrained optimization

### Projected subgradient

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

## References

*## External links

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.

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

- $f\_\{rm\{best\}\}^\{(k)\}\; =\; min\{f\_\{rm\{best\}\}^\{(k-1)\}\; ,\; f(x^\{(k)\})\; \}.$

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\_kgeq0,qquadsum\_\{k=1\}^infty\; alpha\_k^2\; <\; infty,qquad\; sum\_\{k=1\}^infty\; alpha\_k\; =\; infty.$

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

- $alpha\_kgeq0,qquad\; lim\_\{ktoinfty\}\; 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\_kgeq0,qquad\; lim\_\{ktoinfty\}\; gamma\_k\; =\; 0,qquad\; sum\_\{k=1\}^infty\; gamma\_k\; =\; infty.$

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\_\{ktoinfty\}\; f\_\{rm\{best\}\}^\{(k)\}\; -\; f^*math>$

- minimize $f(x)$ subject to

- $xinmathcal\{C\}$

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

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

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

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

- minimize $f\_0(x)$ subject to

- $f\_i\; (x)\; leq\; 0,quad\; i\; =\; 1,dots,m$

where $f\_i$ are convex. The algorithm takes the same form as the unconstrained case

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

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

- $g^\{(k)\}\; =$

partial f_0 (x) & f_i(x) leq 0,quad i = 1,dots,m

partial f_j (x) & f_j(x) > 0end{cases}

where $partial\; f$ denotes the subdifferential of $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.

*

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Wednesday August 20, 2008 at 18:29:59 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Wednesday August 20, 2008 at 18:29:59 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2014 Dictionary.com, LLC. All rights reserved.