On the finite termination of the Douglas-Rachford method for the convex feasibility problem

Abstract

In this paper we apply the Douglas–Rachford (DR) method to solve the problem of finding a point in the intersection of the interior of a closed convex cone and a closed convex set in an infinite-dimensional Hilbert space. For this purpose, we propose two variants of the DR method which can find a point in the intersection in a finite number of iterations. In order to analyse the finite termination of the methods, we use some properties of the metric projection and a result regarding the rate of convergence of fixed point iterations. As applications of the results, we propose the methods for solving the conic and semidefinite feasibility problems, which terminate at a solution in a finite number of iterations.

Keywords:

• Douglas–Rachford method
• convex feasibility problem
• finite termination
• Slater condition
• metric projection
• nonexpansive
• error bound
• conic feasibility problem
• semidefinite feasibility problem

AMS Subject Classifications:

• 47J25
• 47H09
• 90C22
• 90C08
• 93B40

Acknowledgements

We would like to thank Professors W. Takahashi of Tokyo Institute of Technology and D. Kuroiwa of Shimane University for their helpful support. We would also like to thank the anonymous referees for constructive comments.

Notes

No potential conflict of interest was reported by the authors.

1 When C and D are closed convex cones, Slater’s condition and Assumption 1.1 are equivalent [5, Theorem 2.2].

Additional information

Funding

This work was supported by the Ministry of Education, Culture, Sports, Science, and Technology [grant number 16K05280].