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

DOI10.1007/S10107-015-0963-5zbMATH Open1346.90584arXiv1409.8444OpenAlexW3098950028WikidataQ57511162 ScholiaQ57511162MaRDI QIDQ312683FDOQ312683

Authors: G. Li, Ting Kei Pong 

Publication date: 16 September 2016

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

Abstract: We adapt the Douglas-Rachford (DR) splitting method to solve nonconvex feasibility problems by studying this method for a class of nonconvex optimization problem. While the convergence properties of the method for convex problems have been well studied, far less is known in the nonconvex setting. In this paper, for the direct adaptation of the method to minimize the sum of a proper closed function $g$ and a smooth function $f$ with a Lipschitz continuous gradient, we show that if the step-size parameter is smaller than a computable threshold and the sequence generated has a cluster point, then it gives a stationary point of the optimization problem. Convergence of the whole sequence and a local convergence rate are also established under the additional assumption that $f$ and $g$ are semi-algebraic. We also give simple sufficient conditions guaranteeing the boundedness of the sequence generated. We then apply our nonconvex DR splitting method to finding a point in the intersection of a closed convex set $C$ and a general closed set $D$ by minimizing the squared distance to $C$ subject to $D$. We show that if either set is bounded and the step-size parameter is smaller than a computable threshold, then the sequence generated from the DR splitting method is actually bounded. Consequently, the sequence generated will have cluster points that are stationary for an optimization problem, and the whole sequence is convergent under an additional assumption that $C$ and $D$ are semi-algebraic. We achieve these results based on a new merit function constructed particularly for the DR splitting method. Our preliminary numerical results indicate that our DR splitting method usually outperforms the alternating projection method in finding a sparse solution of a linear system, in terms of both the solution quality and the number of iterations taken.

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

Recommendations

• A parameterized Douglas-Rachford splitting algorithm for nonconvex optimization
• Solving nonconvex feasibility problem on a sphere and a closed ball by Douglas-Rachford algorithm
• Peaceman-Rachford splitting for a class of nonconvex optimization problems
• Douglas--Rachford Splitting and ADMM for Nonconvex Optimization: Tight Convergence Results
• A Lyapunov-type approach to convergence of the Douglas-Rachford algorithm for a nonconvex setting

Mathematics Subject Classification ID

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

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
• Variational Analysis
• On Projection Algorithms for Solving Convex Feasibility Problems
• Convex analysis and monotone operator theory in Hilbert spaces
• On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
• On the \(O(1/n)\) convergence rate of the Douglas-Rachford alternating direction method
• A convergent 3-block semiproximal alternating direction method of multipliers for conic programming with 4-type constraints
• Proximal Alternating Minimization and Projection Methods for Nonconvex Problems: An Approach Based on the Kurdyka-Łojasiewicz Inequality
• On the convergence of von Neumann's alternating projection algorithm for two sets
• Tensor completion and low-\(n\)-rank tensor recovery via convex optimization
• Clarke Subgradients of Stratifiable Functions
• Local differentiability of distance functions
• Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods
• Sparse Approximation via Penalty Decomposition Methods
• New fractional error bounds for polynomial systems with applications to Hölderian stability in optimization and spectral theory of tensors
• The Łojasiewicz Inequality for Nonsmooth Subanalytic Functions with Applications to Subgradient Dynamical Systems
• 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
• Alternating Projections and Douglas-Rachford for Sparse Affine Feasibility
• Recent results on Douglas-Rachford methods for combinatorial optimization problems
• Analysis of the convergence rate for the cyclic projection algorithm applied to basic semialgebraic convex sets
• Alternating Projections on Manifolds
• Nonconvex notions of regularity and convergence of fundamental algorithms for feasibility problems
• Local linear convergence for alternating and averaged nonconvex projections
• Douglas-Rachford feasibility methods for matrix completion problems
• Finding Best Approximation Pairs Relative to a Convex and Prox-Regular Set in a Hilbert Space
• <formula formulatype="inline"><tex Notation="TeX">$L_{1/2}$</tex> </formula> Regularization: Convergence of Iterative Half Thresholding Algorithm

Cited In (78)

• Sequence convergence of inexact nonconvex and nonsmooth algorithms with more realistic assumptions
• A parameterized three-operator splitting algorithm for non-convex minimization problems with applications
• The level-set subdifferential error bound via Moreau envelopes
• Convergence of Bregman Peaceman-Rachford splitting method for nonconvex nonseparable optimization
• Convergence Rate Analysis of a Sequential Convex Programming Method with Line Search for a Class of Constrained Difference-of-Convex Optimization Problems
• Extrapolated plug-and-play three-operator splitting methods for nonconvex optimization with applications to image restoration
• Computable centering methods for spiraling algorithms and their duals, with motivations from the theory of Lyapunov functions
• A partial Bregman ADMM with a general relaxation factor for structured nonconvex and nonsmooth optimization
• Nonconvex multi-period mean-variance portfolio optimization
• Exterior-point optimization for sparse and low-rank optimization
• A new boosted proximal point algorithm for minimizing nonsmooth DC functions
• Convergence of Random Reshuffling under the Kurdyka–Łojasiewicz Inequality
• Convergence analysis of an improved Bregman-type Peaceman-Rachford splitting algorithm for nonconvex nonseparable linearly constrained optimization problems
• A mirror inertial forward-reflected-backward splitting: convergence analysis beyond convexity and Lipschitz smoothness
• A three-operator splitting algorithm for nonconvex sparsity regularization
• Solving nonconvex feasibility problem on a sphere and a closed ball by Douglas-Rachford algorithm
• Local minimizers of semi-algebraic functions from the viewpoint of tangencies
• Low rank pure quaternion approximation for pure quaternion matrices
• Randomized Douglas–Rachford Methods for Linear Systems: Improved Accuracy and Efficiency
• Half-quadratic alternating direction method of multipliers for robust orthogonal tensor approximation
• Clustering multivariate count data via Dirichlet-multinomial network fusion
• Block-coordinate and incremental aggregated proximal gradient methods for nonsmooth nonconvex problems
• Fixed point analysis of Douglas-Rachford splitting for ptychography and phase retrieval
• An extrapolated iteratively reweighted \(\ell_1\) method with complexity analysis
• On polarization-based schemes for the FFT-based computational homogenization of inelastic materials
• Calculus of the exponent of Kurdyka-Łojasiewicz inequality and its applications to linear convergence of first-order methods
• A unified Douglas-Rachford algorithm for generalized DC programming
• An incremental aggregated proximal ADMM for linearly constrained nonconvex optimization with application to sparse logistic regression problems
• On the finite convergence of the Douglas-Rachford algorithm for solving (not necessarily convex) feasibility problems in Euclidean spaces
• Convergence Analysis of the Relaxed Douglas--Rachford Algorithm
• Alternating direction method of multipliers for a class of nonconvex and nonsmooth problems with applications to background/foreground extraction
• Convergence rate analysis for averaged fixed point iterations in common fixed point problems
• Two-stage stochastic variational inequalities: an ERM-solution procedure
• Toward a mathematical theory of the crystallographic phase retrieval problem
• Accelerating the DC algorithm for smooth functions
• Kurdyka-Łojasiewicz exponent via inf-projection
• Global convergence of splitting methods for nonconvex composite optimization
• An inexact proximal gradient algorithm with extrapolation for a class of nonconvex nonsmooth optimization problems
• On the Douglas-Rachford algorithm
• A convergent relaxation of the Douglas-Rachford algorithm
• Projecting onto the Intersection of a Cone and a Sphere
• Douglas-Rachford splitting method for semidefinite programming
• Local convergence of the heavy-ball method and iPiano for non-convex optimization
• Convergence analysis of Douglas-Rachford splitting method for ``strongly + weakly convex programming
• General splitting methods with linearization for the split feasibility problem
• A weakly convergent fully inexact Douglas-Rachford method with relative error tolerance
• Nonnegative low rank tensor approximations with multidimensional image applications
• Malitsky-Tam forward-reflected-backward splitting method for nonconvex minimization problems
• Analysis of the alternating direction method of multipliers for nonconvex problems
• Local linear convergence of the alternating direction method of multipliers for nonconvex separable optimization problems
• SURVEY: SIXTY YEARS OF DOUGLAS–RACHFORD
• Two-stage stochastic variational inequalities: theory, algorithms and applications
• Convergence analysis of the generalized splitting methods for a class of nonconvex optimization problems
• Douglas--Rachford Splitting and ADMM for Nonconvex Optimization: Tight Convergence Results
• A family of projection gradient methods for solving the multiple-sets split feasibility problem
• Comparing averaged relaxed cutters and projection methods: theory and examples
• A Bregman forward-backward linesearch algorithm for nonconvex composite optimization: superlinear convergence to nonisolated local minima
• Peaceman-Rachford splitting for a class of nonconvex optimization problems
• A Symmetric Alternating Direction Method of Multipliers for Separable Nonconvex Minimization Problems
• Unifying abstract inexact convergence theorems and block coordinate variable metric iPiano
• Local linear convergence of the ADMM/Douglas-Rachford algorithms without strong convexity and application to statistical imaging
• A primal Douglas-Rachford splitting method for the constrained minimization problem in compressive sensing
• A note on the Douglas-Rachford splitting method for optimization problems involving hypoconvex functions
• The equivalence of three types of error bounds for weakly and approximately convex functions
• Precompact convergence of the nonconvex primal-dual hybrid gradient algorithm
• The Douglas-Rachford algorithm for convex and nonconvex feasibility problems
• A note on the forward-Douglas-Rachford splitting for monotone inclusion and convex optimization
• An abstract convergence framework with application to inertial inexact forward-backward methods
• A parameterized Douglas-Rachford splitting algorithm for nonconvex optimization
• Hölderian Error Bounds and Kurdyka-Łojasiewicz Inequality for the Trust Region Subproblem
• A new use of Douglas-Rachford splitting for identifying infeasible, unbounded, and pathological conic programs
• Douglas-Rachford splitting and ADMM for nonconvex optimization: accelerated and Newton-type linesearch algorithms
• Two-step inertial Bregman alternating minimization algorithm for nonconvex and nonsmooth problems
• An envelope for Davis-Yin splitting and strict saddle-point avoidance
• A Lyapunov function construction for a non-convex Douglas-Rachford iteration
• A survey on some recent developments of alternating direction method of multipliers
• Convergence analysis of two-step inertial Douglas-Rachford algorithm and application
• A splitting method for finding the resolvent of the sum of two maximal monotone operators

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

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