Subgradient Methods

← Back to document page

Subgradient MethodsStephenBoyd, Lin Xiao,and AlmirMutapcicNotesfor EE392o,StanfordUniversity, Autumn,2003October 1, 2003Thesubgradientmethodis a simplealgorithmfor minimizinga nondi looks very much like the ordinarygradient method for di erentiablefunctions,but withseveral example,the Subgradient method usessteplengthsthatare xedaheadof time,insteadof an exactor approximateline search asin the gradient method. Unlike the ordinarygradient method, the Subgradient method isnota descent method; the functionvaluecan (andoftendoes) method is far slower thanNewton'smethod, but is much simplerandcan be appliedto a far widervariety of combiningthe Subgradient methodwithprimalor dualdecompositiontechniques,it is sometimespossibleto developa simpledistributedalgorithmfor a method was originallydeveloped by Shorin the SovietUnionin Subgradient Methods is his book [Sho85].

in the gradient method. Unlike the ordinary gradient method, the subgradient method is notadescentmethod;thefunctionvaluecan(andoftendoes)increase. The subgradient method is far slower than Newton’s method, but is much simpler and can be applied to a far wider variety of problems. By combining the subgradient method

  Methods, Subgradient, Subgradient method