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.

  • $\begingroup$ Would you mind sharing the proof that $P_X$ is firmly non-expansive? $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.