ADMM算法原理

《ADMM算法原理》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、3AlternatingDirectionMethodofMultipliers3.1AlgorithmADMMisanalgorithmthatisintendedtoblendthedecomposabilityofdualascentwiththesuperiorconvergencepropertiesofthemethodofmultipliers.Thealgorithmsolvesproblemsintheformminimizef(x)+g(z)(3.1)subjecttoAx+Bz=cwithvariablesx∈Rnandz∈Rm,whereA∈Rp×n,B∈Rp×m

2、,andc∈Rp.Wewillassumethatfandgareconvex;morespecificassump-tionswillbediscussedin§3.2.Theonlydifferencefromthegenerallinearequality-constrainedproblem(2.1)isthatthevariable,calledxthere,hasbeensplitintotwoparts,calledxandzhere,withtheobjec-tivefunctionseparableacrossthissplitting.Theoptimalvalueoft

3、heproblem(3.1)willbedenotedbyp
=inf{f(x)+g(z)

4、Ax+Bz=c}.Asinthemethodofmultipliers,weformtheaugmentedLagrangianL(x,z,y)=f(x)+g(z)+yT(Ax+Bz−c)+(ρ/2)Ax+Bz−c2.ρ21314AlternatingDirectionMethodofMultipliersADMMconsistsoftheiterationsxk+1:=argminL(x,zk,yk)(3.2)ρxzk+1:=argminL(xk+1,z,yk)(3.3)ρzyk+1:=yk

5、+ρ(Axk+1+Bzk+1−c),(3.4)whereρ>0.Thealgorithmisverysimilartodualascentandthemethodofmultipliers:itconsistsofanx-minimizationstep(3.2),az-minimizationstep(3.3),andadualvariableupdate(3.4).Asinthemethodofmultipliers,thedualvariableupdateusesastepsizeequaltotheaugmentedLagrangianparameterρ.Themethodo

6、fmultipliersfor(3.1)hastheform(xk+1,zk+1):=argminL(x,z,yk)ρx,zyk+1:=yk+ρ(Axk+1+Bzk+1−c).HeretheaugmentedLagrangianisminimizedjointlywithrespecttothetwoprimalvariables.InADMM,ontheotherhand,xandzareupdatedinanalternatingorsequentialfashion,whichaccountsforthetermalternatingdirection.ADMMcanbeviewe

7、dasaversionofthemethodofmultiplierswhereasingleGauss-Seidelpass[90,§10.1]overxandzisusedinsteadoftheusualjointminimization.Separatingtheminimizationoverxandzintotwostepsispreciselywhatallowsfordecompositionwhenforgareseparable.ThealgorithmstateinADMMconsistsofzkandyk.Inotherwords,(zk+1,yk+1)isafu

8、nctionof(zk,yk).Thevariablexkisnotpartofthestate;itisanintermediateresultcomputedfromthepreviousstate(zk−1,yk−1).Ifweswitch(re-label)xandz,fandg,andAandBintheprob-lem(3.1),weobtainavariationonADMMwiththeorderofthex-upd