Splitting Envelopes: Accelerated Second-Order Proximal Methods
Professor Panagiotis Patrinos
We show that operator splitting techniques for solving optimization problems, such as Forward Backward Splitting (FBS) and Douglas Rachford Splitting (DRS), can be interpreted as scaled gradient methods applied to the unconstrained minimization of a continuously differentiable function. Inspired by the connection between the proximal minimization algorithm and the Moreau envelope, we call these functions Forward-Backward and Douglas-Rachford envelope. The new interpretation paves the way of devising new algorithms for composite and separable nonsmooth optimization problems, by applying any well known method for unconstrained smooth optimization. We present two specific applications of the proposed theory: First, a Forward-Backward Newton method with asymptotic quadratic convergence rate. Second, we derive complexity estimates for DRS and an accelerated version of DRS.
Panagiotis (Panos) Patrinos is an Assistant Professor at IMT Institute for Advanced Studies, Lucca, Italy, in Dynamical Systems, Control and Optimization. He completed his graduate studies at the National Technical University of Athens (NTUA), Greece in 2010, obtaining a PhD in Systems, Control and Optimization and a MS in Applied Mathematics (2005). His research interests lie in mathematical optimization and its application to control systems.