Skip to Main content Skip to Navigation
Journal articles

A Smooth Primal-Dual Optimization Framework for Nonsmooth Composite Minimization

Abstract : We propose a new first-order primal-dual optimization framework for a convex optimization template with broad applications. Our optimization algorithms feature optimal convergence guarantees under a variety of common structure assumptions on the problem template. Our analysis relies on a novel combination of three classic ideas applied to the primal-dual gap function: smoothing, acceleration, and homotopy. The algorithms due to the new approach achieve the best known convergence rate results, in particular when the template consists of only non-smooth functions. We also outline a restart strategy for the acceleration to significantly enhance the practical performance. We demonstrate relations with the augmented Lagrangian method and show how to exploit the strongly convex objectives with rigorous convergence rate guarantees. We provide numerical evidence with two examples and illustrate that the new methods can outperform the state-of-the-art, including Chambolle-Pock, and the alternating direction method-of-multipliers algorithms.
Document type :
Journal articles
Complete list of metadata
Contributor : TelecomParis HAL Connect in order to contact the contributor
Submitted on : Friday, September 13, 2019 - 4:59:18 PM
Last modification on : Wednesday, November 3, 2021 - 6:18:40 AM


  • HAL Id : hal-02287465, version 1


Quoc Tran-Dinh, Olivier Fercoq, Volkan Cevher. A Smooth Primal-Dual Optimization Framework for Nonsmooth Composite Minimization. SIAM Journal on Optimization, Society for Industrial and Applied Mathematics, 2018, 28 (1), pp.96-134. ⟨hal-02287465⟩



Record views