FRUGAL SPLITTING OPERATORS : REPRESENTATION, MINIMAL LIFTING, AND CONVERGENCE
Morin, Martin LU ; Banert, Sebastian LU and Giselsson, Pontus LU
(2024)
In SIAM Journal on Optimization
34(2).
p.1595-1621
- Abstract
We investigate frugal splitting operators for finite sum monotone inclusion problems. These operators utilize exactly one direct or resolvent evaluation of each operator of the sum, and the splitting operator's output is dictated by linear combinations of these evaluations' inputs and outputs. To facilitate analysis, we introduce a novel representation of frugal splitting operators via a generalized primal-dual resolvent. The representation is characterized by an index and four matrices, and we provide conditions on these that ensure equivalence between the classes of frugal splitting operators and generalized primal-dual resolvents. Our representation paves the way for new results regarding lifting numbers and the development of a... (More)
We investigate frugal splitting operators for finite sum monotone inclusion problems. These operators utilize exactly one direct or resolvent evaluation of each operator of the sum, and the splitting operator's output is dictated by linear combinations of these evaluations' inputs and outputs. To facilitate analysis, we introduce a novel representation of frugal splitting operators via a generalized primal-dual resolvent. The representation is characterized by an index and four matrices, and we provide conditions on these that ensure equivalence between the classes of frugal splitting operators and generalized primal-dual resolvents. Our representation paves the way for new results regarding lifting numbers and the development of a unified convergence analysis for frugal splitting operator methods, contingent on the directly evaluated operators being cocoercive. The minimal lifting number is n - 1 - f where n is the number of monotone operators and f is the number of direct evaluations in the splitting. Notably, this lifting number is achievable only if the first and last operator evaluations are resolvent evaluations. These results generalize the minimal lifting results by Ryu and by Malitsky and Tam that consider frugal resolvent splittings. Building on our representation, we delineate a constructive method to design frugal splitting operators, exemplified in the design of a novel, convergent, and parallelizable frugal splitting operator with minimal lifting.
(Less)
- author
- Morin, Martin
LU
; Banert, Sebastian
LU
and Giselsson, Pontus
LU
- organization
- publishing date
- 2024-06
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- fixed point iterations, frugal splitting operators, minimal lifting, monotone inclusion, representation
- in
- SIAM Journal on Optimization
- volume
- 34
- issue
- 2
- pages
- 27 pages
- publisher
- Society for Industrial and Applied Mathematics
- external identifiers
-
- scopus:85194912090
- ISSN
- 1052-6234
- DOI
- 10.1137/22M1531105
- language
- English
- LU publication?
- yes
- id
- 8f94d706-743c-40f2-a464-dd170cb13251
- date added to LUP
- 2024-08-21 14:19:41
- date last changed
- 2024-08-21 14:19:52
@article{8f94d706-743c-40f2-a464-dd170cb13251,
abstract = {{<p>We investigate frugal splitting operators for finite sum monotone inclusion problems. These operators utilize exactly one direct or resolvent evaluation of each operator of the sum, and the splitting operator's output is dictated by linear combinations of these evaluations' inputs and outputs. To facilitate analysis, we introduce a novel representation of frugal splitting operators via a generalized primal-dual resolvent. The representation is characterized by an index and four matrices, and we provide conditions on these that ensure equivalence between the classes of frugal splitting operators and generalized primal-dual resolvents. Our representation paves the way for new results regarding lifting numbers and the development of a unified convergence analysis for frugal splitting operator methods, contingent on the directly evaluated operators being cocoercive. The minimal lifting number is n - 1 - f where n is the number of monotone operators and f is the number of direct evaluations in the splitting. Notably, this lifting number is achievable only if the first and last operator evaluations are resolvent evaluations. These results generalize the minimal lifting results by Ryu and by Malitsky and Tam that consider frugal resolvent splittings. Building on our representation, we delineate a constructive method to design frugal splitting operators, exemplified in the design of a novel, convergent, and parallelizable frugal splitting operator with minimal lifting.</p>}},
author = {{Morin, Martin and Banert, Sebastian and Giselsson, Pontus}},
issn = {{1052-6234}},
keywords = {{fixed point iterations; frugal splitting operators; minimal lifting; monotone inclusion; representation}},
language = {{eng}},
number = {{2}},
pages = {{1595--1621}},
publisher = {{Society for Industrial and Applied Mathematics}},
series = {{SIAM Journal on Optimization}},
title = {{FRUGAL SPLITTING OPERATORS : REPRESENTATION, MINIMAL LIFTING, AND CONVERGENCE}},
url = {{http://dx.doi.org/10.1137/22M1531105}},
doi = {{10.1137/22M1531105}},
volume = {{34}},
year = {{2024}},
}