• Speaker: Dr Francisco Arag√≥n Artacho, CARMA, The University of Newcastle
  • Title: Douglas-Rachford: an algorithm that mysteriously solves sudokus and other non-convex problems
  • Location: Room V129, Mathematics Building (Callaghan Campus) The University of Newcastle
  • Time and Date: 4:00 pm, Thu, 21st Jun 2012
  • Abstract:

    The Douglas-Rachford algorithm is an iterative method for finding a point in the intersection of two (or more) closed sets. It is well-known that the iteration (weakly) converges when it is applied to convex subsets of a Hilbert space. Despite the absence of a theoretical justification, the algorithm has also been successfully applied to various non-convex practical problems, including finding solutions for the eight queens problem, or sudoku puzzles. In particular, we will show how these two problems can be easily modelled.

    With the aim providing some theoretical explanation of the convergence in the non-convex case, we have established a region of convergence for the prototypical non-convex Douglas-Rachford iteration which finds a point on the intersection of a line and a circle. Previous work was only able to establish local convergence, and was ineffective in that no explicit region of convergence could be given.

    PS: Bring your hardest sudoku puzzle :)

  • Download: Talk slides (4.7 MB)

  • [Permanent link]