Asymmetric Bregman Forward-Backward Splitting with Projection Correction
(2022)Department of Automatic Control
- Abstract
- This thesis examines first-order Bregman algorithms in a primal and a primal-dual setting. The Bregman gradient descent algorithm is introduced from a majorization-minimization perspective and as a generalization of the gradient descent algorithm. Concepts such as relative smoothness and Legendreness are defined and are shown to be natural restrictions in order to show convergence results.
A special case of the NOFOB algorithm, proposed by Giselsson in 2021, with a Bregman setting is defined, which we call the Bregman NOFOB algorithm. This algorithm works in a primal-dual setting and consists of a nonlinear forward-backward splitting step followed by a projection correction. Both of these components are discussed with respect to the... (More) - This thesis examines first-order Bregman algorithms in a primal and a primal-dual setting. The Bregman gradient descent algorithm is introduced from a majorization-minimization perspective and as a generalization of the gradient descent algorithm. Concepts such as relative smoothness and Legendreness are defined and are shown to be natural restrictions in order to show convergence results.
A special case of the NOFOB algorithm, proposed by Giselsson in 2021, with a Bregman setting is defined, which we call the Bregman NOFOB algorithm. This algorithm works in a primal-dual setting and consists of a nonlinear forward-backward splitting step followed by a projection correction. Both of these components are discussed with respect to the Bregman setting. The Bregman NOFOB framework unifies multiple algorithms, one of which is the celebrated Bregman Chambolle-Pock method. It also allows us to define novel Bregman primal-dual algorithms. Under certain assumptions on the solution set of the problem and on the projection steps, we show that the Bregman NOFOB method converges in duality gap.
This Bregman NOFOB algorithm with asymmetric kernel is compared with theWolfe-Atwood (WA) algorithm on the D-optimal design optimization problem. As confirmed by the theory of this thesis - in the primal case - the two algorithms both converge by sequence and by function value, with sublinear (Bregman NOFOB) and linear (WA) rates. In the primal-dual case we experimentally show that the projection step sizes satisfy the duality gap convergence of the Bregman NOFOB algorithm. Indeed, this duality gap convergence is also verified experimentally. No comparison with the WA algorithm is made in the primal-dual case, since it is restricted to the primal setting. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/student-papers/record/9108697
- author
- Nilsson, Max
- supervisor
-
- Pontus Giselsson LU
- Emma Tegling LU
- organization
- year
- 2022
- type
- H3 - Professional qualifications (4 Years - )
- subject
- report number
- TFRT-6187
- ISSN
- 0280-5316
- language
- English
- id
- 9108697
- date added to LUP
- 2023-01-24 14:49:51
- date last changed
- 2023-01-24 14:49:51
@misc{9108697,
abstract = {{This thesis examines first-order Bregman algorithms in a primal and a primal-dual setting. The Bregman gradient descent algorithm is introduced from a majorization-minimization perspective and as a generalization of the gradient descent algorithm. Concepts such as relative smoothness and Legendreness are defined and are shown to be natural restrictions in order to show convergence results.
A special case of the NOFOB algorithm, proposed by Giselsson in 2021, with a Bregman setting is defined, which we call the Bregman NOFOB algorithm. This algorithm works in a primal-dual setting and consists of a nonlinear forward-backward splitting step followed by a projection correction. Both of these components are discussed with respect to the Bregman setting. The Bregman NOFOB framework unifies multiple algorithms, one of which is the celebrated Bregman Chambolle-Pock method. It also allows us to define novel Bregman primal-dual algorithms. Under certain assumptions on the solution set of the problem and on the projection steps, we show that the Bregman NOFOB method converges in duality gap.
This Bregman NOFOB algorithm with asymmetric kernel is compared with theWolfe-Atwood (WA) algorithm on the D-optimal design optimization problem. As confirmed by the theory of this thesis - in the primal case - the two algorithms both converge by sequence and by function value, with sublinear (Bregman NOFOB) and linear (WA) rates. In the primal-dual case we experimentally show that the projection step sizes satisfy the duality gap convergence of the Bregman NOFOB algorithm. Indeed, this duality gap convergence is also verified experimentally. No comparison with the WA algorithm is made in the primal-dual case, since it is restricted to the primal setting.}},
author = {{Nilsson, Max}},
issn = {{0280-5316}},
language = {{eng}},
note = {{Student Paper}},
title = {{Asymmetric Bregman Forward-Backward Splitting with Projection Correction}},
year = {{2022}},
}