On the Acceleration of Forward-Backward Splitting via an Inexact Newton Method

Andreas Themelis (), Masoud Ahookhosh () and Panagiotis Patrinos ()
Additional contact information
Andreas Themelis: KU Leuven, Department of Electrical Engineering (ESAT-STADIUS)
Masoud Ahookhosh: KU Leuven, Department of Electrical Engineering (ESAT-STADIUS)
Panagiotis Patrinos: KU Leuven, Department of Electrical Engineering (ESAT-STADIUS)

Chapter Chapter 15 in Splitting Algorithms, Modern Operator Theory, and Applications, 2019, pp 363-412 from Springer

Abstract: 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.

Keywords: Forward-backward splitting; Linear Newton approximation; Truncated-Newton method; Backtracking linesearch; Error bound; Superlinear convergence; 49J52; 49M15; 90C06; 90C25; 90C30 (search for similar items in EconPapers)
Date: 2019
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-030-25939-6_15

Ordering information: This item can be ordered from
http://www.springer.com/9783030259396

DOI: 10.1007/978-3-030-25939-6_15

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().