论文标题
乐趣是有限的：道格拉斯·拉赫福德和苏多库难题 - 有限的终止和本地线性融合
The Fun is Finite: Douglas-Rachford and Sudoku Puzzle -- Finite Termination and Local Linear Convergence
论文作者
论文摘要
近年来，道格拉斯 - 拉赫福德分裂方法已被证明可以有效解决许多非凸优化问题。在本文中，我们提出了针对非凸的可行性问题的局部收敛分析，并表明获得了有限的终止和局部线性收敛。对于Sudoku难题的概括，我们证明了Douglas-Rachford的局部线性收敛速率正是$ \ frac {\ sqrt {5}}} {5} $，并且独立于拼图大小。对于$ s $ Queens的问题，我们证明道格拉斯·拉赫福德在有限的迭代后收敛。提供了解决Sudoku难题和$ s $ Queens难题的数值结果，以支持我们的理论发现。
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 $\frac{\sqrt{5}}{5}$ and independent of puzzle size. For the $s$-queens problem we prove 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.
