How to conclude $ \left\lVert x_k - \bar x \right\rVert_2 \le \left\lVert x_0 - \bar x \right\rVert_2$

Question

There are 2 intersecting convex sets and I am discussing about alternating algorithm related to those convex sets.

I obtain the following results

$ \left\lVert y_k - \bar x \right\rVert_2^2 \le \left\lVert x_k - \bar x \right\rVert_2^2 - \left\lVert y_k - x_k \right\rVert_2^2 $

$ \left\lVert x_{k+1} - \bar x \right\rVert_2^2 \le \left\lVert y_k - \bar x \right\rVert_2^2 - \left\lVert x_{k+1} - y_k \right\rVert_2^2 $

How can I conclude following

$ \left\lVert x_k - \bar x \right\rVert_2 \le \left\lVert x_0 - \bar x \right\rVert_2$

Answer 1

Use the first inequality in the second:

\begin{align*} \|x_{k+1}-\bar x\|_2^2&\le \|y_k-\bar x\|_2^2-\|x_{k+1}-y_k\|_2^2\\ &\le \|x_k-\bar x\|_2^2-\|y_k-x_k\|_2^2-\|x_{k+1}-y_k\|_2^2\\ &\le\|x_k-\bar x\|_2^2. \end{align*}

Since a norm is nonnegative, this means that $$\|x_{k+1}-\bar x\|_2\le \|x_k-\bar x\|_2.$$

In other words, the sequence $e_k=\|x_k-\bar x\|_2$ is decreasing. As a result, $e_k\le e_0$.