Title: The Douglas-Rachford splitting algorithm for inconsistent minimization problems
| Speaker: | Walaa Moursi |
| Affiliation: | Stanford University |
| Room: | MC 5417 |
Abstract:
The Douglas--Rachford (DR) method is one of the most popular splitting methods in optimization. The method was first introduced in 1956 to numerically solve certain types of heat equations.
In their seminal work Lions (a Fields' medalist) and Mercier extended the algorithm to find a zero of the sum of two, not necessarily linear and possibly set-valued, maximally monotone operators in possibly infinite-dimensional Hilbert spaces. Nowadays, the method is a very popular splitting technique for finding a minimizer of the sum of two convex functions, more generally a zero of the sum of two maximally monotone operators. Nonetheless, the behaviour of the algorithm remains mysterious in the general inconsistent case, i.e., when the sum problem has no zeros, which corresponds to the absence of minimizers. However, more than a decade ago, it was shown that in the (possibly inconsistent) convex feasibility setting, the so-called shadow sequence remains bounded and its weak cluster points solve a best approximation problem. In this talk, we advance the understanding of the inconsistent case significantly by presenting a complete proof of the full weak convergence in the convex feasibility setting. We also provide strong and linear rates of convergence in special cases.