a) For any $\textbf{x} \in \textbf{V}$, there exists a unique $\Pi \textbf{x} \in \textbf{C}$ such that $$ \|\textbf{x} - \Pi \textbf{x}\| = \min_{\textbf{y} \in \textbf{C}}\|\textbf{x}-\textbf{y}\| $$ b) $\textbf{y}_o \in C$ equals $\Pi \textbf{x}$ exactly when (iff) $$ \langle \textbf{x}- \textbf{y}_o, \textbf{y} - \textbf{y}_o \rangle \leq 0 \text{ for all }\textbf{y} \in \textbf{C} $$ c) If \textbf{C} is a closed convex cone, then $\textbf{y}_o \in \textbf{C}$ equals $\Pi \textbf{x}$ iff $$ \langle\textbf{x} - \textbf{y}_o, \textbf{y}_o \rangle = 0 \text{ and } \langle\textbf{x} - \textbf{y}_o, \textbf{y} \rangle \leq 0 \text{ for all } \textbf{y} \in \textbf{C} $$ d) If \textbf{C} is a closed linear subspace \textbf{V}, then $\textbf{y}_o \in \textbf{C}$ equals $\Pi \textbf{x}$ iff $$ \langle\textbf{x} - \textbf{y}_o, \textbf{y} \rangle = 0 \text{ for all } y \in \textbf{C} $$ e) For any two points $\textbf{x}_1$, $\textbf{x}_2 \in \textbf{V}$, $$ \|\Pi \textbf{x}_1 - \Pi \textbf{x}_2\| \leq \|\textbf{x}_1 - \textbf{x}_2\| $$
Let $\textbf{V} = \mathbb{R}^4$ and $\textbf{C}:=\{\textbf{x} \in \mathbb{R}^4: \textbf{x}_1\leq \textbf{x}_2\leq \textbf{x}_3 \leq \textbf{x}_4\}$. Prove that $\textbf{C}$ is a closed convex cone. Guess the projection $\Pi_c\textbf{x}$ of the vector $\textbf{x}:=(3,1,5,3)^\top$ onto $\textbf{C}$. Check that your guess ir right by verifying that $\textbf{(b)}$ or $\textbf{(b')}$ of the main theorem about metric projection holds
$\textbf{answer}$: Let us prove that $C\{x\in \mathbb{R}^{4+}, x_1 \leq x_2 \leq x_3\leq x_4\}$ is a closed convex cone:
$\forall m \in \mathcal{N}$, $\forall \lambda_1,...\lambda_m \geq 0$, $\forall x_1, ... x_m \in C$ we note:
$$ x_i = (x_i^{(1)}, x_i^{(2)}, x_i^{(3)}, x_i^{(4)})^\top $$ $$ y = \sum_{i = 1}^m \lambda_i x_i = (y^{(1)}, y^{(2)}, y^{(3)}, y^{(4)})^\top $$ as $\forall j \in \{1, ..., m\}, x_i \in C: x_i^{(1)} \leq x_i^{(2)}\leq x_i^{(3)} \leq x_i^{(4)})$ and as $\forall i \in \{1, ..., m\}, \lambda_i \geq 0: x_i \in C: \lambda_ix_i^{(1)} \leq \lambda_ix_i^{(2)}\leq \lambda_ix_i^{(3)} \leq \lambda_ix_i^{(4)})$ Then \begin{align*} \sum_{i = 1}^m\lambda_ix_i^{(1)}&\leq \sum_{i = 1}^m\lambda_ix_i^{(2)}\leq \sum_{i = 1}^m\lambda_ix_i^{(3)}\leq \sum_{i = 1}^m\lambda_ix_i^{(4)}\\ y^{(1)} &\leq y^{(2)} \leq y^{(3)} \leq y^{(4)} \end{align*} $$ y = \sum_{i = 1}^m \lambda_i x_i \in C $$ Therefore $C$ is a convex cone \subsection{C is closed} Useful property:
If $(u_n)_{n\in \mathbb{N}}, (v_n)_{n\in \mathbb{N}} \in \mathbb{R}^{\mathbb{N}}$, $u_n \rightarrow \infty$ (for $n\rightarrow \infty$) and $v_n \rightarrow \infty$ (for $n\rightarrow \infty$) and suppose that $\forall n \in \mathbb{N}$, $u_n \leq v_n$. Then $u \leq v$
Proof
Suppose by contradicion that $u - v > 0$ and define $\varepsilon = u - v$.
As $u_n \xrightarrow[n\to \infty] {}u$, $\exists n_1 \in \mathbb{N}, \forall n \geq n_1$, $-\varepsilon / 3 \leq u - u_n \leq \varepsilon/3 \quad \textbf{(1)}$
As $v_n \xrightarrow[n\to \infty] {}v$, $\exists n_2 \in \mathbb{N}, \forall n \geq n_2$, $-\varepsilon / 3 \leq v - v_n \leq \varepsilon/3 \quad \textbf{(2)}$
Then for $n \geq \max (n_1, n_2)$ \begin{align*} \varepsilon &= u - v \\ &= \underbrace{u - u_n}_{\le \varepsilon/3} \underbrace{- \underbrace{(v-v_n)}_{\le \varepsilon/3}}_{> \varepsilon/3} + u_n - v_n \quad \textbf{(3)}\\ &\le \varepsilon/3 + \varepsilon/3 \quad \textbf{(4)} \quad \text{contradiction as } \varepsilon >0 \end{align*}
Now for all $(x_n)_{n\in \mathbb{N}}\in C^{\mathbb{N}}$ such that $x_n \xrightarrow[n \to \infty]{} x$, we have: $\forall n\in \mathbb{N} x_n^{(1)}\leq x_n^{(2)}\leq x_n^{(3)}\leq x_n^{(4)}$ and thanks to the previous property we conclude that: $ x^{(1)}\leq x^{(2)}\leq x^{(3)}\leq x^{(4)}: x\in C$ $C$ is closed.
One can guess that the projection of the vector $x: (3,1,4,3)^\top$ on $C$ is: $\Pi_C(x): (2,2,4,4)^\top \quad \textbf{(5)}$. Indeed, $2\leq 2\leq 4\leq 4$ so $(2,2,4,4)^\top\in C$ and $\forall y = (y^{(1)}, y^{(2)}, y^{(3)}, y^{(4)}) \in C$: \begin{align*} \langle x - \Pi_C(x), y - \Pi_C(x)\rangle &= \langle(1, -1, 1, -1)^\top, (y^{(1)}-2, y^{(2)}-2, y^{(3)}-4, y^{(4)}-4)^\top \rangle \\ &=(y^{(1)}-2) - (y^{(2)}-2) + (y^{(3)}-4)-(y^{(4)}-4)\\ &=y^{(1)}-y^{(2)}+y^{(3)}-y^{(4)} - 0 \le 0 \quad \textbf{(6)} \end{align*} we have (b)
As for (c) \begin{align*} \langle x - \Pi_C(x), \Pi_C(x)\rangle &= \langle(1, -1, 1, -1)^\top, (2, 2, 4, 4)^\top \rangle \\ &=0\\ \langle x - \Pi_C(x), y \rangle &= y^{(1)} - y^{(2)} + y^{(3)} - y^{(4)}\le 0 \quad \textbf{(7)} \end{align*} My questions:
- In (1) and (2) where does the "3" from the the expression $\varepsilon /3$ come from?
- How can we get from (3) to (4)
- How can we guess the statement in (5)
- How can we state that the 2 inequalities hold in (6) and (7)