Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Incorporating history and deviations in forward–backward splitting

Sadeghi, Hamed LU orcid ; Banert, Sebastian LU and Giselsson, Pontus LU orcid (2024) In Numerical Algorithms 96(4). p.1819-1867
Abstract

We propose a variation of the forward–backward splitting method for solving structured monotone inclusions. Our method integrates past iterates and two deviation vectors into the update equations. These deviation vectors bring flexibility to the algorithm and can be chosen arbitrarily as long as they together satisfy a norm condition. We present special cases where the deviation vectors, selected as predetermined linear combinations of previous iterates, always meet the norm condition. Notably, we introduce an algorithm employing a scalar parameter to interpolate between the conventional forward–backward splitting scheme and an accelerated O(1n2) -convergent forward–backward method that encompasses both the accelerated proximal point... (More)

We propose a variation of the forward–backward splitting method for solving structured monotone inclusions. Our method integrates past iterates and two deviation vectors into the update equations. These deviation vectors bring flexibility to the algorithm and can be chosen arbitrarily as long as they together satisfy a norm condition. We present special cases where the deviation vectors, selected as predetermined linear combinations of previous iterates, always meet the norm condition. Notably, we introduce an algorithm employing a scalar parameter to interpolate between the conventional forward–backward splitting scheme and an accelerated O(1n2) -convergent forward–backward method that encompasses both the accelerated proximal point method and the Halpern iteration as special cases. The existing methods correspond to the two extremes of the allowed scalar parameter range. By choosing the interpolation scalar near the midpoint of the permissible range, our algorithm significantly outperforms these previously known methods when addressing a basic monotone inclusion problem stemming from minimax optimization.

(Less)
Please use this url to cite or link to this publication:
author
; and
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
Convergence rate, Deviations, Forward–backward splitting, Halpern iteration, Inertial algorithms, Monotone inclusions
in
Numerical Algorithms
volume
96
issue
4
pages
1819 - 1867
publisher
Springer
external identifiers
  • scopus:85178405258
ISSN
1017-1398
DOI
10.1007/s11075-023-01686-8
language
English
LU publication?
yes
id
a4a4690a-a579-428a-af78-e01155bc61b9
date added to LUP
2024-01-08 11:02:29
date last changed
2024-10-14 11:56:32
@article{a4a4690a-a579-428a-af78-e01155bc61b9,
  abstract     = {{<p>We propose a variation of the forward–backward splitting method for solving structured monotone inclusions. Our method integrates past iterates and two deviation vectors into the update equations. These deviation vectors bring flexibility to the algorithm and can be chosen arbitrarily as long as they together satisfy a norm condition. We present special cases where the deviation vectors, selected as predetermined linear combinations of previous iterates, always meet the norm condition. Notably, we introduce an algorithm employing a scalar parameter to interpolate between the conventional forward–backward splitting scheme and an accelerated O(1n2) -convergent forward–backward method that encompasses both the accelerated proximal point method and the Halpern iteration as special cases. The existing methods correspond to the two extremes of the allowed scalar parameter range. By choosing the interpolation scalar near the midpoint of the permissible range, our algorithm significantly outperforms these previously known methods when addressing a basic monotone inclusion problem stemming from minimax optimization.</p>}},
  author       = {{Sadeghi, Hamed and Banert, Sebastian and Giselsson, Pontus}},
  issn         = {{1017-1398}},
  keywords     = {{Convergence rate; Deviations; Forward–backward splitting; Halpern iteration; Inertial algorithms; Monotone inclusions}},
  language     = {{eng}},
  number       = {{4}},
  pages        = {{1819--1867}},
  publisher    = {{Springer}},
  series       = {{Numerical Algorithms}},
  title        = {{Incorporating history and deviations in forward–backward splitting}},
  url          = {{http://dx.doi.org/10.1007/s11075-023-01686-8}},
  doi          = {{10.1007/s11075-023-01686-8}},
  volume       = {{96}},
  year         = {{2024}},
}