Feasibility Problems: Douglas-Rachford and Projection Methods

RESEARCH TEAM: Francisco J. Aragón Artacho, Jonathan M. Borwein, Brailey Sims, Ian Searston, Matthew K. Tam, Liangjin Yao

CONTACT: [email protected]

Projection methods form the basis of iterative algorithms, which, at each stage, employ nearest point projections. Applications include a variety of optimization and reconstruction problems, both continuous and combinatorial.

           

1. Publications
   • Borwein, J.M., Li, G., and Tam, M.K. Convergence rate analysis for averaged fixed point iterations in the presence of Hölder regularity (arXiv:1510.06823")
   • Aragón Artacho, F. J., Borwein, J.M., and Tam, M.K. Global behavior of the Douglas-Rachford method for a nonconvex feasibility problem. (arXiv:1506.09026)
   • Borwein J.M., and Tam M.K. (2014). Reflection methods for inverse problems with application to protein conformation determination with J.M. Borwein. Springer volume on the CIMPA school Generalized Nash Equilibrium Problems, Bilevel programming and MPEC New Delhi, India, Dec. 2012. Submitted August 2014. Preprint: arXiv:1408.4213
   • Borwein, J.M., Sims, B., and Tam, M.K. (2014). Norm convergence of realistic projection and reflection methods. Optim., published online August 2014. DOI: 10.1080/02331934.2014.947499. (arXiv:1312.7323).
   • Borwein, J.M. and Tam, M.K. (2014). The cyclic Douglas-Rachford method for inconsistent feasibility problems. Nonlinear Convex Anal., 16(4):537-584, 2015. (arXiv:1310.2195)
   • Aragón Artacho, F. J., Borwein, J. M., Tam, M. K. (2014). Douglas-Rachford feasibility methods for matrix completion problems. ANZIAM J. 55(4):299-326. DOI: 10.1017/S1446181114000145 (arXiv:1308.4243).
   • Borwein, J. M., Li, G. and Yao, L., (2013). Analysis of the convergence rate for the cyclic projection algorithm on semi-algebraic convex sets. (arXiv:1304.7965)
   • Aragón Artacho, F. J., Borwein, J. M., Tam, M. K. (2014). Recent Results on Douglas-Rachford Methods for Combinatorial Optimization Problems. J. Optimization Theory and Applications 163(1):1-30. (arXiv:1305.2657)
   • Aragón Artacho, F. J., Borwein, J. M., Tam, M. K. (2013). Recent Results on Douglas-Rachford Methods. Serdica Mathematical Journal, 39, 313-330.
   • Borwein, J. M., Tam, M. K. (2014). A cyclic Douglas-Rachford Iteration Scheme. J. Optimization Theory and Applications, 160(1), 1-29. (arXiv:1303.1859)
   • Aragón Artacho, F. J., Borwein, J. M. (2012). Global convergence of a non-convex Douglas-Rachford iteration. J. Global Optimization, 1-17. (arXiv:1203.2392)
   • Borwein, J. M. (2012). Maximum entropy and feasibility methods for convex and nonconvex inverse problems. Optimization, 61(1), 1-33. (preprint)
   • Bačák, M., Searston, I., Sims, B. (2012). Alternating projections in CAT (0) spaces. Journal of Mathematical Analysis and Applications, 385(2), 599-607.
   • Borwein, J. M., Sims, B. (2011). The Douglas–Rachford algorithm in the absence of convexity. In Fixed-Point Algorithms for Inverse Problems in Science and Engineering (pp. 93-109). Springer New York. (preprint)

2. Related presentations
   • Projection algorithms for convex and nonconvex feasibility problems (F. J. Aragón Artacho, September 2015). The accompanying puzzles
   • Lectures for Paseky: Theory and Applications of Convex and Non-convex Feasibility Problems. A four lecture series prepared for the Spring School on Variational Analysis (April 2015).
   • Douglas-Rachford Feasibility Methods for Matrix Completion (J.M. Borwein, CARMA/OCANA Seminar, Oct. 2013)
   • Cyclic Douglas-Rachford Iterations (M.K. Tam, AustMS14, Sept.-Oct. 2013)
   • Molecular Reconstructions via Douglas-Rachford (M.K. Tam, CARMA Retreat, Aug 2013)
   • Projection methods in geodesic metric spaces - Part II (B. Sims, OANT Seminar, Aug. 2013)
   • Projection methods in geodesic metric spaces (B. Sims, OANT Seminar, July 2013)
   • Douglas-Rachford for Combinatorial Optimisation (M. K. Tam, AMSSC14, July 2013)
   • Analysis of the convergence rate for the cyclic projection algorithm applied to semi-algebraic convex sets (L. Yao, OANT Seminar, June 2013)
   • Cyclic Douglas-Rachford Iterations (M. K. Tam, OANT Seminar, May 2013)
   • A Cyclic Douglas-Rachford Iteration Scheme (B. Sims, Workshop on Fixed Point Theory Thailand, April 2013)
   • The Method of Alternating Projections (M. K. Tam, AustMS12, September 2012)
   • Douglas-Rachford: an algorithm that mysteriously solves sudokus and other non-convex problems (F. J. Aragón Artacho, June 2012)
   • (Spanish) Un algoritmo que misteriosamente resuelve cualquier sudoku (F. J. Aragón Artacho, June 2012)
   • Entropy & Projection Methods for Inverse Problems (J. M. Borwein, May 2012)
   • Alternating Projection Methods without Convexity (M. K. Tam, CSIRO Big Day In, Feb. 2012)
   • Non-convex Douglas-Rachford iterations (J. M. Borwein, Oct. 2011)
   • Entropy and Projection Methods (J. M. Borwein, June 2011)
   • Entropy and Projection Methods (J. M. Borwein, Sept. 2008 - Mar. 2009)
   • Iterative Methods for Inverse Problems (J. M. Borwein, Feb. 1992)

3. Visualizing Iterative Projection Methods
   • Douglas-Rachford reconstruction of the protein 1PTQ (embedded video)
   • Douglas-Rachford iterative Cinderella applets
   1. Simple Douglas-Rachford (in Cinderella)
   2. Composite Douglas-Rachford (in Cinderella)
   3. Multiple Iterates Douglas-Rachford (in Cinderella)
   4. Circle and halfline Douglas-Rachford (in Cinderella)
   5. 2-cycles Douglas-Rachford (in Cinderella)
   • Cyclic Douglas-Rachford iterative Cinderella applets
   1. Two spheres cyclic Douglas-Rachford
   2. A sphere/ball and a line cyclic Douglas-Rachford
   3. Two lines cyclic Douglas-Rachford
   4. A sphere/ball and a point cyclic Douglas-Rachford
   • Matthew Tam's ASMI Vacation Scholarship
   • Cinderella Interactive Geometry Software.

4. Related links
   • Jon Borwein's Mathematics Portal
   • Douglas-Rachford for Combinatorial Optimization Website
   • Cyclic Douglas-Rachford Website
   • Experimental Mathematics Website
   • Walking on numbers: a multiple media mathematics project
   • CARMA (Priority Research Centre for Computer-Assisted Research Mathematics and its Applications)

5. Related technical reports
   • Tam, M. K. (2012). The Method of Alternating Projections. (Honours thesis, University of Newcastle, Australia).
   • Tam, M. K. (2012). Alternating Projection Methods Failure in the Absence of Convexity. (AMSI Summer Vacation Scholarship).