Open Collections

The Douglas–Rachford operator in the possibly inconsistent case : static properties and dynamic behaviour

University of British Columbia

The problem of finding a minimizer of the sum of two convex functions – or, more generally, that of finding a zero of the sum of two maximally monotone operators – is of central importance in variational analysis and optimization. Perhaps the most popular method of solving this problem is the Douglas–Rachford splitting method. Surprisingly, little is known about the behaviour of the algorithm in the general inconsistent case, i.e., when the sum problem has no zeros. This thesis provides a comprehensive study of the Douglas–Rachford operator and the corresponding algorithm. First, a novel framework of the normal problem that copes with the possibly inconsistent situation is introduced and studied. We present a systematic study of the range of the operator and displacement map, which provides precise information on the minimal displacement vector needed to define the normal problem. A new Fejér monotonicity principle as well as new identities for the Douglas–Rachford operator are developed. A systematic and detailed study of affine nonexpansive operators and their asymptotic behaviour is presented. In the light of the new analysis, we significantly advance the understanding of the inconsistent case by providing a complete proof of the full weak convergence of the shadow sequence to a best approximation solution in the convex feasibility setting. In fact, a more general sufficient condition for weak convergence in the general case is presented. Under some extra assumptions, we were able to prove strong and linear convergence. Our results are illustrated through numerous examples. We conclude with a list of open problems which serve as promising directions of future research.

Text

2017-01-21

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/60141

Mathematics

University of British Columbia

UBCO

http://creativecommons.org/licenses/by-nc-nd/4.0/