Frugal Splitting Operators: Representation, Minimal Lifting, and Convergence

DOI10.1137/22M1531105MaRDI QIDQ6402862zbMATH OpenFDO

Authors Martin Morin, Sebastian Banert, Pontus Giselsson

Publication date 22 June 2022

Full work available at URL https://doi.org/10.1137/22M1531105

Mathematics Subject Classification ID

Fixed-point theorems (47H10) Set-valued and variational analysis (49J53) Numerical methods for variational inequalities and related problems (65K15) Convex programming (90C25)

Abstract: We consider frugal splitting operators for finite sum monotone inclusion problems, i.e., splitting operators that use exactly one direct or resolvent evaluation of each operator of the sum. A novel representation of these operators in terms of what we call a generalized primal-dual resolvent is presented. This representation reveals a number of new results regarding lifting numbers, existence of solution maps, and parallelizability of the forward and backward evaluations. We show that the minimal lifting is $n-1-f$ where $n$ is the number of monotone operators and $f$ is the number of direct evaluations in the splitting. Furthermore, we show that this lifting number is only achievable as long as the first and last evaluations are resolvent evaluations. In the case of frugal resolvent splitting operators, these results are the same as the results of Ryu and Malitsky--Tam. The representation also enables a unified convergence analysis and we present a generally applicable theorem for the convergence and Fej'er monotonicity of fixed point iterations of frugal splitting operators with cocoercive direct evaluations. We conclude by constructing a new convergent and parallelizable frugal splitting operator with minimal lifting.

Recommendations

• Resolvent splitting for sums of monotone operators with minimal lifting
• The geometry of monotone operator splitting methods
• Primal-dual splitting algorithm for solving inclusions with mixtures of composite, Lipschitzian, and parallel-sum type monotone operators
• Convergence Rates for Projective Splitting
• A unified splitting algorithm for composite monotone inclusions

Cited in

(1)

• Forward-backward algorithms devised by graphs

This page was built for publication: Frugal Splitting Operators: Representation, Minimal Lifting, and Convergence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6402862)