Find your next learning step
Douglas-Rachford’s main iterates may live outside the constraints or even drift, while projected shadows carry the feasible or best-approximation meaning.
Open the chapter contents · Topology root · Gold Standard of Education · How X Works
Chapter contents
Choose the route closest to the question, or read from Chapter 1 for the complete argument. The chapters remain open on the page; these grouped routes are an index.
Route 1 · Define the operator
Route 2 · Work reflection ledgers
Route 3 · Read shadows and transfer
Route 4 · Check limits and evidence
Route 5 · Ask and continue
CHAPTER 1 OF 12 · DEFINE THE OPERATOR
1. Reflect first, then inspect the shadow
Alternating projections move directly between constraint sets. Douglas–Rachford uses reflections and averages, producing a main sequence that may live outside both sets. The meaningful feasible or best-approximation information is often carried by a projected shadow sequence.
That distinction matters most when constraints are inconsistent. The main iterates may drift even while their shadows identify a stable nearest pair. Convergence claims must say which sequence is converging and what problem its limit solves.
CHAPTER 2 OF 12 · DEFINE THE OPERATOR
2. The two-set operator
For a closed convex set A, let P_A be the nearest-point projector and R_A=2P_A−I its reflector. A common Douglas–Rachford operator is T=½(I+R_B R_A). Starting from x⁰, compute xᵏ⁺¹=T xᵏ.
The main iterate xᵏ is algorithmic state. A shadow such as P_A xᵏ is the quantity compared with the original feasibility problem. Reversing A and B changes the main operator and can change intermediate behaviour, so the order should be recorded.
CHAPTER 3 OF 12 · WORK REFLECTION LEDGERS
3. A consistent reflection ledger
Let A be the x-axis and B the y-axis in the plane. Start at x⁰=(2,1). Projection onto A gives (2,0), so R_A x⁰=(2,−1). Reflecting that point across B gives (−2,−1). Averaging with x⁰ gives x¹=(0,0), the intersection.
| Quantity | Value | Role |
|---|---|---|
| x⁰ | (2,1) | Main starting point |
| P_A x⁰ | (2,0) | First shadow |
| R_A x⁰ | (2,−1) | Reflection across A |
| R_B R_A x⁰ | (−2,−1) | Second reflection |
| x¹ | (0,0) | Averaged iterate and feasible point |
This one-step example is unusually simple. In general, the main sequence can approach a fixed point outside the intersection while its shadow approaches a feasible point.
CHAPTER 4 OF 12 · WORK REFLECTION LEDGERS
4. Inconsistent parallel lines
Now let A={y=0} and B={y=1}. They do not intersect. Start at x⁰=(2,3). Reflecting across A gives (2,−3); reflecting that across B gives (2,5); averaging with x⁰ gives x¹=(2,4). Each cycle increases the main y-coordinate by one.
| k | Main iterate xᵏ | A-shadow P_A xᵏ | Paired B point P_B R_A xᵏ |
|---|---|---|---|
| 0 | (2,3) | (2,0) | (2,1) |
| 1 | (2,4) | (2,0) | (2,1) |
| 2 | (2,5) | (2,0) | (2,1) |
Calling the run a failure because xᵏ diverges misses the stable shadow. Calling it feasible would also be wrong because the sets are disjoint.
CHAPTER 5 OF 12 · WORK REFLECTION LEDGERS
5. The minimal displacement vector
For inconsistent problems, the displacement x−Tx and its limiting geometry describe how far the constraints are from compatibility. In the parallel-line example, every cycle translates by (0,1), matching the gap direction between the sets up to the operator convention.
The associated normal problem perturbs one set by the minimal displacement so that a consistent surrogate can be solved. State that surrogate explicitly; it is not the original empty intersection.
CHAPTER 6 OF 12 · READ SHADOWS AND TRANSFER
6. Shadow sequences carry the original meaning
A fixed point of the Douglas–Rachford operator is not automatically a point satisfying both constraints. In the consistent convex setting, projecting the fixed point can recover a solution. In inconsistent settings, shadow limits can solve a best-approximation or normal problem under additional conditions.
Therefore save main iterates, both relevant shadows, set violations and the distance between paired shadow points. A graph of only ||xᵏ⁺¹−xᵏ|| can conceal a useful shadow or a persistent translation.
CHAPTER 7 OF 12 · READ SHADOWS AND TRANSFER
7. Changed-context transfer: curved disjoint sets
Parallel affine sets make the shadow pair constant. Replace one line with a closed disk that does not meet the other set. The nearest pair may be unique, but the main dynamics and shadow convergence need a theorem suited to the new geometry.
The transfer check is to compare the observed limit with a direct best-approximation solution, then vary initialization. This extends Dykstra’s best-approximation method: Dykstra targets projection onto a nonempty intersection, while Douglas–Rachford shadows can retain meaning in some inconsistent settings.
CHAPTER 8 OF 12 · READ SHADOWS AND TRANSFER
8. Order, relaxation and implementation
Implement the declared operator exactly. T_AB=½(I+R_B R_A) and T_BA=½(I+R_A R_B) are related but not identical step by step. A relaxation parameter changes the average and its stability range.
Test projectors and reflectors separately. Verify R_A x=2P_A x−x and compare a small run with hand arithmetic. Do not reset the main iterate to its shadow between cycles unless a different algorithm is intended.
CHAPTER 9 OF 12 · CHECK LIMITS AND EVIDENCE
9. Limits and common misconceptions
Convex results do not transfer automatically to nonconvex sets. Projectors can be multivalued, cycles can appear and a shadow may converge to a locally meaningful point or fail to converge. Numerical success on one initialization is not a global guarantee.
Douglas–Rachford is also not simply “faster alternating projections”. It changes the state, operator and proof. The useful comparison is target, assumptions, per-iteration cost and verified stopping evidence.
CHAPTER 10 OF 12 · CHECK LIMITS AND EVIDENCE
10. Practical evidence checklist
Record the set definitions, projection formulas, operator order, relaxation, initial point and stopping tolerances. Monitor main displacement, each shadow’s set membership, paired-shadow distance and objective value for any normal or best-approximation problem.
For inconsistent constraints, estimate the minimal displacement and show the perturbed problem being solved. Compare with alternating, cyclic or direct optimisation on a small instance. Preserve counterexamples where the expected guarantee fails.
CHAPTER 11 OF 12 · ASK AND CONTINUE
11. Frequently asked questions
Which sequence should be returned?
Return the sequence tied to the application and theorem—often a projected shadow—not the main iterate by habit.
Does a diverging main sequence mean there is no useful answer?
No. In some inconsistent convex problems, shadows converge to a normal solution or nearest pair. Verify the applicable assumptions.
Can reflections increase distance dramatically?
Yes. Reflectors are not feasibility steps. Their composition and averaging create the Douglas–Rachford operator; interpret the combined iteration.
CHAPTER 12 OF 12 · ASK AND CONTINUE
12. Sources and next reading
Bauschke and Moursi analyse the general and inconsistent method in On the Douglas–Rachford Algorithm and later establish shadow and value convergence for possibly inconsistent optimisation problems. Their affine-subspace study gives exact behaviour for two not-necessarily-intersecting affine subspaces. The coordinate ledgers above are original teaching examples.
Continue through the Topology root, Dykstra’s algorithm, alternating projections and cyclic projections. The Gold Standard of Education and How X Works provide the wider learning route.
Top · Contents · Previous · How X Works