Pith. sign in

REVIEW 2 major objections 5 minor 26 references

On the behaviour of the Douglas-Rachford algorithm for minimizing a convex function subject to a linear constraint

T0 review · 2 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves that the Douglas–Rachford algorithm converges weakly to a minimizer of a shifted convex program even when the original constrained problem has no solution.

desk verdict A genuine advance in Douglas-Rachford theory for inconsistent convex problems, with a clearly flagged but load-bearing infinite-dimensional assumption that slightly narrows the stated scope. read the letter →

arxiv 1908.05406 v2 pith:J7U7IL5H submitted 2019-08-15 math.OC

Heinz H. Bauschke , Walaa M. Moursi This is my paper · ORCID
classification math.OC MSC 49M2765K1090C2547H1449M29
keywords convexoptimizationDouglas-Rachfordalgorithminconsistentconstrainednormalsolutionminimaldisplacementvectorparallelsplittingmethodprojectionoperatorproximalmapping
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The Douglas–Rachford algorithm is a standard splitting method for minimizing the sum of two convex functions; here the two functions are the indicator of a closed linear subspace $U$ and a general convex function $g$. The paper's aim is to understand what the algorithm still does when the problem $\min_{x\in X}(\iota_U(x)+g(x))$ has no solution, because $\operatorname{dom}g$ and $U$ may be disjoint. It proves that if the gap vector $v=P_{U-\operatorname{dom}g}(0)$ is used to shift $g$, then the shadow sequence $P_UT^n x$ (the projection of the iterates onto $U$) converges weakly to a point of $\arg\min(\iota_U+g(\cdot-v))$, and the function values $g(P_g R_U T^n x)$ converge to the infimum of the shifted problem. A sympathetic reader should care because inconsistent constraints appear naturally in feasibility and parallel-splitting problems, and this result shows the algorithm still produces a meaningful normal solution rather than diverging arbitrarily. In particular, it yields a new parallel splitting theorem for minimizing a sum of convex functions under possibly inconsistent constraints.

What carries the argument

The machinery is the minimal displacement vector $v=P_{U-\operatorname{dom}g}(0)$, together with the identity $Z=\arg\min(\iota_U+g(\cdot-v))$ for the normal-solution set $Z=\{x:v\in N_U(x)+\partial g(x-v)\}$. The vector $v$, which is shown to lie in $U^\perp$, converts an inconsistent problem into a consistent shifted one. The proof is carried by the Douglas–Rachford operator $T=\operatorname{Id}-P_U+P_gR_U$ with reflector $R_U=2P_U-\operatorname{Id}$, the generalized fixed-point set $F=\operatorname{Fix}T(\cdot+v)$, and the projection relation $P_UP_F=P_Z$. Once these static identities are in place, a function-value analysis shows that the prox terms $P_gR_UT^n x$ have all weak cluster points in $\arg\min(\iota_{U-v}+g)$ and that $g(P_gR_UT^n x)$ converges to the shifted infimum; Theorem 5.1 then lifts this to weak convergence of the shadow sequence.

What would settle it

Find an infinite-dimensional Hilbert space, a closed linear subspace $U$, and a convex lower semicontinuous proper $g$ for which $v=P_{U-\operatorname{dom}g}(0)$, $Z\neq\varnothing$, and some starting point $x$ produces a shadow sequence $P_UT^n x$ with a weak cluster point outside $\arg\min(\iota_U+g(\cdot-v))$; Theorem 5.1 declares this impossible. A concrete low-cost check is the paper's Example 5.3, where the formula yields $P_UT^n x=0$ for every $n$; a symbolic or numerical run producing any other limit would indicate a failure of the identity $P_UP_F=P_Z$.

Watch

Extended reading notes

Core claim

The central claim, stated in Theorem 5.1, is that for every starting point $x$, $P_UT^n x\rightharpoonup P_Uy(x)\in\arg\min(\iota_U+g(\cdot-v))$ and $g(P_gR_UT^n x)\to\min(\iota_U+g(\cdot-v))$, where $y(x)=\lim_{n\to\infty}P_F(nv+T^n x)$ and $F=\operatorname{Fix}T(\cdot+v)$. In words: even though the original objective $\iota_U+g$ may have infimum $+\infty$, the algorithm converges to a minimizer of the minimally shifted objective $\iota_U+g(\cdot-v)$. The shift $v$ is the projection of $0$ onto $U-\operatorname{dom}g$ and belongs to $U^\perp$, so it measures the geometric gap between the constraint space and the function's domain. The proof works by identifying the normal-solution set $Z=\{x:v\in N_U(x)+\partial g(x-v)\}$ with $\arg\min(\iota_U+g(\cdot-v))$ and by using the projection identity $P_UP_F=P_Z$ to show that every weak cluster point of the shadow sequence is the same point, namely $P_Uy(x)$.

Load-bearing premise

The load-bearing premise is that the shift vector $v$ equals the projection of $0$ onto $U-\operatorname{dom}g$—automatic in finite dimensions but assumed in general Hilbert spaces—along with the assumption that the normal-solution set $Z$ is nonempty; without these, the identity $Z=\arg\min(\iota_U+g(\cdot-v))$ and the weak convergence of the shadow sequence are not established.

Editorial extensions

If this is right

  • If the assumptions hold, the algorithm finds a normal solution even when $U\cap\operatorname{dom}g=\varnothing$: the shadow sequence converges weakly to a minimizer of $\iota_U+g(\cdot-v)$, and the function values $g(P_gR_UT^n x)$ converge to the infimum of $g$ over $U-v$.
  • The identity $Z=\arg\min(\iota_U+g(\cdot-v))$ gives the abstract normal solution an explicit interpretation as the solution of an ordinary shifted convex program, making the normal problem computationally meaningful.
  • For the sum of finitely many convex functions, the product-space formulation (Corollary 6.7) gives convergence of the parallel Douglas-Rachford updates to a minimizer of $\sum_i g_i(\cdot-v_i)$; functions with full domain are unshifted.
  • When $g=\iota_W$ is an indicator, the result reduces to known affine-convex and two-set feasibility behavior: the shadow sequence converges to a point of $U\cap(v+W)$.
  • The theorem covers cases not handled by earlier infinite-dimensional two-indicator results, since it does not require $Z\subseteq F$; Example 5.3 has $Z\cap F=\varnothing$ yet the shadow sequence converges.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial inference: the proved convergence $g(P_gR_UT^n x)\to\min(\iota_U+g(\cdot-v))$ suggests a practical stopping rule based on successive function values; the paper explicitly leaves termination criteria and numerical experiments for future research (Remark 5.7).
  • Editorial inference: because $v$ is characterized as the limit of $(P_U-\operatorname{Id})P_{\operatorname{dom}g}P_U$ (Fact 2.2), one could estimate $v$ on the fly during the iteration and then switch to the shifted problem; this two-phase procedure is not described in the paper.
  • Editorial inference: the proof uses linearity of $U$ in places such as $P_CP_U=P_C$ for $C\subseteq U$, so extending the result to a general closed convex constraint set would require a new argument; a low-cost first check is to reproduce the closed-form predictions of Example 5.3 numerically.
  • Editorial inference: in the parallel-splitting setting, each shift $v_i$ can be read as a measure of how much the $i$-th constraint must be relaxed to make the system consistent; this interpretation is a direct reading of Corollary 6.7, though the paper does not spell it out.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper studies the Douglas-Rachford algorithm for minimizing the sum of an indicator function of a closed linear subspace U and a proper, lower semicontinuous, convex function g in a real Hilbert space, without assuming the sum has a minimizer. The authors introduce the minimal displacement vector v and the normal solution set Z, and under assumptions (9), (10), (11), and (28) — where (28) is proved only in finite dimensions — they establish in Theorem 5.1 that the shadow sequence P_U T^n x converges weakly to P_U y(x) in argmin(ι_U + g(·−v)), and that g(P_g R_U T^n x) converges to the corresponding infimum. The proof combines a function-value analysis (Lemma 4.2), a cluster-point argument (Lemma 4.3), and a uniqueness step using weak-to-weak continuity of P_Z. The paper also provides examples, including counterexamples to natural conjectures, and a parallel-splitting application in Section 6.

Significance. If the result holds as stated, it is a significant extension of Douglas-Rachford convergence theory to inconsistent convex optimization, going beyond prior work restricted to two indicator functions or affine subspaces. The paper contains detailed proofs, a careful statement of assumptions, and instructive examples that delineate the boundary of the theory. The identification of the shifted objective ι_U + g(·−v) is a conceptual contribution, and the parallel-splitting result in Section 6 is a useful application. The proof is mostly self-contained modulo cited facts, and the main theorem is precise and falsifiable.

major comments (2)
  1. [Section 3, after Proposition 3.1] Assumption (28), v = P_{U−dom g}(0), is stated without proof for infinite-dimensional Hilbert spaces; Proposition 3.1(ii) verifies it only when X is finite-dimensional. Since the derived property v ∈ U⊥ (29) is used in Proposition 3.2, Proposition 3.9, Lemma 4.1, Lemma 4.2, Lemma 4.3, and Theorem 5.1, the main theorem's applicability in infinite-dimensional Hilbert spaces is conditional on an unproved identity. The authors should either prove (28) under the standing assumptions (in particular (11)) or, if this is an open question, state it as an explicit limitation and adjust the abstract and introduction so that they do not suggest the result holds for every Hilbert space satisfying (11) alone.
  2. [Theorem 5.1 and assumption (10)] The proof of weak convergence in Theorem 5.1 relies on assumption (10), the weak-to-weak continuity of P_Z. This is a nontrivial restriction: for a general closed convex set Z in an infinite-dimensional Hilbert space, the metric projection need not be weak-to-weak continuous (for example, projection onto the unit ball in ℓ2). The paper does not provide sufficient conditions for (10) beyond the finite-dimensional case, and the infinite-dimensional examples do not verify it. Please add a discussion of (10) and, if possible, examples of infinite-dimensional settings where it holds.
minor comments (5)
  1. [Lemma 4.1(iv)] The claim that all weak cluster points of (P_U T^n x) lie in U∩(v+dom g) is not justified as written, because dom g need not be weakly closed for a proper lower semicontinuous convex function (e.g., g(x)=1/x on R_{++}). The proof appears to rely on this property. Since this item is not used in the subsequent arguments (Lemma 4.3 uses only (i) and (v) together with weak lower semicontinuity of g), please correct the statement or remove it.
  2. [Introduction] The sentence "Under the above assumptions, which we assume for the rest of the paper" appears in the introduction before assumption (28) is introduced later in Section 3. Consider reordering the presentation so that all standing assumptions are listed before the statement of the main result.
  3. [Abstract and Section 5] There are minor typographical issues, such as "optimiz ation" in the abstract and the unnecessary double spacing in "the Douglas-Rachford algorithm" in the introduction.
  4. [Example 5.2] Example 5.2 claims a consequence of Theorem 5.1 without verifying that the example satisfies assumption (10). Please add a note explaining how (10) is obtained in this example.
  5. [Lemma 4.3] In the proof of Lemma 4.3, the notation for limit superior and limit inferior is visually ambiguous; please define the overline/underline notation explicitly.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the main convergence theorem is proved from stated assumptions; the cited prior results are external theorems, not fitted inputs or renamed conclusions.

full rationale

The paper derives Theorem 5.1 as a conditional convergence statement: under assumptions (9), (10), (11), and (28), the shadow sequence P_U T^n x converges weakly to P_U y(x), which lies in argmin(ι_U + g(·−v)), and the function values converge to the minimum. The minimal displacement vector v is defined from the operator T in (8), and the normal solution set Z is defined independently in (9); the theorem then proves convergence of the shadow sequence to an element of Z, rather than assuming it. The proof uses prior results including Fact 2.1 (properties of firmly nonexpansive mappings), Proposition 3.1(ii) (identification of v in finite dimensions), and Proposition 3.9 (Z = P_U(F)). These are published, parameter-free theorems with stated assumptions that do not include the target conclusion, so they are independent support rather than circular self-justification. The paper's self-citations are part of a coherent research program, but they do not smuggle in the conclusion. The only notable caveat is not circular: in infinite-dimensional Hilbert spaces the identity v = P_{U−dom g}(0) is assumed in (28), whereas Proposition 3.1 proves it only in finite dimensions; this makes the main theorem conditional in infinite dimensions, but it is an explicit assumption and limitation, not a definitional or fitted equivalence.

Assumptions & free parameters 0 free parameters · 7 assumptions · 0 invented entities

The theorem is parameter-free; no constants are fitted to data. The central result holds for any proper lsc convex g and any closed linear subspace U provided the stated domain conditions hold. The key assumptions are the existence of normal solutions (Z≠∅), the constraint qualification 0∈U⊥+dom g*, the weak-to-weak continuity of P_Z, and the identification of v as the projection onto U−dom g in infinite dimensions. All are flagged in the paper and some are shown to be necessary by counterexamples.

assumptions (7)
  • standard math X is a real Hilbert space
    Throughout the paper, the ambient space is a real Hilbert space with inner product and induced norm.
  • domain assumption U is a closed linear subspace of X
    The linear constraint is modeled by the indicator of a closed linear subspace.
  • domain assumption g is proper, lower semicontinuous, and convex
    The objective function g is assumed proper, lsc, and convex, ensuring the proximal mapping P_g is well defined.
  • domain assumption Z = { x | v ∈ N_U(x) + ∂g(x−v) } is nonempty
    Existence of normal solutions is essential. Example 3.6 shows that Z can be empty, in which case the target set is empty and the theorem's conclusion is vacuous.
  • domain assumption P_Z is weak-to-weak continuous
    Automatic in finite-dimensional spaces. In infinite dimensions it is needed in Theorem 5.1 to identify the unique weak cluster point of the shadow sequence.
  • domain assumption 0 ∈ U⊥ + dom g*
    A constraint qualification that ensures the Fenchel dual is feasible. Example 5.5 shows that when it fails, the shadow sequence need not converge.
  • domain assumption v = P_{U−dom g}(0)
    Assumed after Proposition 3.1. It holds in finite-dimensional spaces, but in infinite dimensions it is a genuine restriction. It is used to obtain v ∈ U⊥ and to characterize the normal solution set.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the behaviour of the Douglas-Rachford algorithm for minimizing a convex function subject to a linear constraint." pith.science (2026). https://pith.science/paper/J7U7IL5H

@misc{pith2026190805406,
  author       = {Pith},
  title        = {Pith review of: On the behaviour of the Douglas-Rachford algorithm for minimizing a convex function subject to a linear constraint},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/J7U7IL5H}},
  note         = {Machine review of arXiv:1908.05406}
}
read the original abstract

The Douglas-Rachford algorithm (DRA) is a powerful optimization method for minimizing the sum of two convex (not necessarily smooth) functions. The vast majority of previous research dealt with the case when the sum has at least one minimizer. In the absence of minimizers, it was recently shown that for the case of two indicator functions, the DRA converges to a best approximation solution. In this paper, we present a new convergence result on the the DRA applied to the problem of minimizing a convex function subject to a linear constraint. Indeed, a normal solution may be found even when the domain of the objective function and the linear subspace constraint have no point in common. As an important application, a new parallel splitting result is provided. We also illustrate our results through various examples.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

26 extracted references · 25 canonical work pages

  1. [1]

    Banjac, P

    G. Banjac, P . Goulart, B. Stellato, and S. Boyd, Infeasib ility detection in the alternating di- rection method of multipliers for convex optimization, Journal of Optimization Theory and Applications 183 (2019), 490–519

    work page 2019

  2. [2]

    Bauschke and J.M

    H.H. Bauschke and J.M. Borwein, Dykstra’s alternating pr ojection algorithm for two sets, Journal of Approximation Theory 79 (1994), 418–443

    work page 1994

  3. [3]

    Bauschke, J.M

    H.H. Bauschke, J.M. Borwein, and A.S. Lewis, The method of cyclic projections for closed convex sets in Hilbert space, in Recent Developments in Optimization Theory and Nonlinear Analysis (Jerusalem 1995), Contemporary Mathematics 204 (1997), 1–38. 22

    work page 1997

  4. [4]

    Bauschke, R.I

    H.H. Bauschke, R.I. Bot ¸, W.L. Hare, and W.M. Moursi, Attou ch-Th´ era duality revisited: paramonotonicity and operator splitting, Journal of Approximation Theory 164 (2012), 1065– 1084

    work page 2012

  5. [5]

    Bauschke and P .L

    H.H. Bauschke and P .L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces, 2nd edition, Springer, 2017

    work page 2017

  6. [6]

    Bauschke, P .L

    H.H. Bauschke, P .L. Combettes, and D.R. Luke, Finding be st approximation pairs relative to two closed convex sets in Hilbert spaces, Journal of Approximation Theory 127 (2004), 178–192

    work page 2004

  7. [7]

    Bauschke, M.N

    H.H. Bauschke, M.N. Dao, and W.M. Moursi, The Douglas–Rachf ord algorithm in the affine- convex case, Operations Research Letters 44 (2016) 379–382

    work page 2016

  8. [8]

    Bauschke, W.L

    H.H. Bauschke, W.L. Hare, and W.M. Moursi, Generalized sol utions for the sum of two maximally monotone operators, SIAM Journal on Control and Optimization 52 (2014), 1034– 1047

    work page 2014

Show all 26 references
  1. [9]

    Bauschke, W.L

    H.H. Bauschke, W.L. Hare, and W.M. Moursi, On the range of th e Douglas–Rachford oper- ator, Mathematics of Operations Research 41 (2016), 884–897

    2016

  2. [10]

    Bauschke, S.M

    H.H. Bauschke, S.M. Moffat, and X. Wang, Near equality , ne ar convexity , sums of maxi- mally monotone operators, and averages of firmly nonexpansiv e mappings, Mathematical Programming (Series B) 139 (2013), 55–70

    2013

  3. [11]

    Bauschke and W.M

    H.H. Bauschke and W.M. Moursi, The Douglas–Rachford algo rithm for two (not necessarily intersecting) affine subspaces, SIAM Journal on Optimization 26 (2016), 968–985

    2016

  4. [12]

    Bauschke and W.M

    H.H. Bauschke and W.M. Moursi, On the Douglas–Rachford al gorithm, Mathematical Pro- gramming (Series A) 164 (2017), 263–284

    2017

  5. [13]

    Bauschke and W.M

    H.H. Bauschke and W.M. Moursi, On the order of the operator s in the Douglas–Rachford algorithm, Optimization Letters 10 (2016), 447–455

    2016

  6. [14]

    Bauschke, M.M

    H.H. Bauschke, M.M. Dao and W.M. Moursi, The Douglas–Rachfo rd algorithm in the affine- convex case, Operations research Letters 44 (2016), 379–382

    2016

  7. [15]

    Combettes, Iterative construction of the resolve nt of a sum of maximal monotone oper- ators, Journal of Convex Analysis 16 (2009), 727–748

    P .L. Combettes, Iterative construction of the resolve nt of a sum of maximal monotone oper- ators, Journal of Convex Analysis 16 (2009), 727–748

    2009

  8. [16]

    Douglas and H.H

    J. Douglas and H.H. Rachford, On the numerical soluion o f heat conduction problems in two and three variables, T ransactions of the AMS82 (1956), 421–439

    1956

  9. [17]

    Eckstein and D.P

    J. Eckstein and D.P . Bertsekas, On the Douglas-Rachfor d splitting method and the proximal point algorithm for maximal monotone opeators, Mathematical Programming (Series A) 55 (1992), 293–318

    1992

  10. [18]

    Iusem, On some properties of paramonotone operato rs, Journal of Convex Analysis 5 (1998), 269–278

    A.N. Iusem, On some properties of paramonotone operato rs, Journal of Convex Analysis 5 (1998), 269–278

    1998

  11. [19]

    Kaczor and M.T

    W.J. Kaczor and M.T. Nowak, Problems in Mathematical Analysis I , AMS, Providence, Rhode Island, 2000

    2000

  12. [20]

    Knopp, Infinite Sequences and Series , Dover, New York, 1956

    K. Knopp, Infinite Sequences and Series , Dover, New York, 1956

    1956

  13. [21]

    Lions and B

    P .-L. Lions and B. Mercier, Splitting algorithms for the sum of two nonlinear operators, SIAM Journal on Numerical Analysis 16 (1979), 964–979

    1979

  14. [22]

    Liu, E.K

    Y . Liu, E.K. Ryu, and W. Yin, A new use of Douglas-Rachford splitting for identifying infea- sible, unbounded, and pathological conic programs, Mathematical Programming (Series A) 177 (2019), 225–253. 23

    2019

  15. [23]

    Moffat, W.M

    S.M. Moffat, W.M. Moursi and S. Wang, Nearly convex sets: fine p roperties and domains or ranges of subdifferentials of convex functions, Mathematical Programming (Series A) 126 (2016), 193–223

    2016

  16. [24]

    Rockafellar, Convex Analysis, Princeton University Press, Princeton, 1970

    R.T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, 1970

    1970

  17. [25]

    E.K. Ryu, Y . Liu, and W. Yin, Douglas-Rachford splitting and ADMM for pathologi- cal convex optimization, Computational Optimization and Applications 74 (2019), 747–778, https://doi.org/10.1007/s10589-019-00130-9 and also arxiv:1801.06618

    2019 arXiv

  18. [26]

    Svaiter, On weak convergence of the Douglas-Rachf ord method, SIAM Journal on Control and Optimization 49 (2011), 280–287

    B.F. Svaiter, On weak convergence of the Douglas-Rachf ord method, SIAM Journal on Control and Optimization 49 (2011), 280–287. 24

    2011

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.