Alternating Direction Method of Multipliers
(Redirected from ADMM)
Jump to navigation
Jump to search
An Alternating Direction Method of Multipliers is an augmented Lagrangian algorithm that ...
- AKA: ADMM.
- See: Basis Pursuit, Jacobi Method, Douglas-Rachford Splitting Algorithm, Proximal Point Algorithm, Constrained Optimization Algorithm.
References
2015
- (Wikipedia, 2015) ⇒ http://en.wikipedia.org/wiki/Augmented_Lagrangian_method#Alternating_direction_method_of_multipliers Retrieved:2015-11-5.
- The alternating direction method of multipliers (ADMM) is a variant of the augmented Lagrangian scheme that uses partial updates for the dual variables. This method is often applied to solve problems such as [math]\displaystyle{ \min_x f(x) + g(x). }[/math] This is equivalent to the constrained problem [math]\displaystyle{ \min_{x,y} f(x) + g(y), \quad \text{subject to}\quad x = y. }[/math] Though this change may seem trivial, the problem can now be attacked using methods of constrained optimization (in particular, the augmented Lagrangian method), and the objective function is separable in x and y. The dual update requires solving a proximity function in x and y at the same time; the ADMM technique allows this problem to be solved approximately by first solving for x with y fixed, and then solving for y with x fixed. Rather than iterate until convergence (like the Jacobi method), the algorithm proceeds directly to updating the dual variable and then repeating the process. This is not equivalent to the exact minimization, but surprisingly, it can still be shown that this method converges to the right answer (under some assumptions). Because of this approximation, the algorithm is distinct from the pure augmented Lagrangian method.
The ADMM can be viewed as an application of the Douglas-Rachford splitting algorithm, and the Douglas-Rachford algorithm is in turn an instance of the Proximal point algorithm; details can be found here. There are several modern software packages that solve Basis pursuit and variants and use the ADMM; such packages include YALL1 (2009), SpaRSA (2009) and SALSA (2009).
- The alternating direction method of multipliers (ADMM) is a variant of the augmented Lagrangian scheme that uses partial updates for the dual variables. This method is often applied to solve problems such as [math]\displaystyle{ \min_x f(x) + g(x). }[/math] This is equivalent to the constrained problem [math]\displaystyle{ \min_{x,y} f(x) + g(y), \quad \text{subject to}\quad x = y. }[/math] Though this change may seem trivial, the problem can now be attacked using methods of constrained optimization (in particular, the augmented Lagrangian method), and the objective function is separable in x and y. The dual update requires solving a proximity function in x and y at the same time; the ADMM technique allows this problem to be solved approximately by first solving for x with y fixed, and then solving for y with x fixed. Rather than iterate until convergence (like the Jacobi method), the algorithm proceeds directly to updating the dual variable and then repeating the process. This is not equivalent to the exact minimization, but surprisingly, it can still be shown that this method converges to the right answer (under some assumptions). Because of this approximation, the algorithm is distinct from the pure augmented Lagrangian method.