Douglas-Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems

DOI10.1007/s10107-015-0963-5zbMath1346.90584arXiv1409.8444OpenAlexW3098950028WikidataQ57511162 ScholiaQ57511162MaRDI QIDQ312683

Guoyin Li, Ting Kei Pong

Publication date: 16 September 2016

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Large-scale problems in mathematical programming (90C06) Applications of mathematical programming (90C90) Nonconvex programming, global optimization (90C26)

Related Items (67)

On the Douglas-Rachford algorithm ⋮ Block-coordinate and incremental aggregated proximal gradient methods for nonsmooth nonconvex problems ⋮ A survey on some recent developments of alternating direction method of multipliers ⋮ Douglas-Rachford splitting and ADMM for nonconvex optimization: accelerated and Newton-type linesearch algorithms ⋮ Malitsky-Tam forward-reflected-backward splitting method for nonconvex minimization problems ⋮ Local convergence of the heavy-ball method and iPiano for non-convex optimization ⋮ Convergence analysis of two-step inertial Douglas-Rachford algorithm and application ⋮ Global Convergence of Splitting Methods for Nonconvex Composite Optimization ⋮ Local Linear Convergence of the ADMM/Douglas--Rachford Algorithms without Strong Convexity and Application to Statistical Imaging ⋮ Kurdyka-Łojasiewicz exponent via inf-projection ⋮ A primal Douglas-Rachford splitting method for the constrained minimization problem in compressive sensing ⋮ Projecting onto the Intersection of a Cone and a Sphere ⋮ Precompact convergence of the nonconvex primal-dual hybrid gradient algorithm ⋮ A splitting method for finding the resolvent of the sum of two maximal monotone operators ⋮ The equivalence of three types of error bounds for weakly and approximately convex functions ⋮ Two-stage stochastic variational inequalities: an ERM-solution procedure ⋮ A New Boosted Proximal Point Algorithm for Minimizing Nonsmooth DC Functions ⋮ Half-quadratic alternating direction method of multipliers for robust orthogonal tensor approximation ⋮ An extrapolated iteratively reweighted \(\ell_1\) method with complexity analysis ⋮ Computable centering methods for spiraling algorithms and their duals, with motivations from the theory of Lyapunov functions ⋮ Peaceman-Rachford splitting for a class of nonconvex optimization problems ⋮ The Douglas-Rachford algorithm for convex and nonconvex feasibility problems ⋮ An envelope for Davis-Yin splitting and strict saddle-point avoidance ⋮ Nonnegative low rank tensor approximations with multidimensional image applications ⋮ Convergence Rate Analysis for Averaged Fixed Point Iterations in Common Fixed Point Problems ⋮ Convergence analysis of an improved Bregman-type Peaceman-Rachford splitting algorithm for nonconvex nonseparable linearly constrained optimization problems ⋮ A weakly convergent fully inexact Douglas-Rachford method with relative error tolerance ⋮ Randomized Douglas–Rachford Methods for Linear Systems: Improved Accuracy and Efficiency ⋮ Convergence of Bregman Peaceman-Rachford splitting method for nonconvex nonseparable optimization ⋮ Convergence of Random Reshuffling under the Kurdyka–Łojasiewicz Inequality ⋮ Clustering multivariate count data via Dirichlet-multinomial network fusion ⋮ A Symmetric Alternating Direction Method of Multipliers for Separable Nonconvex Minimization Problems ⋮ An abstract convergence framework with application to inertial inexact forward-backward methods ⋮ Unifying Abstract Inexact Convergence Theorems and Block Coordinate Variable Metric iPiano ⋮ An incremental aggregated proximal ADMM for linearly constrained nonconvex optimization with application to sparse logistic regression problems ⋮ Analysis of the alternating direction method of multipliers for nonconvex problems ⋮ A Lyapunov function construction for a non-convex Douglas-Rachford iteration ⋮ Fixed Point Analysis of Douglas--Rachford Splitting for Ptychography and Phase Retrieval ⋮ Comparing Averaged Relaxed Cutters and Projection Methods: Theory and Examples ⋮ Local Minimizers of Semi-Algebraic Functions from the Viewpoint of Tangencies ⋮ Low Rank Pure Quaternion Approximation for Pure Quaternion Matrices ⋮ A parameterized Douglas-Rachford splitting algorithm for nonconvex optimization ⋮ Accelerating the DC algorithm for smooth functions ⋮ 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 ⋮ A family of projection gradient methods for solving the multiple-sets split feasibility problem ⋮ Convergence analysis of the generalized splitting methods for a class of nonconvex optimization problems ⋮ Local linear convergence of the alternating direction method of multipliers for nonconvex separable optimization problems ⋮ A convergent relaxation of the Douglas-Rachford algorithm ⋮ Calculus of the exponent of Kurdyka-Łojasiewicz inequality and its applications to linear convergence of first-order methods ⋮ Two-stage stochastic variational inequalities: theory, algorithms and applications ⋮ Douglas--Rachford Splitting and ADMM for Nonconvex Optimization: Tight Convergence Results ⋮ Convergence Analysis of the Relaxed Douglas--Rachford Algorithm ⋮ An inexact proximal gradient algorithm with extrapolation for a class of nonconvex nonsmooth optimization problems ⋮ Sequence Convergence of Inexact Nonconvex and Nonsmooth Algorithms with More Realistic Assumptions ⋮ SURVEY: SIXTY YEARS OF DOUGLAS–RACHFORD ⋮ On polarization-based schemes for the FFT-based computational homogenization of inelastic materials ⋮ Two-step inertial Bregman alternating minimization algorithm for nonconvex and nonsmooth problems ⋮ A Three-Operator Splitting Algorithm for Nonconvex Sparsity Regularization ⋮ A Bregman Forward-Backward Linesearch Algorithm for Nonconvex Composite Optimization: Superlinear Convergence to Nonisolated Local Minima ⋮ Convergence Rate Analysis of a Sequential Convex Programming Method with Line Search for a Class of Constrained Difference-of-Convex Optimization Problems ⋮ Solving Nonconvex Feasibility Problem on a Sphere and a Closed Ball by Douglas–Rachford Algorithm ⋮ Alternating Direction Method of Multipliers for a Class of Nonconvex and Nonsmooth Problems with Applications to Background/Foreground Extraction ⋮ Hölderian Error Bounds and Kurdyka-Łojasiewicz Inequality for the Trust Region Subproblem ⋮ A unified Douglas-Rachford algorithm for generalized DC programming ⋮ Toward a Mathematical Theory of the Crystallographic Phase Retrieval Problem ⋮ Convergence Analysis of Douglas--Rachford Splitting Method for “Strongly + Weakly” Convex Programming

Cites Work

• Recent results on Douglas-Rachford methods for combinatorial optimization problems
• New fractional error bounds for polynomial systems with applications to Hölderian stability in optimization and spectral theory of tensors
• Local linear convergence for alternating and averaged nonconvex projections
• On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
• On the convergence of von Neumann's alternating projection algorithm for two sets
• Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods
• Global convergence of a non-convex Douglas-Rachford iteration
• On the local convergence of the Douglas-Rachford algorithm
• Linear convergence of the Douglas–Rachford method for two closed sets
• On the $O(1/n)$ Convergence Rate of the Douglas–Rachford Alternating Direction Method
• DOUGLAS–RACHFORD FEASIBILITY METHODS FOR MATRIX COMPLETION PROBLEMS
• Tensor completion and low-n-rank tensor recovery via convex optimization
• Proximal Alternating Minimization and Projection Methods for Nonconvex Problems: An Approach Based on the Kurdyka-Łojasiewicz Inequality
• On the Numerical Solution of Heat Conduction Problems in Two and Three Space Variables
• Clarke Subgradients of Stratifiable Functions
• Finding Best Approximation Pairs Relative to a Convex and Prox-Regular Set in a Hilbert Space
• Splitting Algorithms for the Sum of Two Nonlinear Operators
• Variational Analysis
• Local differentiability of distance functions
• <formula formulatype="inline"><tex Notation="TeX">$L_{1/2}$</tex> </formula> Regularization: Convergence of Iterative Half Thresholding Algorithm
• Alternating Projections and Douglas-Rachford for Sparse Affine Feasibility
• On Projection Algorithms for Solving Convex Feasibility Problems
• Analysis of the Convergence Rate for the Cyclic Projection Algorithm Applied to Basic Semialgebraic Convex Sets
• A Convergent 3-Block SemiProximal Alternating Direction Method of Multipliers for Conic Programming with 4-Type Constraints
• Alternating Projections on Manifolds
• Nonconvex Notions of Regularity and Convergence of Fundamental Algorithms for Feasibility Problems
• Sparse Approximation via Penalty Decomposition Methods
• The Łojasiewicz Inequality for Nonsmooth Subanalytic Functions with Applications to Subgradient Dynamical Systems
• Convex analysis and monotone operator theory in Hilbert spaces

This page was built for publication: Douglas-Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems