A Study On Nonconvex Feasibility Problems Using Douglas Rachford Operator Splitting Method

Abstract

This thesis studies the splitting algorithms for solving feasibility problems involving one or more nonconvex sets. The Douglas-Rachford algorithm and the method of alternating projection are the two projection algorithms frequently used for solving the feasibility problems. The method of alternating projection is the simplest projection algorithm to find a feasibility point involving two or more nonempty, closed sets. It involves finding orthogonal projection alternatingly onto two or more closed sets in a Hilbert space. Weak convergence of the method is established in a convex setting for periodic or quasiperiodic projection provided the intersection of the sets is nonempty. The Douglas-Rachford splitting algorithm is successfully implemented in the convex feasibility problems. When one or more set is nonconvex, the algorithm is used to solve different types of feasibility problems, but the convergence of the algorithm is still not thoroughly investigated. The behavior of the Douglas-Rachford method in both consistent and inconsistent settings are studied. Interestingly, here, the Douglas-Rachford operator is not a nonexpansive map which is an essential requirement for studying the convergence of the Douglas-Rachford algorithm. In the consistent setting, it has been shown that the Douglas Rachford sequence converges and the corresponding shadow sequence converges to the intersection of sets. In the inconsistent setting, it is observed that the Douglas Rachford sequence diverges, and the corresponding shadow sequence has a weak cluster point. The convergence of both the algorithms is still not fully clear when one or more set is nonconvex. Here, behavior of both the algorithms involving one set as convex and the other set being nonconvex are analyzed.