Recent results on Douglas-Rachford methods for combinatorial optimization problems

DOI10.1007/S10957-013-0488-0zbMATH Open1305.90341arXiv1305.2657OpenAlexW2098764331MaRDI QIDQ467464FDOQ467464

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

Publication date: 3 November 2014

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

Abstract: We discuss recent positive experiences applying convex feasibility algorithms of Douglas--Rachford type to highly combinatorial and far from convex problems.

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

zbMATH Keywords

sudokumodellingprojectionscombinatorial optimizationreflectionssatisfiabilityfeasibilityDouglas-Rachfordnonograms

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Cites Work

• On the Numerical Solution of Heat Conduction Problems in Two and Three Space Variables
• Splitting Algorithms for the Sum of Two Nonlinear Operators
• Convex analysis and monotone operator theory in Hilbert spaces
• Title not available (Why is that?)
• Solving monotone inclusions via compositions of nonexpansive averaged operators
• On the convergence of von Neumann's alternating projection algorithm for two sets
• Techniques of variational analysis
• Weak convergence of the sequence of successive approximations for nonexpansive mappings
• Title not available (Why is that?)
• Convex functions. Constructions, characterizations and counterexamples
• Restricted normal cones and sparsity optimization with affine constraints
• Projection and proximal point methods: Convergence results and counterexamples.
• Alternating projections in CAT(0) spaces
• Removing multiplicative noise by Douglas-Rachford splitting methods
• A cyclic Douglas-Rachford iteration scheme
• Global convergence of a non-convex Douglas-Rachford iteration
• The Douglas-Rachford algorithm in the absence of convexity
• The cyclic Douglas-Rachford method for inconsistent feasibility problems
• Nonconvex notions of regularity and convergence of fundamental algorithms for feasibility problems
• Douglas-Rachford feasibility methods for matrix completion problems
• Searching with iterated maps
• Finding best approximation pairs relative to two closed convex sets in Hilbert spaces
• On weak convergence of the Douglas-Rachford method
• Title not available (Why is that?)
• Convex optimization techniques for the efficient recovery of a sparsely corrupted low-rank matrix
• A Lyusternik-Graves theorem for the proximal point method
• Tetravex is NP-complete

Cited In (40)

• A new projection method for finding the closest point in the intersection of convex sets
• Iteration process for fixed point problems and zeros of maximal monotone operators
• 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
• Convergence rate analysis for averaged fixed point iterations in common fixed point problems
• Reflection Methods for Inverse Problems with Applications to Protein Conformation Determination
• Global behavior of the Douglas-Rachford method for a nonconvex feasibility problem
• A feasibility approach for constructing combinatorial designs of circulant type
• On the Douglas-Rachford algorithm
• Douglas-Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems
• General splitting methods with linearization for the split feasibility problem
• A weakly convergent fully inexact Douglas-Rachford method with relative error tolerance
• The Douglas-Rachford algorithm for the case of the sphere and the line
• The block-wise circumcentered-reflection method
• SURVEY: SIXTY YEARS OF DOUGLAS–RACHFORD
• Solving Nonconvex Feasibility Problem on a Sphere and a Closed Ball by Douglas–Rachford Algorithm
• Optimal rates of linear convergence of relaxed alternating projections and generalized Douglas-Rachford methods for two subspaces
• Circumcentering the Douglas-Rachford method
• Solving graph coloring problems with the Douglas-Rachford algorithm
• A product space reformulation with reduced dimension for splitting algorithms
• Constraint reduction reformulations for projection algorithms with applications to wavelet construction
• Circumcentering reflection methods for nonconvex feasibility problems
• An enhanced formulation for solving graph coloring problems with the Douglas-Rachford algorithm
• Matrix product constraints by projection methods
• The Douglas-Rachford algorithm for convex and nonconvex feasibility problems
• 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 linear convergence of the circumcentered-reflection method
• Projection methods for quantum channel construction
• Non-separable multidimensional multiresolution wavelets: a Douglas-Rachford approach
• A parameterized Douglas-Rachford splitting algorithm for nonconvex optimization
• APPLICATION OF PROJECTION ALGORITHMS TO DIFFERENTIAL EQUATIONS: BOUNDARY VALUE PROBLEMS
• New Douglas-Rachford algorithmic structures and their convergence analyses
• Comparing Averaged Relaxed Cutters and Projection Methods: Theory and Examples
• Convergence analysis of processes with valiant projection operators in Hilbert space
• Dynamics of the Douglas-Rachford method for ellipses and \(p\)-spheres
• A Lyapunov function construction for a non-convex Douglas-Rachford iteration
• Norm convergence of realistic projection and reflection methods
• Randomized Douglas–Rachford Methods for Linear Systems: Improved Accuracy and Efficiency

This page was built for publication: Recent results on Douglas-Rachford methods for combinatorial optimization problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q467464)