Splitting Envelopes: Accelerated Second-Order Proximal Methods

Professor Panagiotis Patrinos
Assistant Professor, IMT Institute for Advanced Studies, Lucca, Italy
Given on: Oct. 2nd, 2014
Time: 4:15 - 5:15pm
Venue: Packard 101


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.