Forward–backward quasi-Newton methods for nonsmooth optimization problems

By Lorenzo Stella, Andreas Themelis, Panagiotis Patrinos. 2016

175 citations recorded by the source corpus.

The forward–backward splitting method (FBS) for minimizing a nonsmooth composite function can be interpreted as a (variable-metric) gradient method over a continuously differentiable function which we call forward–backward envelope (FBE). This allows to extend algorithms for smooth unconstrained optimization and apply them to nonsmooth (possibly constrained) problems. Since the FBE can be computed by simply evaluating forward–backward steps, the resulting methods rely on a similar black-box oracle as FBS. We propose an algorithmic scheme that enjoys the same global convergence properties of FBS when the problem is convex, or when the objective function possesses the Kurdyka–Łojasiewicz property at its critical points. Moreover, when using quasi-Newton directions the proposed method achieves superlinear convergence provided that usual second-order sufficiency conditions on the FBE hold at the limit point of the generated sequence. Such conditions translate into milder requirements on the original function involving generalized second-order differentiability. We show that BFGS fits our framework and that the limited-memory variant L-BFGS is well suited for large-scale problems, greatly outperforming FBS or its accelerated version in practice, as well as ADMM and other problem-specific solvers. The analysis of superlinear convergence is based on an extension of the Dennis and Moré theorem for the proposed algorithmic scheme.

Subfields: Computational Mechanics, Computational Theory and Mathematics, Numerical Analysis

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computational Theory and Mathematics

In Numerical Analysis

Citations in the corpus

Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition (2016, methodology): “While the first methods that achieved this remarkable property required a memory of previous gradient values, the stochastic variance-reduced gradient (SVRG) method of Johnson and Zhang [2013] does not have this drawback. Gong and Ye [2014] show that SVRG has a linear convergence rate without SC und”
A Stochastic Semismooth Newton Method for Nonsmooth Nonconvex Optimization (2018, background): “Let us mention that an alternative globalization is analyzed in [61, 80] where the authors propose the so-called forward-backward envelope (FBE) as a smooth merit function for problem (1.”