Subgradient method: Difference between revisions

Revision as of 08:12, 18 March 2012

Revision as of 16:08, 18 March 2012

Line 1:

'''Subgradient methods''' are [[iterative method]]s for solving [[convex optimization|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. SubgradientWhen methodsthe areobjective slowerfunction thanis Newton'sdifferentiable, methodsubgradient whenmethods appliedfor tounconstrained minimizeproblems twiceuse continuouslythe differentiablesame convexsearch functions.direction However,as Newton'sthe method failsof to[[gradient convergedescent|steepest on problems that have non-differentiable kinks and flat regionsdescent]].

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.

Depending on the algorithm, subgradient methods may use different strategies for determining the search direction and step length.

* Using the steepest descent direction, but with step lengths that are computed according to a fixed strategy or from an estimate of the difference of the current function value from the optimum.

* Applying a [[linear transformation|transformation matrix]] to the steepest descent direction, and then performing a line search or applying a step length selection strategy. (Naum Shor's Space Dilation/R algorithms)

* Building a local model of the subdifferential of the function (Bundle Methods)

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.