A Lyapunov Function Construction for a Non-convex Douglas–Rachford Iteration

While global convergence of the Douglas–Rachford iteration is often observed in applications, proving it is still limited to convex and a handful of other special cases. Lyapunov functions for difference inclusions provide not only global or local convergence certificates, but also imply robust stability, which means that the convergence is still guaranteed in the presence of persistent disturbances. In this work, a global Lyapunov function is constructed by combining known local Lyapunov functions for simpler, local subproblems via an explicit formula that depends on the problem parameters. Specifically, we consider the scenario, where one set consists of the union of two lines and the other set is a line, so that the two sets intersect in two distinct points. Locally, near each intersection point, the problem reduces to the intersection of just two lines, but globally the geometry is non-convex and the Douglas–Rachford operator multi-valued. Our approach is intended to be prototypical for addressing the convergence analysis of the Douglas–Rachford iteration in more complex geometries that can be approximated by polygonal sets through the combination of local, simple Lyapunov functions.

O. Giladi has been supported by ARC Grant DP160101537. B. S. Rüffer has been supported by ARC Grant DP160102138. Both authors would like to thank the anonymous referees for their helpful comments.

Authors and Affiliations

1. School of Mathematical and Physical Sciences, University of Newcastle, Callaghan, NSW, 2308, Australia

   Ohad Giladi & Björn S. Rüffer

Corresponding author

Correspondence to Ohad Giladi.

Communicated by Guoyin Li.

Appendix: Proof of Proposition 5.2

We begin by establishing condition (14). The proof for condition (15) is essentially the same and thus omitted for brevity.

1.1 Establishing Condition (14)

We have by Proposition 5.1 that \(T_{A_2,B}\mathbf {x}= \mathbf {p}_2 + \cos \theta _{2}{\mathbf {M}}_{\theta _{2}}\left( \mathbf {x}-\mathbf {p}_2\right) \)\(= \nicefrac {1}{2} \mathbf {e}_1 + \cos \theta _{2}{\mathbf {M}}_{\theta _{2}}\left( \mathbf {x}-\nicefrac {1}{2} \mathbf {e}_1\right) \). If \(\theta _{2}=\nicefrac \pi 2\), then this simplifies further to \(T_{A_2,B}\mathbf {x}= \mathbf {p}_2\), resulting in \(V_{1}(T_{A_2,B}\mathbf {x}) = 1\). We can hence deduce that

Now, if \(\theta _{2}\ne \nicefrac \pi 2\), then we have \(V_1(T_{A_2,B}\mathbf {x}) = \left\| T_{A_2,B}\mathbf {x}- \mathbf {p}_1\right\| ^2 = \left\| T_{A_2,B}\mathbf {x}+ \nicefrac {1}{2} \mathbf {e}_1\right\| ^2 = \left\| \mathbf {e}_1 + \cos \theta _2{\mathbf {M}}_{\theta _{2}}\left( \mathbf {x}-\nicefrac {1}{2} \mathbf {e}_1\right) \right\| ^2 = \left\| \cos \theta _{2}{\mathbf {M}}_{\theta _{2}}\left( \mathbf {x}-\nicefrac {1}{2} \mathbf {e}_1 + S_{\theta _2}\mathbf {e}_1\right) \right\| ^2 = \cos ^2\theta _2\left\| \mathbf {x}-\nicefrac {1}{2} \mathbf {e}_1 +S_{\theta _2}\mathbf {e}_1\right\| ^2\), where \(S_{\theta _2} :=\frac{1}{\cos \theta _2} {\mathbf {M}}_{-\theta _{2}}\) satisfies \(S_{\theta _2}\mathbf {e}_1 = \mathbf {e}_1+\tan \theta _2\mathbf {e}_2\), and so \(-\nicefrac {1}{2} \mathbf {e}_1 + S_{\theta _2}\mathbf {e}_1 = \nicefrac {1}{2} \mathbf {e}_1 + \tan \theta _2\mathbf {e}_2\). The inequality \(V_1(T_{A_2,B}\mathbf {x}) > \rho V_1(\mathbf {x})\) is thus equivalent to \(\cos ^2\theta _2\left\| \mathbf {x}+\nicefrac {1}{2} \mathbf {e}_1 +\tan \theta _2\mathbf {e}_2\right\| ^2 > \rho \left\| \mathbf {x}+\nicefrac {1}{2} \mathbf {e}_1\right\| ^2\). Expanding this gives \(\cos ^2\theta _2\Vert \mathbf {x}+\nicefrac {1}{2} \mathbf {e}_1\Vert ^2\)\(+\)\(2\cos ^2\theta _2\tan \theta _2\langle \mathbf {x}\)\(+\)\(\nicefrac {1}{2} \mathbf {e}_1, \mathbf {e}_2\rangle + \cos ^2\theta _2\tan ^2\theta _2 > \rho \left\| \mathbf {x}+\nicefrac {1}{2} \mathbf {e}_1\right\| ^2\) or, equivalently,

By assumption, we have \(\rho > \cos ^2\theta _2\). Hence, estimate (32) is equivalent to

Completing the square gives

Since \(\theta _2 \in ]0,\pi [\), we have \(\sin \theta _2 > 0\), and so (33) is equivalent to

Since \(\mathbf {p}_1 = -\nicefrac {1}{2} \mathbf {e}_1\), this establishes (14), which contains (31) as a special case.

1.2 An Auxiliary Lemma

Before we can proceed with the proof of the proposition, we need the following auxiliary result, which provides a characterization of the set \(D_3\) defined in (9). Note that since \(A_1\) and \(A_2\) are two non-parallel straight lines, their intersection is a single point.

Lemma A.1

Let \(\mathbf {c}\) be the unique intersection point of \(A_1\) and \(A_2\). Then,

and we have

where \(\mathbf {n}_1\), \(\mathbf {n}_2\), are given by

Proof

The line \(A_1\) is the collection of all points \(\mathbf {x}\in {\mathbb {R}}^2\) that satisfy \(\langle \mathbf {x},\mathbf {e}_1\rangle \sin \theta _1\) − \(\langle \mathbf {x},\mathbf {e}_2\rangle \cos \theta _1\)\(+\)\(\nicefrac {1}{2} \sin \theta _1 = 0\). Similarly, the line \(A_2\) is the collection of all points \(\mathbf {x}\in {\mathbb {R}}^2\) that satisfy \(\langle \mathbf {x},\mathbf {e}_1\rangle \sin \theta _2 - \langle \mathbf {x},\mathbf {e}_2\rangle \cos \theta _2 - \nicefrac {1}{2}\sin \theta _2 = 0\). Solving these two equations implies that the intersection point \(\mathbf {c}\) between \(A_1\) and \(A_2\) is indeed given by (34). Now, the (normalized) normal vectors to the lines splitting the angles between \(A_1\) and \(A_2\) are given by (35) and (36) and this completes the proof of the auxiliary lemma. \(\square \)

We are now in a position to establish condition (16). The proof of condition (17) follows closely that of condition (16) and is thus omitted for reasons of space.

1.3 Establishing Condition (16)

Since the direction vector of \(A_i\) is \((\cos \theta _i, \sin \theta _i)\), \(\mathbf {d}_{i}^{\perp }:=(\sin \theta _i, -\cos \theta _i)\) is a normal vector to \(A_{i}\) and the distance of a point Q to \(A_{i}\) is given by \(|\langle Q-\mathbf {p}_{i},\mathbf {d}_{i}^{\perp }\rangle |\). We compute

and

Now, since \(\theta _1 \in ]0,\pi /2]\) and \(\theta _2\in ]\theta _{1},\pi [\), we have \(|\cos \theta _1\cos \theta _2| < 1\), \(\cos ^{2}\theta _{i}<1\), \(\sin \theta _2 > 0\), and \((1+\sin \theta _{1})(1+\sin \theta _{2}) > 1\). Since we assumed that \(\rho \ge (1+\sin \theta _{1})(1+\sin \theta _{2})\), we have \(|\cos \theta _1\cos \theta _2|< 1 < \rho \). With these estimates, we can bound (37) generously as

and simplify (38) to

In light of (39) and (40), \(A_{1}\) is the closer line to \(\mathbf {p}_1+\frac{\cos \theta _2\sin \theta _2}{\rho -\cos ^2\theta _2}\mathbf {e}_2\), so it follows that \(\mathbf {p}_1+\frac{\cos \theta _2\sin \theta _2}{\rho -\cos ^2\theta _2}\mathbf {e}_2 \in D_1\). Therefore, in order to prove (16), it is enough to show that

that is, we want the radius of the ball to be smaller than the distance of the center to the boundary of \(D_1\) (which is exactly \(D_3\)). Now, by the auxiliary Lemma A.1, we have

By squaring both sides of (41) and using (42), we need to establish that

Using (34)–(36), as well as standard trigonometric identities, the right-hand side simplifies to

so that we need to verify two inequalities, both of which can be simplified further. Starting with (43), we take a common denominator and extract common factors. Using that \(0<\theta _{2}<\pi \), \(\sin ^{2}\theta _{2}>0\), and \(\rho >\cos ^{2}\theta _{2}\), as well as trusty trigonometric identities, we simplify (43) to

A similar argument can be made for (44), which simplifies to

For \(\rho > 0\), the left-hand side of (45) is greater than the left-hand side of (46). So it is sufficient to verify that (46) holds.

The roots of the quadratic polynomial in \(\rho \) on the left-hand side of (46) are \(\rho _{1,2} = 1+\sin \theta _1\sin \theta _2 \pm (\sin \theta _1 + \sin \theta _2)\), so that (46) holds whenever \(\rho \) is larger or equal to the larger of the two roots, i.e.,

which establishes (16).

This completes the proof of the proposition.\(\square \)

Reprints and permissions