The alternating direction method of multipliers (ADMM) is an iterative algorithm for convex optimization that embeds a Gaussian-Seidel decomposition into each iteration of the augmented Lagrangian method (ALM). The algorithm dates back to the early 1980’s and has recently enjoyed growing popularity due to its applicability to a broad spectrum of application such as partial differential equations, mechanics, image processing, machine learning and so on. In addition, the algorithm can be relatively easy adapted for parallel and distributed processing over a network of computing nodes, making it a very attractive solution for modern big data related problems.
The classical ADMM algorithm employs two blocks of variables that are alternately updated, and it's convergence was proved 40 year ago. However, when the objective function is not separable across the variables, the convergence of the ADMM is still an open question even when the objective function is convex. For some problems it would be computationally beneficial to extend the classical ADMM directly to the case of a multi-block convex minimization, but such an extension fails to converge even when solving a simple square system of linear equations. There are several proposals to overcome the drawback, ranging from solutions that restrict the range of original problems being solved, add additional cost in each step of computation, or limit the stepsize in updating the Lagrange multipliers to algorithms that modify cyclic ADMM.
In this talk we present classical two-block ADMM and its extensions to multi-block and coupled convex optimization problems. We analyze the convergence of the classical algorithm and randomly permuted (RP)-ADMM, which is a modification of cyclic multi-block ADMM that mitigates the divergence problem without slowing down the performance of ADMM.
Current 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996
