Distributed Optimization:Analysis and Synthesis via CircuitsStephen BoydProf. S. Boyd, EE364b, Stanford UniversityOutline• canonical form for distributed convex optimization• circuit intepretation• primal decomposition• dual decomposition• prox decomposition• momentum termsProf. S. Boyd, EE364b, Stanford University 1Distributed convex optimization problem•convex optimization problem partitioned into coupled subsystems• divide variables, constraints, objective terms into two groups– local variables, constraints, objective terms appear in only onesubsystem– complicating variables, constraints, objective terms appear in morethan one subsystem• describe by hypergraph– subsystems are nodes– complicating variables, constraints, objective terms are hyperedgesProf. S. Boyd, EE364b, Stanford University 2Conditional separability•separable problem: can solve by solving subsystems separately, e.g.,minimize f1(x1) + f2(x2)subject to x1∈ C1, x2∈ C2• in distributed problem, two subsystems are conditionally separable ifthey are separable when all other variables are fixed• two subsystems not connected by a net are conditionally separable• cf. conditional independence in Bayes net: two var ia bl es not connectedby hyperedge are conditi ona ll y independen t, given all other variablesProf. S. Boyd, EE364b, Stanford University 3Examples•minimize f1(z1, x) + f2(z2, x), with variables z1, z2, x– x is the complicating variable; when fixed, problem is separable– z1, z2are private or local variables– x is a public or interface or boundary variable between the twosubproblems– hypergraph: two nodes connected by an edge• optimal control problem– state is the complicating variable between past and future– hypergraph: simple chainProf. S. Boyd, EE364b, Stanford University 4Transformation to standard form•introduce slack variables for complicating inequality constraints• introduce local copies of complicating vari ab le s• implicitly minimize over private variables (preserves convexity)• represent local constraints in domain of objective term• we are left with– all variables are public, associated with a single node– all constraints are consistency constraints, i.e., equality of two ormore variablesProf. S. Boyd, EE364b, Stanford University 5Example• minimize f1(z1, x) + f2(z2, x), with variables z1, z2, x• introduce local copies of complicating vari ab le :minimize f1(z1, x1) + f2(z2, x2)subject to x1= x2• eliminate local variables:minimize˜f1(x1) +˜f2(x2)subject to x1= x2with˜fi(xi) = infzifi(zi, xi)Prof. S. Boyd, EE364b, Stanford University 6General form• n subsystems with variables x1, . . . , xn• m nets with common variable values z1, . . . , zmminimizePni=1fi(xi)subject to xi= Eiz, i = 1, . . . , n• matrices Eigive netlist or hypergraph(row k is ep, where kth entry of xiis in net p)Prof. S. Boyd, EE364b, Stanford University 7Optimality conditions•introduce dual variable yiassociated with xi= Eiz• optimality conditions are∇fi(xi) = yi(subsystem relations)xi= Eiz (primal feasibility)Pni=1ETiyi= 0 (dual feasibility)(for nondifferentiable case,replace ∇fi(xi) with gi∈ ∂fi(xi))• primal condition: (primal) variables on each net are the same• dual condition: dual variables on each net sum to zeroProf. S. Boyd, EE364b, Stanford University 8Circuit interpretation (primal/voltages)PSfrag• subsystems are (grounded) nonlinear resistors• nets are wires (nets); consistency constraint is KVL• zjis voltage on net j• xiis vector of pin voltages for resistor iProf. S. Boyd, EE364b, Stanford University 9Circuit interpretation (dual/currents)•yiis vector of currents entering resistor i• dual feasibility is KCL: sum of currents leaving net j i s zero• V-I characteristic for resistor i: yi= ∇fi(xi)• fi(x) is content function of resistor i• convexity of fiis incremental passivity of resistor i:(xi− ˜xi)T(yi− ˜yi) ≥ 0, yi= ∇fi(xi), ˜yi= ∇fi(˜xi)• optimality conditions are exactly the circuit equationsProf. S. Boyd, EE364b, Stanford University 10Decomposition methods•solve distributed problem iteratively– algorithm state maintained in nets• each step consists of– (parallel) update of subsystem primal and dual var i ab le s, based onlyon adjacent net states– update of the net states, based only on adj ace nt subsystem s• algorithms differ in– interface to s ub sys tems– state and updateProf. S. Boyd, EE364b, Stanford University 11Primal decompositionrepeat1. dis tri bu te net variables to adjacent subsystemsxi:= Eiz2. optim i ze subsystem s (separately )solve su bprob l ems to evaluate yi= ∇fi(xi)3. coll ect and sum dual variables for each netw :=Pni=1ETiyi4. update net variablesz := z − αkw.• step f actor αkchosen by standard gradient or subgradient rulesProf. S. Boyd, EE364b, Stanford University 12Primal decomposition•algorithm state i s net variable z (net v olt ages )• w =Pni=1ETiyiis du al residu al (net current residua ls )• primal feasibility maintained; dual feasibility approached in limit• subsystems are voltage controlled:– voltage xiis ass erte d at subsystem pins– pin currents yiare then foundProf. S. Boyd, EE364b, Stanford University 13Circuit interpretation•connect capacitor to each net; system relaxes to equilibrium• forward Eul er update is primal decomposition• incremental passivity implies convergence to equilibriumzx1x2x3Prof. S. Boyd, EE364b, Stanford University 14Dual decompositioninitialize yiso thatPni=1ETiyi= 0(dual variables sum t o zero on each net)repeat1. optim i ze subsystem s (separately )find xiwith ∇fi(xi) = yi, i.e., mi n im iz e fi(xi) − yTixi2. coll ect and average primal variables over each netz := (ETE)−1ETx3. update dual variablesy := y − αk(x − Ez)Prof. S. Boyd, EE364b, Stanford University 15Dual decomposition•algorithm state i s dual variable y• x − Ez is consistency residual• dual feasibility maintained; primal feasibility approached in limit• subsystems are current controlled:– pin currents yiare asse rted– pin voltages xiare then foundProf. S. Boyd, EE364b, Stanford University 16Circuit interpretation•connect inductor to each pin; system relaxes to equilibrium• forward Eul er update is dual decomposition• incremental passivity implies convergence to equilibriumzx1x2x3↑ y1↑ y2↑ y3Prof. S. Boyd, EE364b, Stanford University 17Prox(imal) interface•prox operator:Pρ(y, ¯x) =