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

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.

To appear in Mathematical Programming

References in corpus (1)

• A Convergent 3-Block Semi-Proximal Alternating Direction Method of Multipliers for Conic Programming with $4$-Type of Constraints

Cited by in corpus (37)

• Calculus of the exponent of Kurdyka-Łojasiewicz inequality and its applications to linear convergence of first-order methods
• Douglas-Rachford splitting and ADMM for nonconvex optimization: tight convergence results
• Accelerating the DC algorithm for smooth functions
• Convergence rate analysis for averaged fixed point iterations in the presence of Hölder regularity
• A Bregman forward-backward linesearch algorithm for nonconvex composite optimization: superlinear convergence to nonisolated local minima
• Iteratively Linearized Reweighted Alternating Direction Method of Multipliers for a Class of Nonconvex Problems
• The Asynchronous PALM Algorithm for Nonsmooth Nonconvex Problems
• A Proximal Approach for a Class of Matrix Optimization Problems
• Block-coordinate and incremental aggregated proximal gradient methods for nonsmooth nonconvex 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
• Douglas-Rachford splitting and ADMM for nonconvex optimization: Accelerated and Newton-type linesearch algorithms
• FedDR -- Randomized Douglas-Rachford Splitting Algorithms for Nonconvex Federated Composite Optimization
• Alternating Direction Method of Multipliers for A Class of Nonconvex and Nonsmooth Problems with Applications to Background/Foreground Extraction
• Convergence analysis under consistent error bounds
• A Lyapunov function construction for a non-convex Douglas-Rachford iteration
• An abstract convergence framework with application to inertial inexact forward--backward methods
• Primal-Dual Frank-Wolfe for Constrained Stochastic Programs with Convex and Non-convex Objectives
• The Douglas-Rachford Algorithm for Weakly Convex Penalties
• Peaceman-Rachford splitting for a class of nonconvex optimization problems
• Convergence rate analysis of a sequential convex programming method with line search for a class of constrained difference-of-convex optimization problems
• Unifying abstract inexact convergence theorems and block coordinate variable metric iPiano
• Analysis of the alternating direction method of multipliers for nonconvex problems
• A three-operator splitting algorithm for nonconvex sparsity regularization
• Fixed Point Analysis of Douglas-Rachford Splitting for Ptychography and Phase Retrieval
• Stochastic Optimization for DC Functions and Non-smooth Non-convex Regularizers with Non-asymptotic Convergence
• Blind Ptychography by Douglas-Rachford Splitting
• Convergence of Random Reshuffling Under The Kurdyka-Łojasiewicz Inequality
• Low Rank Pure Quaternion Approximation for Pure Quaternion Matrices
• Toward a mathematical theory of the crystallographic phase retrieval problem
• Prior-aware Dual Decomposition: Document-specific Topic Inference for Spectral Topic Models
• Nonnegative Low Rank Tensor Approximation and its Application to Multi-dimensional Images
• A mirror inertial forward-reflected-backward splitting: Global convergence and linesearch extension beyond convexity and Lipschitz smoothness
• Anderson Acceleration for Nonconvex ADMM Based on Douglas-Rachford Splitting
• A UAV-Mounted Free Space Optical Communication: Trajectory Optimization for Flight Time
• Linear convergence of inexact descent method and inexact proximal gradient algorithms for lower-order regularization problems
• A parameterized Douglas-Rachford Splitting algorithm for nonconvex optimization