Accelerated Douglas-Rachford splitting and ADMM for structured nonconvex optimization
Abstract:
Although originally designed and analyzed for solving convex problems, the Alternating Direction Method of Multipliers (ADMM) and its close relatives, Douglas-Rachford Splitting (DRS) and Paceman-Rachford Splitting, have been observed to perform remarkably when applied to certain classes of structured nonconvex optimization problems. However, partial global convergence results in the nonconvex setting have only recently emerged. The goal of this work is two-fold: First, we show how the Douglas-Rachford Envelope (DRE), introduced by the authors in 2014, can be employed to devise global convergence guarantees for ADMM, DRS, PRS and nonconvex problems under less restrictive conditions, larger prox stepsizes and over-relaxation parameters than what was previously known. Furthermore, exploiting properties of the DRE, we propose a new globally convergent algorithmic scheme that greatly accelerates convergence. In fact, under mild assumptions, the algorithm is shown to converge superlinearly by performing exactly the same kind of computations as ADMM, DRS, PRS.
Biography:
Panagiotis (Panos) Patrinos is assistant professor at the Department of Electrical Engineering (ESAT) of KU Leuven, Belgium since 2015. During fall/winter 2014 he held a visiting assistant professor position at Stanford University. He received his PhD in Control and Optimization, M.S. in Applied Mathematics and M.Eng. from National Technical University of Athens, in 2010, 2005 and 2003, respectively. After his PhD he held postdoc positions at the University of Trento and IMT Lucca, Italy, where he became an assistant professor in 2012. His current research interests are in the theory and algorithms of structured convex and nonconvex optimization and applications in control, machine learning and signal processing.