Subgradient Method

《Subgradient Method》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、SubgradientMethodsStephenBoydandAlmirMutapcicNotesforEE364b,StanfordUniversity,Winter2006-07January23,2007Contents1Introduction22Basicsubgradientmethod22.1Negativesubgradientupdate...........................22.2Stepsizerules............................

2、.......32.3Convergenceresults................................43Convergenceproof43.1Assumptions....................................43.2Somebasicinequalities..............................53.3Aboundonthesuboptimalitybound......................73.4Astoppin

3、gcriterion................................83.5Numericalexample................................84Alternatingprojections94.1Optimalstepsizechoicewhenf⋆isknown...................94.2Findingapointintheintersectionofconvexsets...............114.3Solvingconv

4、exinequalities............................144.4Positivesemidefinitematrixcompletion.....................155Projectedsubgradientmethod165.1Numericalexample................................186Projectedsubgradientfordualproblem186.1Numericalexample.........

5、.......................207Subgradientmethodforconstrainedoptimization217.1Numericalexample................................248Speedingupsubgradientmethods2411IntroductionThesubgradientmethodisaverysimplealgorithmforminimizinganondifferentiableconvexfunct

6、ion.Themethodlooksverymuchliketheordinarygradientmethodfordifferentiablefunctions,butwithseveralnotableexceptions:•Thesubgradientmethodappliesdirectlytonondifferentiablef.•Thesteplengthsarenotchosenviaalinesearch,asintheordinarygradientmethod.Inthemostco

7、mmoncases,thesteplengthsarefixedaheadoftime.•Unliketheordinarygradientmethod,thesubgradientmethodisnotadescentmethod;thefunctionvaluecan(andoftendoes)increase.Thesubgradientmethodisreadilyextendedtohandleproblemswithconstraints.Subgradientmethodscanbemu

8、chslowerthaninterior-pointmethods(orNewton’smethodintheunconstrainedcase).Inparticular,theyarefirst-ordermethods;theirperfor-mancedependsverymuchontheproblemscalingandconditioning.(Incontrast,Newtonandinterior-pointmethodsaresecond-order