SuperMann: a superlinearly convergent algorithm for finding fixed points of nonexpansive operators

Abstract

Operator splitting techniques have recently gained popularity in convex optimization problems arising in various control fields. Being fixed-point iterations of nonexpansive operators, such methods suffer many well known downsides, which include high sensitivity to ill conditioning and parameter selection, and consequent low accuracy and robustness. As universal solution we propose SuperMann, a Newton-type algorithm for finding fixed points of nonexpansive operators. It generalizes the classical Krasnosel'skii-Mann scheme, enjoys its favorable global convergence properties and requires exactly the same oracle. It is based on a novel separating hyperplane projection tailored for nonexpansive mappings which makes it possible to include steps along any direction. In particular, when the directions satisfy a Dennis-Moré condition we show that SuperMann converges superlinearly under mild assumptions, which, surprisingly, do not entail nonsingularity of the Jacobian at the solution but merely metric subregularity. As a result, SuperMann enhances and robustifies all operator splitting schemes for structured convex optimization, overcoming their well known sensitivity to ill conditioning.

References in corpus (3)

• 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
• Fast ADMM for Semidefinite Programs with Chordal Sparsity

Cited by in corpus (7)

• Anderson Accelerated Douglas-Rachford Splitting
• A Bregman forward-backward linesearch algorithm for nonconvex composite optimization: superlinear convergence to nonisolated local minima
• Douglas-Rachford splitting and ADMM for nonconvex optimization: Accelerated and Newton-type linesearch algorithms
• A Stochastic Operator Framework for Optimization and Learning with Sub-Weibull Errors
• QOCO: A Quadratic Objective Conic Optimizer with Custom Solver Generation
• SPIRAL: A superlinearly convergent incremental proximal algorithm for nonconvex finite sum minimization
• Asynchronous Distributed Learning with Quantized Finite-Time Coordination