# Composition of projections has a fixed point in a Hilbert space

Let Let H be a Hilbert space with an inner product ⟨⋅,⋅⟩ : H×H→R, and induced norm $∥⋅∥ : H→R_+$

Let $C_1$ and $C_2$ be closed, convex, nonempty, disjoint subsets of $H$ with at least one of them compact. And $P_X:H→X$ the metric projection onto X, i.e., $P_X(x):=argmin_{y∈X}∥x−y∥$ for convex compact nonempty subsets of H and $x \in H$.

Let $P: C_1 → C_1$ be given by $P(x) = (P_{C_1} \circ P_{C_2})(x)$ for $x \in C_1$

I want to prove the following:

Let $x \in C_1$ fixed, then the succession $(P^n(x))^{\infty}_{n=1}$ converges to a fixed point.

I tried (unsuccessfully) to prove that it $(P^n(x))^{\infty}_{n=1}$ is a Cauchy succession and so it converges to a point in $C_1$, I know that $P_x$ is firmly non-expansive i.e.

$\left\| P_X(x) - P_X(y) \right\|^2 \leq \langle x-y, P_X(x) - P_X(y) \rangle$

and hence non-expansive i.e.

$\left\| P_X(x) - P_X(y) \right\|^2 \leq \left\| x-y\right\|^2$

I also proved previously that if x is a fixed point of P then x minimizes the distance between $C_1$ and $C_2$.

I also tried to prove that $P(x)$ strictly metric i.e. the inequality is strict for every two different points. So I could use some modification of the contraction mapping theorem.

I also believe that P is continuous, because it is a composition of continuous functions, and so there exist a fixed point (either $C_1$ or $C_2$ is compact and convex). Also I've read that any non-expansive function from a closed convex bounded set onto itself has at least one fixed point. However, how can I prove that $(P^n(x))^{\infty}_{n=1}$ converges to a fixed point? Any advice would be greatly appreciated.

I really think that the key is to prove that $(P^n(x))^{\infty}_{n=1}$ is Cauchy, however I haven't been able to prove that.

• Would you mind sharing the proof that $P_X$ is firmly non-expansive? – Jonas Dahlbæk Oct 22 '14 at 9:31

This long answer is based on many little observations; at every step I will use the preceding ones, sometimes implicitly. Tell me if some step is not clear.

Call $P_1:=P_{C_1}$ and $P_2:=P_{C_2}$.
You can assume that $C_1$ is compact (if the compact set is $C_2$, with the following argument you will get that $P_2 P^n(x)$ converges to some $\ell$ fixed by $P_2P_1$, so $P^{n+1}(x)=P_1P_2P^n(x)$ converges to $P_1(\ell)$ which is fixed by $P_1P_2$).

Lemma. Let $x,y\in H$ and form the sequences $(x_n)_{n=0}^\infty$, given by $x_0=x$, $x_{2k+1}=P_2(x_{2k})$, $x_{2k+2}=P_1(x_{2k+1})$, and the similar one, $(y_n)_{n=0}^\infty$, which begins with $y_0=y$. Then $|x_n-y_n|$ is nonincreasing.
Proof. Let us show that
$|x_{2k}-y_{2k}|^2\le(x_{2k}-y_{2k},x_{2k-1}-y_{2k-1})\le|x_{2k-1}-y_{2k-1}|^2\ \ (*)$
(the inequality $|x_{2k+1}-y_{2k+1}|^2\le|x_{2k}-y_{2k}|^2$ is identical). Since $y_{2k}\in C_1$ and $x_{2k}=P_1(x_{2k-1})$ we have $(x_{2k}-y_{2k},x_{2k}-x_{2k-1})\le 0$. In the same way, $(y_{2k}-x_{2k},y_{2k}-y_{2k-1})\le 0$. Adding the two inequalities gives
$(x_{2k}-y_{2k},x_{2k}-x_{2k-1}-y_{2k}+y_{2k-1})\le 0$, which is just the first inequality in $(*)$.
The second one is easier: $|x_{2k}-y_{2k}|=|P_1(x_{2k-1})-P_1(y_{2k-1})|\le|x_{2k-1}-y_{2k-1}|$, so $(x_{2k}-y_{2k},x_{2k-1}-y_{2k-1})\le |x_{2k}-y_{2k}|\cdot|x_{2k-1}-y_{2k-1}|\le|x_{2k-1}-y_{2k-1}|^2$. $\blacksquare$

From the proof we deduce also that $|(x_{2k}-y_{2k})-(x_{2k-1}-y_{2k-1})|\to 0\ \ (**)$: in fact, call $\alpha:=\lim_{k\to\infty}|x_n-y_n|$; then $(*)$ tells us that also $(x_{2k}-y_{2k},x_{2k-1}-y_{2k-1})\to\alpha$, so $|(x_{2k}-y_{2k})-(x_{2k-1}-y_{2k-1})|^2=|x_{2k}-y_{2k}|^2+|x_{2k-1}-y_{2k-1}|^2-2(x_{2k}-y_{2k},x_{2k-1}-y_{2k-1})\to 0.$

From now on $x$ is your given element, so that we have to show that $x_{2k}=P^k(x)$ converges.
Call $d$ the distance between $C_1$ and $C_2$. Since $C_1$ is compact, $C:=C_1-C_2$ is a convex, closed set (this is an easy fact which is true in all Banach spaces). So $z:=P_C(0)$ is the unique vector in $C_1-C_2$ with minimum norm and clearly $|z|=d$.
Write $z=a-b$ with $a\in C_1$ and $b\in C_2$ (this representation is not unique in general!). If you take $y:=a$, obviously $y_1=P_2(a)=b$ (because $b$ is at minimum distance from $a$), $y_2=a$ and so on. Thus $(**)$ gives $(x_{2k}-x_{2k-1})-(a-b)\to 0$, so $x_{2k}-x_{2k-1}\to z$.

Then one would like to use compactness to deduce that a subsequence of $(x_{2k})$ converges, but it is not guaranteed that the limit is $a$. In general it will converge to some other $a'\in C_1$ such that $a'-z\in C_2$ (and $P(a')=a'$).

The trick is to look at $F=\{(a,b)\in C_1\times C_2:a-b=z\}$, which is closed and convex. Taking again $y:=a$, since $y_{2k}=a$, from $(*)$ we deduce that $|x_{2k}-a|$ is nonincreasing, as well as $|x_{2k-1}-b|$. Let's work in $H':=H\times H$ and call $t_k:=(x_{2k},x_{2k-1})$. We have just said that the distance $|t_k-f|$ is nonincreasing for any fixed $f\in F$.

Clearly $P_F(t_k)$ is Cauchy, so it converges to some $p\in F$: in fact, if $i>j$, $|P_F(t_i)-P_F(t_j)|^2\le|P_F(t_j)-t_i|^2-|P_F(t_i)-t_i|^2$ (since the angle between $P_F(t_i)-t_i$ and $P_F(t_i)-P_F(t_j)$ is obtuse) $\le|P_F(t_j)-t_j|^2-|P_F(t_i)-t_i|^2$ (since we know that $|f-t_i|\le|f-t_j|$, where $f:=P_F(t_j)$).

Finally let $(t_{k_n})$ be a subsequence which converges weakly to some $q=(u,v)\in H'$ (it exists since $(t_k)$ is bounded). Since $t_{k_n}=(x_{2k_n},x_{2k_n-1})$ we obtain $x_{2k_n}\rightharpoonup u\in C_1$ and $x_{2k_n-1}\rightharpoonup v\in C_2$ and we know that $x_{2k_n}-x_{2k_n-1}\to z$, so $u-v=z$. Thus $q\in F$. It suffices to check that in fact $p=q$, because then (since this holds for every subsequence $(t_{k_n})$) $t_k\rightharpoonup p$, so $x_{2k}\rightharpoonup u$, so $x_{2k}\to u$ (since $C_1$ is compact and any strongly converging subsequence $x_{2k_n}$ must converge to $u$).
But the fact that $p=q$ is straightforward: $(P_F(t_k)-t_k,P_F(t_k)-q)\le 0$ (since $q\in F$) and we know that $P_F(t_{k_n})-q\to p-q$ and $P_F(t_{k_n})-t_{k_n}\rightharpoonup p-q$, thus in the limit $(p-q,p-q)\le 0$, which gives $p=q$.