Full Text: PDF
Volume 3, Issue 3, 31 December 2021, Pages 435-456
Abstract. In recent years, the Douglas-Rachford splitting method has been shown to be effective at solving many non-convex optimization problems. In this paper, a local convergence analysis for non-convex feasibility problems is presented and both finite termination and local linear convergence are obtained. For a generalization of the Sudoku puzzle, it is proved that the local linear rate of convergence of Douglas-Rachford is exactly and independent of puzzle size. For the s-queens problem, it is proved that Douglas-Rachford converges after a finite number of iterations. Numerical results on solving Sudoku puzzles and s-queens puzzles are provided to support our theoretical findings.
How to Cite this Article:
Robert Tovey, Jingwei Liang, The fun is finite: Douglas-Rachford and Sudoku puzzle – Finite termination and local linear convergence, J. Appl. Numer. Optim. 3 (2021), 435-456.