Tutte Colloquium - Jonathan Eckstein

Title: The ADMM:  Past, Present, and Future

Abstract: Over the past 15 years, the alternating direction method of multipliers (ADMM) has become a standard optimization method.  This talk will cover the origins of the ADMM, its subsequent development, and what to expect in the future.

The origins of the ADMM are somewhat unusual in that it was discovered computationally before it was analyzed.  Its convergence analysis is also noteworthy because, while the ADMM may outwardly appear to be a dual ascent method, the natural analyses center on reducing the distance to certain fixed points combining primal and dual variables.  The nature of these analyses explains the difficulty of proving convergence of natural variants of the algorithm that change the penalty parameter between iterations or involve sums of more than two functions.

We will also cover some currently known variations on the ADMM and the problem formulation features that tend to distinguish between successful and unsuccessful applications.  Finally, the talk will briefly address what we may expect for the future and what other operator splitting methods might become viable members of the optimization toolbox.