Local and Global Analysis of Relaxed Douglas-Rachford for Nonconvex Feasibility Problems
by Anna-Lena Martins
Date of Examination:2019-03-19
Date of issue:2019-07-01
Advisor:Prof. Dr. Luke Russell
Referee:Prof. Dr. Luke Russell
Referee:Prof. Dr Thorsten Hohage
Files in this item
Name:diss_martins_web.pdf
Size:1.42Mb
Format:PDF
Description:PhD thesis
Abstract
English
This thesis investigates the local and global convergence analysis of the relaxed Douglas-Rachford method. This algorithm, which was first proposed over a decade ago, has become a standard procedure in applications. Convergence results for this algorithm are limited either to convex feasibility or consistent nonconvex feasibility with strong assumptions on the regularity of the underlying sets. After discussing feasibility problems and projection methods to solve these in general, we investigate the relaxed Douglas-Rachford method in detail for inconsistent and nonconvex feasibility problems. By introducing a new type of regularity of sets, called superregularity at a distance, we establish sufficient conditions for local linear convergence of the corresponding sequence for the method of relaxed Douglas-Rachford subsuming already existing results in the literature. We analyze a cyclic relaxed Douglas-Rachford scheme and state convergence results for closed and convex sets, by considering many-set feasibility problems. We then apply the theory developed to the famous phase retrieval problem and discuss the numerical performance of the algorithms.
Keywords: subtransversality; nonconvex; relaxed Douglas-Rachford; metric subregularity; linear convergence; fixed point; relaxed averaged alternating reflections; projection; inconsistent feasibility problem; super-regular; phase retrieval; cyclic relaxed Douglas-Rachford