Forward-backward envelope for the sum of two nonconvex functions: Further properties and nonmonotone line-search algorithms

Abstract

We propose ZeroFPR, a nonmonotone linesearch algorithm for minimizing the sum of two nonconvex functions, one of which is smooth and the other possibly nonsmooth. 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 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 ZeroFPR. Our theoretical results are backed up by promising numerical simulations. On large-scale problems, by computing linesearch directions using limited-memory quasi-Newton updates our algorithm greatly outperforms FBS and its accelerated variant (AFBS).

References in corpus (3)

• The rate of convergence of Nesterov's accelerated forward-backward method is actually faster than $1/k^2$
• Splitting methods with variable metric for KL functions
• Forward-backward quasi-Newton methods for nonsmooth optimization problems

Cited by in corpus (32)

• Douglas-Rachford splitting and ADMM for nonconvex optimization: tight convergence results
• Embedded nonlinear model predictive control for obstacle avoidance using PANOC
• A Bregman forward-backward linesearch algorithm for nonconvex composite optimization: superlinear convergence to nonisolated local minima
• Constrained composite optimization and augmented Lagrangian methods
• SuperMann: a superlinearly convergent algorithm for finding fixed points of nonexpansive operators
• On the acceleration of forward-backward splitting via an inexact Newton method
• Proximal Gradient Algorithms under Local Lipschitz Gradient Continuity: A Convergence and Robustness Analysis of PANOC
• Block-coordinate and incremental aggregated proximal gradient methods for nonsmooth nonconvex problems
• Proximal Gradient Algorithms: Applications in Signal Processing
• Catalyst Acceleration for First-order Convex Optimization: from Theory to Practice
• Douglas-Rachford splitting and ADMM for nonconvex optimization: Accelerated and Newton-type linesearch algorithms
• Proximal gradient methods beyond monotony
• Binary Control Pulse Optimization for Quantum Systems
• Fixed-Time Gradient Flows for Solving Constrained Optimization: A Unified Approach
• Multi-block Bregman proximal alternating linearized minimization and its application to orthogonal nonnegative matrix factorization
• Uncertainty-aware demand management of water distribution networks in deregulated energy markets
• Projected gradient descent accumulates at Bouligand stationary points
• A Stochastic Extra-Step Quasi-Newton Method for Nonsmooth Nonconvex Optimization
• Local Convergence of Proximal Splitting Methods for Rank Constrained Problems
• Implicit augmented Lagrangian and generalized optimization
• A new envelope function for nonsmooth DC optimization
• PANTR: A proximal algorithm with trust-region updates for nonconvex constrained optimization
• Prediction-Correction for Nonsmooth Time-Varying Optimization via Forward-Backward Envelopes
• Three Operator Splitting with a Nonconvex Loss Function
• A quadratically convergent proximal algorithm for nonnegative tensor decomposition
• SPIRAL: A superlinearly convergent incremental proximal algorithm for nonconvex finite sum minimization
• An interior proximal gradient method for nonconvex optimization
• A trust region-type normal map-based semismooth Newton method for nonsmooth nonconvex composite optimization
• Proximal Dogleg Opportunistic Majorization for Nonconvex and Nonsmooth Optimization
• An Envelope for Davis-Yin Splitting and Strict Saddle Point Avoidance
• A mirror inertial forward-reflected-backward splitting: Global convergence and linesearch extension beyond convexity and Lipschitz smoothness
• A linesearch-type normal map-based semismooth Newton method for nonsmooth nonconvex composite optimization