Douglas-Rachford method is a splitting algorithm for finding a zero of the sum of two maximal monotone operators. Each of its iterations requires the sequential solution of two proximal subproblems. The aim of this work is to present a fully inexact version of Douglas-Rachford method wherein both proximal subproblems are solved approximately within a relative error tolerance. We also present a semi-inexact variant in which the first subproblem is solved exactly and the second one inexactly. We prove that both methods generate sequences weakly convergent to the solution of the underlying inclusion problem, if any.
Accepté le :
DOI : 10.1051/cocv/2018063
Mots-clés : Douglas - Rachford method, relative error, weak convergence, splitting
@article{COCV_2019__25__A57_0,
author = {Fux Svaiter, Benar},
title = {A weakly convergent fully inexact {Douglas-Rachford} method with relative error tolerance},
journal = {ESAIM: Control, Optimisation and Calculus of Variations},
publisher = {EDP-Sciences},
volume = {25},
year = {2019},
doi = {10.1051/cocv/2018063},
mrnumber = {4023130},
zbl = {07194596},
language = {en},
url = {http://www.numdam.org/articles/10.1051/cocv/2018063/}
}
TY - JOUR AU - Fux Svaiter, Benar TI - A weakly convergent fully inexact Douglas-Rachford method with relative error tolerance JO - ESAIM: Control, Optimisation and Calculus of Variations PY - 2019 VL - 25 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/cocv/2018063/ DO - 10.1051/cocv/2018063 LA - en ID - COCV_2019__25__A57_0 ER -
%0 Journal Article %A Fux Svaiter, Benar %T A weakly convergent fully inexact Douglas-Rachford method with relative error tolerance %J ESAIM: Control, Optimisation and Calculus of Variations %D 2019 %V 25 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/cocv/2018063/ %R 10.1051/cocv/2018063 %G en %F COCV_2019__25__A57_0
Fux Svaiter, Benar. A weakly convergent fully inexact Douglas-Rachford method with relative error tolerance. ESAIM: Control, Optimisation and Calculus of Variations, Tome 25 (2019), article no. 57. doi : 10.1051/cocv/2018063. http://www.numdam.org/articles/10.1051/cocv/2018063/
[1] and , Iteration complexity of an inexact douglas-rachford method and of a Douglas-Rachford-Tseng’s F-B four-operator splitting method for solving monotone inclusions. Numer. Algorithms 82 (2019) 263–295 | DOI | MR | Zbl
[2] , and , Recent results on Douglas-Rachford methods for combinatorial optimization problems. J. Optim. Theory Appl. 163 (2014) 1–30 | DOI | MR | Zbl
[3] , and , Local linear convergence of the ADMM/Douglas-Rachford algorithms without strong convexity and application to statistical imaging. SIAM J. Imaging Sci. 9 (2016) 842–868 | DOI | MR | Zbl
[4] and , The Douglas-Rachford algorithm in the absence of convexity, in Fixed-point algorithms for inverse problems in science and engineering, Vol. 49 of Springer Optimization and its Applications. Springer, New York (2011) 93–109 | DOI | MR | Zbl
[5] , , and , Enlargement of monotone operators with applications to variational inequalities. Set-Valued Anal. 5 (1997) 159–180 | DOI | MR | Zbl
[6] and On the numerical solution of heat conduction problems in two and three space variables. Trans. Am. Math. Soc. 82 (1956) 421–439 | DOI | MR | Zbl
[7] and , On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators. Math. Program. 55 (1992) 293–318 | DOI | MR | Zbl
[8] and , A family of projective splitting methods for the sum of two maximal monotone operators. Math. Program. 111 (2008) 173–199 | DOI | MR | Zbl
[9] and , Relative-error approximate versions of Douglas–Rachford splitting and special cases of the ADMM. Math. Program. 170 (2017) 417–444 | DOI | MR | Zbl
[10] , Representing monotone operators by convex functions, in Workshop/Miniconference on Functional Analysis and Optimization. Vol. 20 of Proceedings of the Centre for Mathematics and its Analysis. Australian National University, Canberra (1988) 59–65 | MR | Zbl
[11] Application of the method of multipliers to variational inequalities. Stud. Math. Appl. 15 (1983) 299–331
[12] and , Splitting Methods in Communication, Imaging, Science, and Engineering. Scientific Computation. Springer, Cham (2016) | DOI | MR
[13] and , Nonconvex notions of regularity and convergence of fundamental algorithms for feasibility problems. SIAM J. Optim. 23 (2013) 2397–2419 | DOI | MR | Zbl
[14] , and , Alternating projections and Douglas-Rachford for sparse affine feasibility. IEEE Trans. Signal Process. 62 (2014) 4868–4881 | DOI | MR | Zbl
[15] and , Douglas-Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems. Math. Program. 159 (2016) 371–401 | DOI | MR | Zbl
[16] , , and , Activity identification and local linear convergence of Douglas-Rachford/ADMM under partial smoothness, in Scale space and variational methods in computer vision, Vol. 9087 of Lecture Notes in Computer Science. Springer, Cham (2015) 642–653 | DOI | MR | Zbl
[17] and , Splitting algorithms for the sum of two nonlinear operators. SIAM J. Numer. Anal. 16 (1979) 964–979 | DOI | MR | Zbl
[18] , Monotone (nonlinear) operators in Hilbert space. Duke Math. J. 29 (1962) 341–346 | DOI | MR | Zbl
[19] , Weak convergence of the sequence of successive approximations for nonexpansive mappings. Bull. Am. Math. Soc. 73 (1967) 591–597 | DOI | MR | Zbl
[20] and , A hybrid approximate extragradient-proximal point algorithm using the enlargement of a maximal monotone operator. Set-Valued Anal. 7 (1999) 323–345 | DOI | MR | Zbl
[21] and A hybrid projection-proximal point algorithm. J. Convex Anal. 6 (1990) 59–70 | MR | Zbl
[22] and , Error bounds for proximal point subproblems and associated inexact proximal point algorithms. Math. Program. 88 (2000) 371–389 | DOI | MR | Zbl
[23] and , An inexact hybrid generalized proximal point algorithm and some new results on the theory of Bregman functions. Math. Oper. Res. 25 (2000) 214–230 | DOI | MR | Zbl
[24] and , A unified framework for some inexact proximal point algorithms. Numer. Funct. Anal. Optim. 22 (2001) 1013–1035 | DOI | MR | Zbl
[25] , A family of enlargements of maximal monotone operators. Set-Valued Anal. 8 (2000) 311–328 | DOI | MR | Zbl
[26] , On weak convergence of the Douglas-Rachford method. SIAM J. Control Optim. 49 (2011) 280–287 | DOI | MR | Zbl
Cité par Sources :
