Forward-Backward Envelope for the Sum of Two Nonconvex Functions: Further Properties and Nonmonotone Linesearch Algorithms
Authors:
- Andreas ThemelisATAndreas Themelis
- Lorenzo StellaLSLorenzo Stella
- Panagiotis PatrinosPPPanagiotis Patrinos
- 1 January 2018
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Optimization
- Vol. 28 (3) , 2274-2303
Abstract
We propose \sf ZeroFPR, a nonmonotone linesearch algorithm for minimizing the sum of two nonconvex functions, one of which is smooth and the other possibly nonsmooth. \sf ZeroFPR is the first algorithm that, despite being fit for fully nonconvex problems and requiring only the black-box oracle of forward-backward splitting (FBS)---namely evaluations of the gradient of the smooth term and of the proximity operator of the nonsmooth one---achieves superlinear convergence rates under mild assumptions at the limit point when the linesearch directions satisfy a Dennis--Moré condition, and we show that this is the case for Broyden's quasi-Newton directions. Our approach is based on the forward-backward envelope (FBE), an exact and strictly continuous penalty function for the original cost. Extending previous results we show that, despite being nonsmooth for fully nonconvex problems, the FBE still enjoys favorable first- and second-order properties which are key for the convergence results of \sf ZeroFPR. Our the...Keywords
All Related Versions
Funding Information
- Fonds De La Recherche Scientifique - FNRS and Fonds Wetenschappelijk Onderzoek (30468160 (SeLMA))
- Fonds Wetenschappelijk Onderzoek (G086518N, G086318N)
- KU Leuven (StG/15/043)
This publication has 42 references indexed in Scilit:
- Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward–backward splitting, and regularized Gauss–Seidel methodsMathematical Programming, 2011
- Iteratively reweighted least squares minimization for sparse recoveryCommunications on Pure and Applied Mathematics, 2009
- On the convergence of the proximal algorithm for nonsmooth functions involving analytic featuresMathematical Programming, 2007
- $rm K$-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse RepresentationIEEE Transactions on Signal Processing, 2006
- On gradients of functions definable in o-minimal structuresAnnales de l'institut Fourier, 1998
- Sur la géométrie semi- et sous- analytiqueAnnales de l'institut Fourier, 1993
- First- and second-order epi-differentiability in nonlinear programmingTransactions of the American Mathematical Society, 1988
- Updating quasi-Newton matrices with limited storageMathematics of Computation, 1980
- A characterization of superlinear convergence and its application to quasi-Newton methodsMathematics of Computation, 1974
- A class of methods for solving nonlinear simultaneous equationsMathematics of Computation, 1965