Operator splittingDouglas-Rachford splittingConsensus optimizationMonotone Operator Splitting MethodsStephen Boyd (with help from Neal Parikh and Eric Chu)EE364b, Stanford University1Outline1 Operator splitting2 Douglas-Rachford splitting3 Consensus optimizationOperator splitting 2Operator splitting•want to solve 0 ∈ F (x) with F maximal monotone•main idea: write F as F = A + B, with A and B maximal monotone•called operator splitting•solve using method s that require evaluation of resolventsRA= (I + λA)−1, RB= (I + λB)−1(or Cayley operators CA= 2RA− I and CB= 2RB− I)•useful when RAand RBcan b e evaluated more easily than RFOperator splitting 2Main result•A, B maximal monotone, so Cayley op era tors CA, CBnonexpansive•hence CACBnonexpansive•key result:0 ∈ A(x) + B(x) ⇐⇒ CACB(z) = z, x = RB(z)•so solutions of 0 ∈ A(x) + B(x) can be found from fixed points ofnonexpansive operator CACBOperator splitting 3Proof of main result•write CACB(z) = z and x = RB(z) asx = RB(z), ˜z = 2x − z, ˜x = RA(˜z), z = 2˜x − ˜z•subtract 2nd & 4th equations to c oncl u de x = ˜x•4th equation is then 2x = ˜z + z•now add x + λB(x) ∋ z and x + λA(x) ∋ ˜z to get2x + λ(A(x) + B(x)) ∋ ˜z + z = 2x•hence A(x) + B(x) ∋ 0•argument goes other way (but we don’t need it)Operator splitting 4Outline1 Operator splitting2 Douglas-Rachford splitting3 Consensus optimizationDouglas-Rachford splitting 5Peaceman-Rachford and Douglas-Rachford splitting•Peaceman-Rachford splitting is un d amped iterationzk+1= CACB(zk)doesn’t converge in gen er al case; need CAor CBto be contraction•Douglas-Rachford splitting is damped iterationzk+1:= (1/2)(I + CACB)(zk)always converges when 0 ∈ A(x) + B(x) has solution•these methods trace ba ck to the mid-1950s (!!)Douglas-Rachford splitting 5Douglas-Rachford splittingwrite D-R iteration zk+1:= (1/2)(I + CACB)(zk) asxk+1/2:= RB(zk)zk+1/2:= 2xk+1/2− zkxk+1:= RA(zk+1/2)zk+1:= zk+ xk+1− xk+1/2last update follows fromzk+1:= (1/2)(2xk+1− zk+1/2) + (1/2)zk= xk+1− (1/2)(2xk+1/2− zk) + (1/2)zk= zk+ xk+1− xk+1/2•can consider xk+1− xk+1/2as a residual•zkis running sum of residualsDouglas-Rachford splitting 6Douglas-Rachford algorithm•many ways to rewrite/rearrange D-R algorithm•equivalent to many other algorithms; often not obvious•need very little: A, B maximal monotone; solution exists•A and B are handled separately (via RAand RB); they are ‘uncoupled’Douglas-Rachford splitting 7Alternating direction method of multipliersto minimize f(x) + g(x), we solve 0 ∈ ∂f (x) + ∂g(x)with A(x) = ∂g(x), B(x) = ∂f(x), D-R isxk+1/2:= argminxf(x) + (1/2λ)kx − zkk22zk+1/2:= 2xk+1/2− zkxk+1:= argminxg(x) + (1/2λ)kx − zk+1/2k22zk+1:= zk+ xk+1− xk+1/2a sp ec ia l case of the alternating direction method of multipliers (ADMM)Douglas-Rachford splitting 8Constrained optimization•constrained convex problem:minimize f(x)subject to x ∈ C•take B(x) = ∂f(x) and A(x) = ∂IC(x) = NC(x)•so RB(z) = proxf(z) and RA(z) = ΠC(z)•D-R isxk+1/2:= proxf(zk)zk+1/2:= 2xk+1/2− zkxk+1:= ΠC(zk+1/2)zk+1:= zk+ xk+1− xk+1/2Douglas-Rachford splitting 9Dykstra’s alternating projections•find a point in the intersection of convex sets C, D•D-R gives algorithmxk+1/2:= ΠC(zk)zk+1/2:= 2xk+1/2− zkxk+1:= ΠD(zk+1/2)zk+1:= zk+ xk+1− xk+1/2•this is Dykstra’s alternating projections algorithm•much faster than classical alternating projections(e.g., for C, D polyhedral, converges in finite number of steps)Douglas-Rachford splitting 10Positive semidefinite matrix completion•some entries of matrix in Snknown; find values for others so completedmatrix is PSD•C = Sn+, D = {X | Xij= Xknownij, (i, j) ∈ K}•projection onto C: find eigendecomposition X =Pni=1λiqiqTi; thenΠC(X) =nXi=1max{0, λi}qiqTi•projection onto D: set specified entries to known valuesDouglas-Rachford splitting 11Positive semidefinite matrix completionspecific example: 50 × 50 matrix missing about half of its entries•initialize Z0= 0Douglas-Rachford splitting 12Positive semidefinite matrix completion20 40 60 80 10010−410−2100102iteration kkXk+1− Xk+1/2kF•blue: alternating projections; red: D-R•Xk+1/2∈ C, Xk+1∈ DDouglas-Rachford splitting 13Outline1 Operator splitting2 Douglas-Rachford splitting3 Consensus optimizationConsensus optimization 14Consensus optimization•want to minimizePNi=1fi(x)•rewrite as consensus problemminimizePNi=1fi(xi)subject to x ∈ C = {(x1, . . . , xN) | x1= · · · = xN}•D-R consensus optimization:xk+1/2:= proxf(zk)zk+1/2:= 2xk+1/2− zkxk+1:= ΠC(zk+1/2)zk+1:= zk+ xk+1− xk+1/2Consensus optimization 14Douglas-Rachford consensus•xk+1/2-update splits into N separate (parallel) problems:xk+1/2i:= argminzifi(zi) + (1/2λ)kzi− zkik22, i = 1, . . . , N•xk+1-update is averaging:xk+1i:= zk+1/2= (1/N)NXi=1zk+1/2i, i = 1, . . . , N•zk+1-update becomeszk+1i= zki+zk+1/2− xk+1/2i= zki+ 2xk+1/2− zk− xk+1/2i= zki+ (xk+1/2− xk+1/2i) + (xk+1/2− zk)•taking average of last equation, we get zk+1= xk+1/2Consensus optimization 15Douglas-Rachford consensus•renaming xk+1/2as xk+1, D-R consensus becomesxk+1i:= proxfi(zki)zk+1i:= zki+ (xk+1− xk+1i) + (xk+1− xk)•subsystem (local) state: x, zi, xi•gather xi’s to compute x, which is th en scatteredConsensus optimization 16Distributed QP•we use D-R consensus to solve QPminimize f(x) =PNi=1(1/2)kAix − bik22subject to Fix ≤ gi, i = 1, . . . , Nwith variable x ∈ Rn•each of N proc essors will handle an objective term, block of constraints•coordinate N QP solvers to solve big QPConsensus optimization 17Distributed QP•D-R consensus algorithm isxk+1i:= argminFixi≤gi(1/2)kAixi− bik22+ (1/2λ)kxi− zkik22zk+1i:= zki+ (xk+1− xk+1i) + (xk+1− xk),•first step is N parallel QP solves•second step gives coordination, to solve large problem•inequality constraint residual is 1T(F xk− g)+Consensus optimization 18Distributed QPexample with n = 100 variables, N = 10 subsystems10 20 30 40 5010−210010210 20 30 40 50500100015002000iteration k1T(F xk− g)+f(xk)Consensus optimization