Cargando…

A convergent relaxation of the Douglas–Rachford algorithm

This paper proposes an algorithm for solving structured optimization problems, which covers both the backward–backward and the Douglas–Rachford algorithms as special cases, and analyzes its convergence. The set of fixed points of the corresponding operator is characterized in several cases. Converge...

Descripción completa

Detalles Bibliográficos
Autor principal: Thao, Nguyen Hieu
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Springer US 2018
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6445491/
https://www.ncbi.nlm.nih.gov/pubmed/31007390
http://dx.doi.org/10.1007/s10589-018-9989-y
_version_ 1783408206571110400
author Thao, Nguyen Hieu
author_facet Thao, Nguyen Hieu
author_sort Thao, Nguyen Hieu
collection PubMed
description This paper proposes an algorithm for solving structured optimization problems, which covers both the backward–backward and the Douglas–Rachford algorithms as special cases, and analyzes its convergence. The set of fixed points of the corresponding operator is characterized in several cases. Convergence criteria of the algorithm in terms of general fixed point iterations are established. When applied to nonconvex feasibility including potentially inconsistent problems, we prove local linear convergence results under mild assumptions on regularity of individual sets and of the collection of sets. In this special case, we refine known linear convergence criteria for the Douglas–Rachford (DR) algorithm. As a consequence, for feasibility problem with one of the sets being affine, we establish criteria for linear and sublinear convergence of convex combinations of the alternating projection and the DR methods. These results seem to be new. We also demonstrate the seemingly improved numerical performance of this algorithm compared to the RAAR algorithm for both consistent and inconsistent sparse feasibility problems.
format Online
Article
Text
id pubmed-6445491
institution National Center for Biotechnology Information
language English
publishDate 2018
publisher Springer US
record_format MEDLINE/PubMed
spelling pubmed-64454912019-04-17 A convergent relaxation of the Douglas–Rachford algorithm Thao, Nguyen Hieu Comput Optim Appl Article This paper proposes an algorithm for solving structured optimization problems, which covers both the backward–backward and the Douglas–Rachford algorithms as special cases, and analyzes its convergence. The set of fixed points of the corresponding operator is characterized in several cases. Convergence criteria of the algorithm in terms of general fixed point iterations are established. When applied to nonconvex feasibility including potentially inconsistent problems, we prove local linear convergence results under mild assumptions on regularity of individual sets and of the collection of sets. In this special case, we refine known linear convergence criteria for the Douglas–Rachford (DR) algorithm. As a consequence, for feasibility problem with one of the sets being affine, we establish criteria for linear and sublinear convergence of convex combinations of the alternating projection and the DR methods. These results seem to be new. We also demonstrate the seemingly improved numerical performance of this algorithm compared to the RAAR algorithm for both consistent and inconsistent sparse feasibility problems. Springer US 2018-03-06 2018 /pmc/articles/PMC6445491/ /pubmed/31007390 http://dx.doi.org/10.1007/s10589-018-9989-y Text en © The Author(s) 2018 Open AccessThis article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
spellingShingle Article
Thao, Nguyen Hieu
A convergent relaxation of the Douglas–Rachford algorithm
title A convergent relaxation of the Douglas–Rachford algorithm
title_full A convergent relaxation of the Douglas–Rachford algorithm
title_fullStr A convergent relaxation of the Douglas–Rachford algorithm
title_full_unstemmed A convergent relaxation of the Douglas–Rachford algorithm
title_short A convergent relaxation of the Douglas–Rachford algorithm
title_sort convergent relaxation of the douglas–rachford algorithm
topic Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6445491/
https://www.ncbi.nlm.nih.gov/pubmed/31007390
http://dx.doi.org/10.1007/s10589-018-9989-y
work_keys_str_mv AT thaonguyenhieu aconvergentrelaxationofthedouglasrachfordalgorithm
AT thaonguyenhieu convergentrelaxationofthedouglasrachfordalgorithm