Source-linked AI summary
Douglas-Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems
Guoyin Li, Ting Kei Pong
TL;DR
The paper addresses the limited theory for Douglas-Rachford splitting on nonconvex feasibility problems. It analyzes a smooth-plus-proper-closed optimization formulation using a new merit function, establishing convergence under small-step and boundedness conditions and reporting favorable preliminary sparse-recovery comparisons with alternating projections.
Problem
Douglas-Rachford splitting is well understood for convex problems but has incomplete theoretical justification for possibly nonconvex sets.
Method
The paper analyzes Douglas-Rachford splitting for smooth functions with Lipschitz gradients plus proper closed functions, then applies it to squared-distance minimization for nonconvex feasibility.
Results
With a sufficiently small computable step size, cluster points are stationary; semi-algebraicity yields whole-sequence convergence, and compactness of either feasibility set ensures boundedness.
Takeaways & Limitations
Preliminary sparse linear-system experiments indicate that Douglas-Rachford usually outperforms alternating projections in solution quality and iteration count.
Takeaways & Limitations
The feasibility method can stop at a stationary point that is not globally optimal, so it does not guarantee solving the feasibility problem.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper studies Douglas-Rachford splitting beyond convex settings, targeting nonconvex feasibility through a smooth optimization reformulation. It develops convergence results for structured optimization and applies them to feasibility problems, with preliminary experiments favoring the method over alternating projections.
- Feasibility problems seek points in intersections of two closed sets and encompass practical optimization and reconstruction problems.
- Nonconvex Douglas-Rachford behavior remains theoretically incomplete despite successful applications to important nonconvex problems.
- The method minimizes squared distance to a closed convex set subject to membership in a closed set, recasting feasibility as optimization.
- For smooth-plus-proper-closed optimization, a sufficiently small computable step size and a cluster point yield stationarity; semi-algebraicity gives whole-sequence convergence and a local rate.
- For nonconvex feasibility, compactness of either set ensures bounded iterates, while semi-algebraicity ensures convergence of the whole sequence.
- Preliminary sparse linear-system experiments indicate that Douglas-Rachford usually outperforms alternating projections in solution quality and iteration count.
2 Notation and preliminaries
The paper establishes notation for extended-real-valued functions, subdifferentials, distances, projections, and semi-algebraic structures. It also introduces the Kurdyka-Lojasiewicz framework used in the convergence analysis.
- A proper function has a nonempty domain and never takes the value −∞, while a closed function is lower semicontinuous.
- The limiting subdifferential generalizes derivatives and convex subdifferentials, reducing to the gradient for continuously differentiable functions.
- The distance to a set is the infimum norm distance, and closed convex sets have a projection operator denoted by P_S.
- Semi-algebraic sets are finite unions of polynomial equality-and-inequality descriptions, and semi-algebraic functions have semi-algebraic graphs.
- The Kurdyka-Lojasiewicz property uses a concave desingularizing function near a point, and a KL function satisfies it throughout its subdifferential domain.
- Every proper closed semi-algebraic function satisfies the KL property with ψ(s) = cs^(1−θ) for θ ∈ [0,1) and c > 0.
3 Douglas-Rachford splitting for structured optimization
The paper analyzes a direct nonconvex Douglas-Rachford method for minimizing f+g under a computable step-size condition. A merit-function argument establishes stationary-point results, whole-sequence convergence, boundedness, and eventual rates under additional assumptions.
- Problem and method: The method targets minimizing f+g, where f has a Lipschitz continuous gradient and g is proper closed with an easily computable proximal mapping.The paper also notes applications to sparse learning problems with f as a loss and g as a regularizer.
- Merit-function analysis: The Douglas-Rachford merit function is designed to decrease along iterations and supports the convergence analysis.Under the step-size condition, the merit sequence is nonincreasing, and the resulting step differences converge to zero.
- Stationarity: A sufficiently small computable step size and a cluster point imply that the generated sequence yields a stationary point of the optimization problem.The stationary-point conclusion follows by passing to the limit in the optimality relations along a convergent subsequence.
- Global convergence: If f and g are semi-algebraic and the sequence has a cluster point, the whole generated sequence converges.The convergence proof uses the semi-algebraic setting and the associated KL property.
- Convergence rates: The method has an eventual convergence rate characterized by the KL exponent θ, including finite stationarity when θ = 0.For other θ ranges, the paper states corresponding distance-rate conclusions.
- Boundedness and algorithm: The generated sequence is bounded when f and g are bounded below and at least one is coercive, provided the step size satisfies the prescribed condition.The algorithm starts from an initial point and step size, then repeats updates until a termination criterion is met.
4 Douglas-Rachford splitting for nonconvex feasibility problems
The paper applies a damped Douglas-Rachford scheme to nonconvex feasibility by minimizing squared distance to a closed convex set subject to a closed set, establishing boundedness, stationarity, and convergence under explicit assumptions.
- Problem formulation: The feasibility problem is reformulated as minimizing the squared distance to C over D, with projections onto C and D used in the resulting algorithm.The formulation exploits the smoothness and Lipschitz continuity of the squared-distance objective associated with the closed convex set C.
- Convergence guarantees: For sufficiently small step size, the nonconvex DR iteration is bounded when either C or D is compact, and every cluster point is stationary.The boundedness argument uses coercivity when D is compact or when C is compact, allowing the general convergence theorem to apply.
- Convergence guarantees: When C and D are closed semi-algebraic sets, the entire sequence converges to a point whose shared limit is stationary for the feasibility objective.This follows by combining the boundedness and stationarity result with the whole-sequence convergence theorem for semi-algebraic functions.
- Limitation: The method may stop at a non-global stationary point, but a zero squared-distance objective certifies membership in C ∩ D.Thus stationarity alone does not guarantee a feasible point, whereas objective value zero provides a feasibility certificate.
- Extensions: The framework extends to feasibility over multiple compact semi-algebraic sets by representing their product as a single constraint set, with convergence and local rate conclusions under additional conditions.The generalization yields convergence to a point in the product set and provides a local linear rate when the stated regularity condition holds.
- Comparison: Unlike classical DR applied to indicator functions, the damped scheme can converge for examples where the classical method has a discrete limit cycle.The comparison concerns the same pair of sets and highlights the practical effect of the damped formulation.
5 Numerical simulations
The experiments compare the proposed DR splitting method with alternating projection and classical DR on random sparse linear-system instances. The proposed method outperforms alternating projection in iterations and solution quality, while classical DR is slower and produces lower-quality solutions than the proposed method.
- Experimental setup: The study tests DR splitting for finding an r-sparse solution of a linear system against alternating projection and classical DR.The experiments generate random linear systems with sparse solutions and compare the methods on identical instances.
- Experimental setup: 50 random instances are generated for each m = 100, 200, 300, 400 and 500, with n = 4000, 5000 and 6000.Success means a terminal function value below 10^-12, while failure means a value above 10^-6.
- Results: The proposed DR splitting method clearly outperforms alternating projection in both iteration count and solution quality.Both methods fail more often on harder instances with smaller m.
- Results: Classical DR is slower than both proposed DR splitting and alternating projection, with solution quality worse than proposed DR but better than alternating projection.Table 2 reports averaged iterations, terminal function-value extrema, successes, and failures.
6 Concluding remarks
The paper studies convergence of Douglas-Rachford splitting for nonconvex optimization and feasibility problems. A new merit function supports convergence results under a sufficiently small step size and boundedness, while preliminary experiments favor the method over alternating projection for sparse linear systems.
- Theory: The paper establishes global convergence and local convergence rates for DR splitting with a sufficiently small step-size parameter and a bounded generated sequence.The step-size condition uses an explicit threshold.
- Theory: Simple sufficient conditions are provided to guarantee boundedness of the sequence generated by DR splitting.
- Numerical evidence: Preliminary numerical experiments indicate that DR splitting usually outperforms alternating projection in solution quality and number of iterations for sparse linear systems.