ADMM优化算法讲解

alternating direction method of multipliers优化算法讲解OutlineDual decompositionMethod of multipliersAlternating direction method of multipliersCommon patternsExamplConsensus and exchangeConclusionsDual decompositionDual problemp convex equality constrained optimization problemminimizesubject to Ax= 6e Lagrangian: L(a, g)=f(a)+y(Ac-bdual function: g(y)=infx L(, g)e dual problem: maximize g(g)recover x*=argminL(, y*)Dual decompositionDual ascentgradient method for dual problem: y+l=yk +aVg(yky ")=A c-b, where a= argmin L(a, y")b dual ascent method isk+1gminz L(a, yk/-minimization(Axk+I-b)// dual updateworks, with lots of strong assumptionsDual decompositionDual decompositione suppose f is separablef(x)=f1(x1)+…+fN(xN),x=(x1Nthen L is separable in x: L(a, y)=L1(a1, 3)+...+Ln(N, 3)-y bLi(ai, y)=fi(ai)+y Aiaie -minimization in dual ascent splits into N separate minimizationsk+1argmin Li(li, y)Which can be carried out in parallelDual decompositionDual decompositiondual decomposition(Everett, Dantzig, Wolfe, Benders 1960-65k+1argLi(ei, y)N A: k+scatterupdate i in parallel, gather Ai k+solve a large problemby iteratively solving subproblems(in parallel)dual variable update provides coordinationworks, with lots of assumptions; often slowDual decompositionOutlineDual decompositionMethod of multipliersAlternating direction method of multipliersCommon patternsExamplConsensus and exchangeConclusionsMethod of multipliersMethod of multipliersa method to robustify dual ascentb use augmented Lagrangian(Hestenes, Powell 1969),p>0(, y)=f(c)+y(Ax-b)+(p/2)Acmethod of multipliers( Hestenes, Powell; analysis in Bertsekas 1982)k+1argmin Lp(a, yD(A.(note specific dual update step length pMethod of multipliersMethod of multipliers dual update stepoptimality conditions( for differentiableAcx-b=0, Vf(a*)+A(primal and dual feasibility)Since ah+1minimizes Lp(a, y)k+1 kf(x4+1)+A7(y+p(AVxf(at)+adual update yti=y+p(k+1k+1dual feasibleprimal feasibility achieved in limit: A k+I-b>0Method of multipliers