Cyclic Relaxed Douglas-Rachford Splitting for Inconsistent Nonconvex Feasibility

This paper analyzes the cyclic relaxed Douglas-Rachford algorithm for inconsistent nonconvex feasibility problems by characterizing its fixed points, relating their shadows to those of the cyclic projections algorithm, and establishing conditions for local quantitative convergence.

The Gist

Imagine you are trying to find a single spot on a map where several different regions overlap. Maybe you are looking for a place that is simultaneously inside a park, a school zone, and a quiet neighborhood.

• The Easy Case (Consistent): If these three areas actually overlap, there is a "sweet spot" where all three meet. Finding this spot is the goal of a feasibility problem.
• The Hard Case (Inconsistent): Sometimes, the areas don't overlap at all. The park and the school zone might be separated by a busy highway. In this case, there is no perfect solution. The goal shifts: instead of finding a point that is in all sets, we want to find a point that is as close as possible to being in all of them simultaneously.

This paper introduces a new mathematical "compass" to help solve these messy, overlapping (or non-overlapping) problems, especially when the shapes of the areas are weird and curvy (nonconvex).

The Old Tools vs. The New Tool

To solve these problems, mathematicians use algorithms that bounce back and forth between the shapes.

1. Cyclic Projections (The Bouncer): Imagine a bouncer who checks if you are in the park. If you aren't, they push you to the nearest edge of the park. Then they check if you are in the school zone, and push you to that edge if you aren't. They keep doing this in a circle.

   • The Problem: If the areas don't overlap, this bouncer gets stuck in a loop, bouncing between the closest edges but never settling down. It can get stuck in a "local minimum," which is like a small valley that looks like the bottom but isn't the true lowest point.

2. Douglas-Rachford (The Rebounder): This is a more complex algorithm. Instead of just pushing you to the edge, it reflects you through the edge (like a mirror) and then takes a step back. It's known for being very good at escaping "bad" local valleys in inconsistent problems. However, in its original form, it can sometimes run off to infinity or behave unpredictably.

3. The New Tool: Cyclic Relaxed Douglas-Rachford:
   The authors of this paper created a "hybrid" tool. Think of it as a dimmer switch between the Bouncer and the Rebounder.

   • They introduced a "relaxation parameter" (let's call it $\lambda$).
   • If you turn the switch all the way to one side, you get the classic Rebounder.
   • If you turn it to the other side, you get the Bouncer.
   • The Innovation: By setting the switch somewhere in the middle, they created an algorithm that keeps the Rebounder's ability to escape bad traps but behaves more like the Bouncer, ensuring it stays within a bounded area and doesn't run off to infinity.

What Did They Discover?

The paper makes three main discoveries about this new hybrid tool:

1. Where does it stop? (Fixed Points)
When you run this algorithm, the point where it finally stops (or circles around) isn't just a random spot. The authors proved that this stopping point is a specific average of points located on the edges of all the different shapes.

• Analogy: Imagine the algorithm is a group of people standing on the edges of different rooms. The final "meeting point" isn't in the middle of nowhere; it's a weighted average of where everyone is standing. This guarantees that if the shapes are bounded, the algorithm won't wander off into the distance.

2. The "Shadow" Trick
The algorithm stops at a point that might look a bit "fuzzy" or off-center. However, the authors showed that if you take that fuzzy point and cast a "shadow" of it onto one of the shapes (by projecting it straight onto the nearest edge), that shadow is extremely close to the solution you would get if you just used the simple Bouncer method.

• Analogy: The algorithm finds a "rough draft" solution. If you shine a light on it to project a shadow onto the wall (the set), that shadow is a very clean, high-quality answer. This explains why, in practice, people often take the final result of these complex algorithms and "clean it up" with one last projection step. The paper proves this isn't just a lucky guess; it's mathematically sound.

3. How Fast Does It Work? (Convergence)
The authors proved that under certain conditions (specifically, if the shapes aren't too jagged or weird), the algorithm doesn't just wander around forever; it actually converges.

• It moves toward the solution at a predictable speed (linear convergence).
• Even if the shapes don't overlap (inconsistent), the algorithm finds the "best possible compromise" and stops there.
• They also defined a "gap" metric. If the shapes don't overlap, the algorithm measures the total distance between the points it finds on each shape. If this total distance is zero, the shapes overlap. If it's greater than zero, that number tells you exactly how "inconsistent" the problem is and how close the solution is to being perfect.

Summary in Plain English

This paper takes a powerful but sometimes unstable mathematical tool (Douglas-Rachford) and adds a "stabilizer" (relaxation) to make it safe for messy, real-world problems where things don't fit together perfectly.

They proved that:

1. The tool will always stay within a reasonable area and won't run away.
2. The final result it gives you is a specific mathematical average of the boundaries of the shapes.
3. If you take that result and project it onto one of the shapes, you get a very high-quality answer that is close to the best possible solution.
4. The tool is guaranteed to find this solution quickly, even when the shapes are weird and don't overlap.

Essentially, they gave us a reliable, mathematically proven way to find the "best possible fit" when nothing fits perfectly.

Technical Summary

Technical Summary: Cyclic Relaxed Douglas-Rachford Splitting for Inconsistent Nonconvex Feasibility

Problem Statement
The paper addresses the feasibility problem of finding a point $z$ that belongs to the intersection of a finite collection of closed subsets $\{A_1, \dots, A_m\}$ in a real Euclidean space. The study specifically targets two challenging scenarios often encountered in practice:

1. Inconsistency: The intersection $\bigcap_{i=1}^m A_i$ is empty.
2. Nonconvexity: The sets $A_i$ are not necessarily convex.

In inconsistent settings, classical projection methods often struggle, and the standard Douglas-Rachford (DR) algorithm, while robust against local minima, typically lacks fixed points and may diverge in convex inconsistent settings. The authors aim to analyze a specific stabilization of the DR algorithm—the Cyclic Relaxed Douglas-Rachford (CRDR) algorithm—to provide theoretical guarantees for local convergence and fixed-point characterization in these difficult nonconvex, inconsistent regimes.

Methodology and Framework
The authors define the CRDR operator $T$ as a composition of relaxed two-set DR operators:
$$T = T_{1,2} \circ T_{2,3} \circ \dots \circ T_{m,1}$$
where each two-set operator is defined as:
$$T_{i,j} = \frac{\lambda}{2}(R_{A_i}R_{A_j} + \text{Id}) + (1-\lambda)P_{A_j}$$
Here, $P_A$ is the metric projector, $R_A = 2P_A - \text{Id}$ is the reflector, and $\lambda \in (0, 1]$ is a relaxation parameter.

• $\lambda = 1$ recovers the standard Cyclic DR operator.
• $\lambda = 0$ recovers the Cyclic Projections operator.

The analysis relies on tools from variational analysis, specifically:

• Set Regularity: Utilizing concepts of prox-regularity and super-regularity at a distance (a property allowing regularity characterization from points outside the set).
• Operator Properties: Characterizing projectors and reflectors as pointwise almost $\alpha$-firmly nonexpansive (a$\alpha$-fne) mappings.
• Metric Subregularity: Using gauge functions to relate the distance to the fixed point set with the distance to the image of the operator.

Key Contributions and Results

1. Characterization of Fixed Points
The paper establishes that fixed points of the CRDR operator are bounded and lie within the convex hull of the sets, even when the problem is inconsistent.

• Theorem 1: Shows that any fixed point $x$ of $T$ can be expressed as a specific linear combination of projections and reflections of points within the sets.
• Boundedness: Unlike the standard DR operator where fixed points may diverge to the horizon as $\lambda \to 1$ in inconsistent cases, the CRDR fixed points remain bounded for $\lambda < 1$ if the sets are bounded.
• Relation to Cyclic Projections: The authors prove that the "shadows" (projections) of CRDR fixed points onto the sets are closely related to the fixed points of the cyclic projections operator.

2. Shadow Analysis and Affine Approximations
A significant portion of the work (Section 3.2) justifies the common heuristic of projecting the final iterate of a DR-type algorithm onto one of the sets to "clean up" the solution.

• Theorem 2: Under assumptions of super-regularity and the existence of linear tangent cones (Shapiro+ property), the projection of a CRDR fixed point onto a set $A_1$ is shown to be an almost fixed point of the cyclic projections mapping.
• Implication: This provides a theoretical basis for using a few iterations of cyclic projections starting from a CRDR fixed point to reach a neighborhood of a cyclic projection fixed point, which represents a local gap between the sets.

3. Local Quantitative Convergence
The paper derives local convergence rates for the CRDR algorithm in the nonconvex, inconsistent setting.

• Theorem 3: Under the assumption that the sets are super-regular and satisfy a metric subregularity condition (specifically, that the distance to the fixed point set is bounded by a gauge function of the residual), the algorithm exhibits local convergence.
• Convergence Rates:
  • If the gauge function is linear (metric subregularity), the algorithm converges R-linearly.
  • The convergence rate depends on the relaxation parameter $\lambda$, the number of sets $m$, and the "violation" of the almost firmly nonexpansive property (which relates to the degree of nonconvexity).
• Corollary 3: The sum of the gaps between successive projections of the iterates converges to a constant $g \ge 0$. If $g=0$, the problem is consistent; if $g>0$, it quantifies the minimal distance between the sets in the inconsistent case.

Significance and Claims
The authors position this work as a bridge between the Cyclic Douglas-Rachford algorithm and the Cyclic Projections algorithm.

• Robustness in Inconsistency: The paper claims that the CRDR algorithm avoids the divergence issues of the standard DR algorithm in inconsistent settings while maintaining the ability to escape bad local minima.
• Generalization: The results extend previous convergence guarantees (which were often limited to convex or consistent cases) to nonconvex and inconsistent feasibility problems.
• Practical Justification: The analysis of "shadows" (Theorem 2) rigorously justifies the practical strategy of post-processing DR iterates with projections, a technique widely used in applications like phase retrieval but previously lacking theoretical grounding in inconsistent nonconvex settings.
• Limitations: The authors note that the primary condition for linear convergence (metric subregularity) is difficult to verify a priori, though they cite empirical evidence from other works suggesting it holds for prox-regular, subtransversal sets.

In summary, the paper provides a rigorous fixed-point and convergence analysis for a relaxed cyclic DR splitting method, demonstrating that it yields bounded solutions and linear convergence rates for inconsistent, nonconvex problems under standard regularity assumptions, while clarifying the relationship between DR iterates and cyclic projection fixed points.