Recent results on Douglas-Rachford methods for combinatorial optimization problems

DOI10.1007/s10957-013-0488-0zbMath1305.90341arXiv1305.2657MaRDI QIDQ467464

Jonathan M. Borwein, Matthew K. Tam, Francisco J. Aragón Artacho

Publication date: 3 November 2014

Published in: Journal of Optimization Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1305.2657

zbMATH Keywords

projections; sudoku; modelling; combinatorial optimization; reflections; satisfiability; feasibility; Douglas-Rachford; nonograms

Mathematics Subject Classification ID

90C27: Combinatorial optimization

Related Items

Reflection Methods for Inverse Problems with Applications to Protein Conformation Determination, Norm convergence of realistic projection and reflection methods, SURVEY: SIXTY YEARS OF DOUGLAS–RACHFORD, Solving Nonconvex Feasibility Problem on a Sphere and a Closed Ball by Douglas–Rachford Algorithm, A weakly convergent fully inexact Douglas-Rachford method with relative error tolerance, The cyclic Douglas–Rachford algorithm with r-sets-Douglas–Rachford operators, On the Finite Convergence of the Douglas--Rachford Algorithm for Solving (Not Necessarily Convex) Feasibility Problems in Euclidean Spaces, On the order of the operators in the Douglas-Rachford algorithm, Global behavior of the Douglas-Rachford method for a nonconvex feasibility problem, Optimal rates of linear convergence of relaxed alternating projections and generalized Douglas-Rachford methods for two subspaces, Douglas-Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems, Projection methods for quantum channel construction, A new projection method for finding the closest point in the intersection of convex sets, The Douglas-Rachford algorithm for the case of the sphere and the line, Circumcentering the Douglas-Rachford method, Solving graph coloring problems with the Douglas-Rachford algorithm, Dynamics of the Douglas-Rachford method for ellipses and \(p\)-spheres, Matrix product constraints by projection methods, Convergence analysis of processes with valiant projection operators in Hilbert space, A Lyapunov function construction for a non-convex Douglas-Rachford iteration, A feasibility approach for constructing combinatorial designs of circulant type, General splitting methods with linearization for the split feasibility problem, Constraint reduction reformulations for projection algorithms with applications to wavelet construction, Circumcentering reflection methods for nonconvex feasibility problems, A product space reformulation with reduced dimension for splitting algorithms, An enhanced formulation for solving graph coloring problems with the Douglas-Rachford algorithm, The Douglas-Rachford algorithm for convex and nonconvex feasibility problems, The block-wise circumcentered-reflection method, A parameterized Douglas-Rachford splitting algorithm for nonconvex optimization, A cyclic Douglas-Rachford iteration scheme, The rate of linear convergence of the Douglas-Rachford algorithm for subspaces is the cosine of the Friedrichs angle, Iteration process for fixed point problems and zeros of maximal monotone operators, On the Douglas-Rachford algorithm, On the linear convergence of the circumcentered-reflection method, New Douglas--Rachford Algorithmic Structures and Their Convergence Analyses, Convergence Rate Analysis for Averaged Fixed Point Iterations in Common Fixed Point Problems, APPLICATION OF PROJECTION ALGORITHMS TO DIFFERENTIAL EQUATIONS: BOUNDARY VALUE PROBLEMS, Comparing Averaged Relaxed Cutters and Projection Methods: Theory and Examples

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Restricted normal cones and sparsity optimization with affine constraints
• Finding best approximation pairs relative to two closed convex sets in Hilbert spaces
• Alternating projections in CAT(0) spaces
• A Lyusternik-Graves theorem for the proximal point method
• Tetravex is NP-complete
• Removing multiplicative noise by Douglas-Rachford splitting methods
• On the convergence of von Neumann's alternating projection algorithm for two sets
• Projection and proximal point methods: Convergence results and counterexamples.
• A cyclic Douglas-Rachford iteration scheme
• Global convergence of a non-convex Douglas-Rachford iteration
• Techniques of variational analysis
• The Douglas–Rachford Algorithm in the Absence of Convexity
• DOUGLAS–RACHFORD FEASIBILITY METHODS FOR MATRIX COMPLETION PROBLEMS
• On Weak Convergence of the Douglas–Rachford Method
• On the Numerical Solution of Heat Conduction Problems in Two and Three Space Variables
• Splitting Algorithms for the Sum of Two Nonlinear Operators
• Solving monotone inclusions via compositions of nonexpansive averaged operators
• The Cyclic Douglas-Rachford Method for Inconsistent Feasibility Problems
• Searching with iterated maps
• Nonconvex Notions of Regularity and Convergence of Fundamental Algorithms for Feasibility Problems
• Weak convergence of the sequence of successive approximations for nonexpansive mappings
• Convex analysis and monotone operator theory in Hilbert spaces