admm_slides_Alternating Direction Method of Multipliers

有关ADMM的相关内容

Alternating Direction Method of Multipliers

Prof S. BoydEE364b, Stanford University

source: Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers (Boyd, Parikh, Chu, Peleato, Eckstein)1

有关ADMM的相关内容

Goals

robust methods for

arbitrary-scale optimization– machine learning/statistics with huge data-sets– dynamic optimization on large-scale network

decentralized optimization– devices/processors/agents coordinate to solve large problem, by passing relatively small messages

有关ADMM的相关内容

OutlineDual decomposition Method of multipliers Alternating direction method of multipliers Common patterns Examples Consensus and exchange Conclusions

Dual decomposition

有关ADMM的相关内容

Dual problem

convex equality constrained optimization problem minimize subject to f (x ) Ax= b

Lagrangian: L(x, y )= f (x)+ y T (Ax b) dual function: g (y )= inf x L(x, y ) dual problem: maximize g (y )

recover x = argminx L(x, y )

Dual decomposition

有关ADMM的相关内容

Dual ascent

gradient method for dual problem: y k+1= y k+αk g (y k ) g (y k )= Ax b, where x = argminx L(x, y k ) dual ascent method is xk+1 y k+1:=:= argminx L(x, y k ) y k+αk (Axk+1 b)// x-minimization// dual update

works, with lots of strong assumptions

Dual decomposition

有关ADMM的相关内容

Dual decomposition

suppose f is separable: f (x )= f 1 (x 1 )+···+ f N (x N ), x= (x 1, . . ., x N )

then L is separable in x: L(x, y )= L1 (x1, y )+···+ LN (xN, y ) y T b, Li (xi, y )= fi (xi )+ y T Ai xi

x-minimization in dual ascent splits into N separate minimizations+1 xk i

:=

argmin Li (xi, y k )xi

which can be carried out in parallel

Dual decomposition

有关ADMM的相关内容

Dual decomposition

dual decomposition (Everett, Dantzig, Wolfe, Benders 1960–65)+1 xk i

:=:=

argminxi Li (xi, y k ), y k+αk (N i=1

i= 1, . . ., N

y k+1

+1 b) Ai xk i

+1 scatter y k; update xi in parallel; gather Ai xk i

solve a large problem– by iteratively solving subproblems (in parallel)– dual variable update provides coordination

works, with lots of assumptions; often slow

Dual decomposition

有关ADMM的相关内容

OutlineDual decomposition Method of multipliers Alternating direction method of multipliers Common patterns Examples Consensus and exchange Conclusions

Method of multipliers

有关ADMM的相关内容

Method of multipliers

a method to robustify dual ascent use augmented Lagrangian (Hestenes, Powell 1969),ρ> 0 Lρ (x, y )= f (x)+ y T (Ax b)+ (ρ/2) Ax b2 2

method of multipliers (Hestenes, Powell; analysis in Bertsekas 1982) xk+1 yk+1

:=:=

argmin Lρ (x, y k )x

y+ρ(Axk+1 b)

k

(note speci c dual update step lengthρ)

Method of multipliers

有关ADMM的相关内容

Method of multipliers dual update step

optimality conditions (for di erentiable f ): Ax b= 0, (primal and dual feasibility) since xk+1 minimizes Lρ (x, y k ) 0=== x Lρ

(xk+1, y k ) x f (xk+1 )+ AT y k+ρ(Axk+1 b) x f (xk+1 )+ AT y k+1 f (x )+ AT y = 0

dual update y k+1= y k+ρ(xk+1 b) makes (xk+1, y k+1 ) dual feasible primal feasibility achieved in limit: Axk+1 b→ 0

Method of multipliers

有关ADMM的相关内容

Method of multipliers

(compared to dual decomposition)

good news: converges under much more relaxed conditions (f can be nondi erentiable, take on value+∞, . . . ) bad news: quadratic penalty destroys splitting of the x-update, so can’t do decomposition

Method of multipliers

有关ADMM的相关内容

OutlineDual decomposition Method of multipliers Alternating direction method of multipliers Common patterns Examples Consensus and exchange Conclusions

Alternating direction method of multipliers

有关ADMM的相关内容

Alternating direction method of multipliers

a method– with good robustness of method of multipliers– which can support decomposition

“robust dual decomposition” or“decomposable method of multipliers” proposed by Gabay, Mercier, Glowinski, Marrocco in 1976

Alternating direction method of multipliers

有关ADMM的相关内容

Alternating direction method of multipliers

ADMM problem form (with f, g convex) minimize f (x)+ g (z ) subject to Ax+ Bz= c– two sets of variables, with separable objective

Lρ (x, z, y )= f (x)+ g (z )+ y T (Ax+ Bz c)+ (ρ/2) Ax+ Bz c ADMM: xk+1 zk+1

2 2

:=:=:=

argminx Lρ (x, z k, y k ) argminz Lρ (xk+1

// x-minimizationk

, z, y )

// z -minimization// dual update14

y k+1

y k+ρ(Axk+1+ Bz k+1 c)

Alternating direction method of multipliers

有关ADMM的相关内容

Alternating direction method of multipliers

if we minimized over x and z jointly, reduces to method of multipliers instead, we do one pass of a Gauss-Seidel method we get splitting since we minimize over x with z xed, and vice versa

Alternating direction method of multipliers

有关ADMM的相关内容

ADMM and optimality conditions

optimality conditions (for di erentiable case):– primal feasibility: Ax+ Bz c= 0– dual feasibility: f (x)+ AT y= 0, g ( z )+ B T y= 0

since z k+1 minimizes Lρ (xk+1, z, y k ) we have 0== g (z k+1 )+ B T y k+ρB T (Axk+1+ Bz k+1 c) g (z k+1 )+ B T y k+1