ADMM优化算法讲解

【实例简介】
alternating direction method of multipliers优化算法讲解
Outline Dual decomposition Method of multipliers Alternating direction method of multipliers Common patterns Exampl Consensus and exchange Conclusions Dual decomposition Dual problem p convex equality constrained optimization problem minimize subject to Ax= 6 e Lagrangian: L(a, g)=f(a)+y(Ac-b dual function: g(y)=infx L(, g) e dual problem: maximize g(g) recover x*=argminL(, y*) Dual decomposition Dual ascent gradient method for dual problem: y+l=yk +aVg(yk y ")=A c-b, where a= argmin L(a, y") b dual ascent method is k+1 gminz L(a, yk / -minimization (Axk+I-b)// dual update works, with lots of strong assumptions Dual decomposition Dual decomposition e suppose f is separable f(x)=f1(x1)+…+fN(xN),x=(x1 N then L is separable in x: L(a, y)=L1(a1, 3)+...+Ln(N, 3)-y b Li(ai, y)=fi(ai)+y Aiai e -minimization in dual ascent splits into N separate minimizations k+1 argmin Li(li, y) Which can be carried out in parallel Dual decomposition Dual decomposition dual decomposition(Everett, Dantzig, Wolfe, Benders 1960-65 k+1 arg Li(ei, y) N A: k+ scatter update i in parallel, gather Ai k+ solve a large problem by iteratively solving subproblems(in parallel) dual variable update provides coordination works, with lots of assumptions; often slow Dual decomposition Outline Dual decomposition Method of multipliers Alternating direction method of multipliers Common patterns Exampl Consensus and exchange Conclusions Method of multipliers Method of multipliers a method to robustify dual ascent b use augmented Lagrangian(Hestenes, Powell 1969),p>0 (, y)=f(c)+y(Ax-b)+(p/2)Ac method of multipliers( Hestenes, Powell; analysis in Bertsekas 1982) k+1 argmin Lp(a, y D(A. (note specific dual update step length p Method of multipliers Method of multipliers dual update step optimality conditions( for differentiable Acx-b=0, Vf(a*)+A (primal and dual feasibility) Since ah+1 minimizes Lp(a, y) k+1 k f(x4+1)+A7(y+p(A Vxf(at)+a dual update yti=y+p( k+1k+1 dual feasible primal feasibility achieved in limit: A k+I-b>0 Method of multipliers 【实例截图】
【核心代码】