Recent results on Douglas-Rachford methods for combinatorial optimization problems

DOI10.1007/s10957-013-0488-0zbMath1305.90341arXiv1305.2657OpenAlexW2098764331MaRDI 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

projectionssudokumodellingcombinatorial optimizationreflectionssatisfiabilityfeasibilityDouglas-Rachfordnonograms

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items

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

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