Alternating Direction Method of Multipliers (ADMM)
Post date: Oct 30, 2015 12:30:11 AM
1) Dual descent applies gradient descent on the dual problem [1].
s.t.
+ // primal minimization
+ // dual update
where is the Lagrangian multiplier and is the gradient update step side. Note that the celebrated "shadow price" is the optimal Lagrangian multiplier, such that the unconstrained, but priced, problem and the constrained problem yield the same solution, provided that strong duality holds.
=> Dual decomposition: if the objective is separable, then the primal minimization is also separable, coupled only by the multiplier.
2) Method of multipliers (MoM): Add an additional quadratic term (augmenting the Lagrangian) to modify the primal minimization so that the dual update is more robust.
Limitation: The primal minimization is no longer separable due to the quadratic term. (Without the quadratic term, the derivative wrt a scalar variable (in a vector one) does not contain others)
3) ADMM uses alternating (update a variable while keeping the others fixed) Gauss-Seidel (always use the latest fixed variable) update in the primal minimization to gracefully handle the coupling induced by the MoM.