The Fun is Finite: Douglas-Rachford and Sudoku Puzzle -- Finite Termination and Local Linear Convergence

preprint2021arXivOpen access

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 we present a local convergence analysis for non-convex feasibility problems and show that both finite termination and local linear convergence are obtained. For a generalization of the Sudoku puzzle, we prove that the local linear rate of convergence of Douglas-Rachford is exactly 55\frac{\sqrt{5}}{5} and independent of puzzle size. For the ss-queens problem we prove that Douglas-Rachford converges after a finite number of iterations. Numerical results on solving Sudoku puzzles and ss-queens puzzles are provided to support our theoretical findings.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.