On the acceleration of forward-backward splitting via an inexact Newton method

Abstract

We propose a Forward-Backward Truncated-Newton method (FBTN) for minimizing the sum of two convex functions, one of which smooth. Unlike other proximal Newton methods, our approach does not involve the employment of variable metrics, but is rather based on a reformulation of the original problem as the unconstrained minimization of a continuously differentiable function, the forward-backward envelope (FBE). We introduce a generalized Hessian for the FBE that symmetrizes the generalized Jacobian of the nonlinear system of equations representing the optimality conditions for the problem. This enables the employment of conjugate gradient method (CG) for efficiently solving the resulting (regularized) linear systems, which can be done inexactly. The employment of CG prevents the computation of full (generalized) Jacobians, as it requires only (generalized) directional derivatives. The resulting algorithm is globally (subsequentially) convergent, $Q$-linearly under an error bound condition, and up to $Q$-superlinearly and $Q$-quadratically under regularity assumptions at the possibly non-isolated limit point.

References in corpus (5)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Forward-backward quasi-Newton methods for nonsmooth optimization problems
• Forward-backward envelope for the sum of two nonconvex functions: Further properties and nonmonotone line-search algorithms
• A quasi-Newton proximal splitting method
• Forward-backward truncated Newton methods for convex composite optimization

Cited by in corpus (11)

• A Bregman forward-backward linesearch algorithm for nonconvex composite optimization: superlinear convergence to nonisolated local minima
• QPALM: A Proximal Augmented Lagrangian Method for Nonconvex Quadratic Programs
• 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
• Douglas-Rachford splitting and ADMM for nonconvex optimization: Accelerated and Newton-type linesearch algorithms
• Multi-block Bregman proximal alternating linearized minimization and its application to orthogonal nonnegative matrix factorization
• PANTR: A proximal algorithm with trust-region updates for nonconvex constrained optimization
• Gauss-Newton meets PANOC: A fast and globally convergent algorithm for nonlinear optimal control
• A quadratically convergent proximal algorithm for nonnegative tensor decomposition
• SPIRAL: A superlinearly convergent incremental proximal algorithm for nonconvex finite sum minimization