Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

FORWARD-BACKWARD SPLITTING WITH DEVIATIONS FOR MONOTONE INCLUSIONS

Sadeghi, Hamed LU orcid ; Banert, Sebastian LU and Giselsson, Pontus LU orcid (2024) In Applied Set-Valued Analysis and Optimization 6(2). p.113-135
Abstract

We propose and study a weakly convergent variant of the forward-backward algorithm for solving structured monotone inclusion problems. Our algorithm features a per-iteration deviation vector, providing additional degrees of freedom. The only requirement on the deviation vector to guarantee convergence is that its norm is bounded by a quantity that can be computed online. This approach offers great flexibility and paves the way for the design of new forward-backward-based algorithms, while still retaining global convergence guarantees. These guarantees include linear convergence under a metric subregularity assumption. Choosing suitable monotone operators enables the incorporation of deviations into other algorithms, such as the... (More)

We propose and study a weakly convergent variant of the forward-backward algorithm for solving structured monotone inclusion problems. Our algorithm features a per-iteration deviation vector, providing additional degrees of freedom. The only requirement on the deviation vector to guarantee convergence is that its norm is bounded by a quantity that can be computed online. This approach offers great flexibility and paves the way for the design of new forward-backward-based algorithms, while still retaining global convergence guarantees. These guarantees include linear convergence under a metric subregularity assumption. Choosing suitable monotone operators enables the incorporation of deviations into other algorithms, such as the Chambolle-Pock method and Krasnosel'skii-Mann iterations. We propose a novel inertial primal-dual algorithm by selecting the deviations along a momentum direction and deciding their size by using the norm condition. Numerical experiments validate our convergence claims and demonstrate that even this simple choice of a deviation vector can enhance the performance compared to, for instance, the standard Chambolle-Pock algorithm. Copy: 2024 Applied Set-Valued Analysis and 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
Forward-backward splitting, Global convergence, Inertial primal-dual algorithm, Linear convergence rate, Monotone inclusions
in
Applied Set-Valued Analysis and Optimization
volume
6
issue
2
pages
23 pages
publisher
Biemdas Academic Publishers
external identifiers
  • scopus:85189006469
ISSN
2562-7775
DOI
10.23952/asvao.6.2024.2.01
language
English
LU publication?
yes
id
6d145755-a704-4e2c-a128-cb54cbf0d064
date added to LUP
2024-04-16 15:40:06
date last changed
2024-04-17 02:58:34
@article{6d145755-a704-4e2c-a128-cb54cbf0d064,
  abstract     = {{<p>We propose and study a weakly convergent variant of the forward-backward algorithm for solving structured monotone inclusion problems. Our algorithm features a per-iteration deviation vector, providing additional degrees of freedom. The only requirement on the deviation vector to guarantee convergence is that its norm is bounded by a quantity that can be computed online. This approach offers great flexibility and paves the way for the design of new forward-backward-based algorithms, while still retaining global convergence guarantees. These guarantees include linear convergence under a metric subregularity assumption. Choosing suitable monotone operators enables the incorporation of deviations into other algorithms, such as the Chambolle-Pock method and Krasnosel'skii-Mann iterations. We propose a novel inertial primal-dual algorithm by selecting the deviations along a momentum direction and deciding their size by using the norm condition. Numerical experiments validate our convergence claims and demonstrate that even this simple choice of a deviation vector can enhance the performance compared to, for instance, the standard Chambolle-Pock algorithm. Copy: 2024 Applied Set-Valued Analysis and Optimization.</p>}},
  author       = {{Sadeghi, Hamed and Banert, Sebastian and Giselsson, Pontus}},
  issn         = {{2562-7775}},
  keywords     = {{Forward-backward splitting; Global convergence; Inertial primal-dual algorithm; Linear convergence rate; Monotone inclusions}},
  language     = {{eng}},
  month        = {{08}},
  number       = {{2}},
  pages        = {{113--135}},
  publisher    = {{Biemdas Academic Publishers}},
  series       = {{Applied Set-Valued Analysis and Optimization}},
  title        = {{FORWARD-BACKWARD SPLITTING WITH DEVIATIONS FOR MONOTONE INCLUSIONS}},
  url          = {{http://dx.doi.org/10.23952/asvao.6.2024.2.01}},
  doi          = {{10.23952/asvao.6.2024.2.01}},
  volume       = {{6}},
  year         = {{2024}},
}