Hi: I've been reading an optimization text by Charles Byrne, "A First Course In Optimization". I'm currently going through the chapter where he explains things about convex sets and convex functions and projections. The material is explained well but it's also quite terse. My question has two parts.
1) Does anyone know of a text or notes that provide figures which give the geometric intuition behind the various projection/convex relations. I have Rockefellar and Lemarchal but they're not helpful for helping my brain with intuition.
2) I think that, based on a previous question that was answered beautfully and a comment in Byrne's text, I finally understand what is meant by a subspace on $R^{n}$. Byrne explains the following:
Suppose one takes $R^{3}$. Then the xy plane is a subspace, W, of $R^{3}$ and the z plane is the W_perp because it is normal to the xy plane.
Of course, this is a very visual and straightforward example.
But, this simple example and the answer to my previous question gave me some intuition that I wanted to confirm.
Slightly more generally speaking than the $R^{3}$ example above , is it okay to think of the subspace as a subset of some larger space, $R^{n}$ where the dimensions that are lost ( the ones that don't belong to the subspace ) are perpendicular to the resulting subspace.
This would then make the relation
$< x - P_{c}(x), P_{c}(y) - P_{c}(x) > = 0$ where c belong to some subspace C
understandable in the following way.
As x moves away from it's projection ( which is represented by the first term ) and $P_{c}(y)$ moves away from the same projection ( which is represented by the second term ), these two vectors must be perpendicular to each other. This is because $P_{c}(y)$ belongs to C and $x - P_{c}(x)$ doesn't and is perpendicular to all c belonging to C. Therefore, the dot product of the two vectors has to be zero.
My thinking is that, in general, if a vector x belongs to $R^{n}$ and another vector $y$ belongs to a subspace of $R^{n}$ called C, then $x - P_{c}(x)$ is orthogonal to any vector belonging to the subspace C.
Hopefully this is correct but I'm still not clear on the concept of linear manifold and why it's not necessarily a subspace. I'm gonna read about that some more. Thank you for any wisdom or intuitive references or even a good online class related to this material. To my brain, this material is sort of "advanced linear algebra".
1. Projection onto a halspace
Proposition. If $C\subset\mathbb{R}^n$ is a subspace then $$ \langle x-P_C(x), y-P_C(x)\rangle=0 \quad \forall y\in C. $$ Proof. By the property of the metric projection, we have $$ \langle x-P_C(x), u-P_C(x)\rangle\leq 0 \quad \forall u\in C. $$ Substituting $u=y\in C$ and $u=2P_C(x)-y\in C$ into above inequality we obtain $$ \langle x-P_C(x), y-P_C(x)\rangle\leq 0, $$ $$ \langle x-P_C(x), P_C(x)-y\rangle\leq 0. $$ Therefore $$ \langle x-P_C(x), y-P_C(x)\rangle=0 \quad \forall y\in C. $$
2. Linear manifold
Definition. A set $S\subset\mathbb{R}^n$ is called a subspace if for all $x,y\in S, \lambda\in\mathbb{R}^n$ we have $$ \lambda x\in S, x+y\in S. $$
REM Let $\lambda=0$ and $x\in S$. We have $0=\lambda x\in S$.
Definition. A set $M\subset\mathbb{R}^n$ is called a linear manifold if $$ x,y\in M\;\Longrightarrow\;tx+(1-t)y\in M (\forall t\in\mathbb{R}). $$ Geometrical meaning.
A linear manifold is a translation of a subspace.
$M\subset\mathbb{R}^n$ is a linear manifold iff $M$ contains the straight line connecting any two points belonging to $M$.
Example.
(1) In $\mathbb{R}$:
$\{0\}$ and $\mathbb{R}$ are subspaces;
A point and the whole space $\mathbb{R}$ are linear manifolds.
(2) In $\mathbb{R}^2$:
$\{0\}$, straight lines go through origin, $\mathbb{R}^2$ are subspaces;
A point, a line, and the whole space $\mathbb{R}^2$ are linear manifolds.
(3) In $\mathbb{R}^3$:
$\{0\}$, straight lines, planes go through origin, $\mathbb{R}^3$ are subspaces;
A point, a line, a plane and the whole space $\mathbb{R}^3$ are linear manifolds.
(4) In $\mathbb{R}^n$: A point, a line, a plane, a subspace, a hyperplane and the whole space $\mathbb{R}^n$ are linear manifolds.
Relationships of linear manifolds and subspaces
Proposition 1. If $M\subset\mathbb{R}^n$ is a subspace then $M$ is a linear manifold containing $0$.
Proof. Let $x,y\in M, \lambda\in\mathbb{R}$. Since $M$ is a subspace, $\lambda x+(1-\lambda)y\in M$. Hence, $M$ is a linear manifold. Certainly, $0\in M$.
Proposition 2. Let $M\subset\mathbb{R}^n$ be a linear manifold and $0\in M$. Then $M$ is a subspace of $\mathbb{R}^n$.
Proof. Suppose that $M$ is a linear manifold. Let $x,y\in M, \lambda\in\mathbb{R}$. Since $0\in M$ and $M$ is a linear manifold $$ \lambda x=\lambda x+(1-\lambda)0\in M, $$ $$ x+y=2[(1/2)x+(1/2)y]+(-1)0\in M. $$ Hence, $M$ is a subspace.
Proposition 3. Let $M\subset\mathbb{R}^n$. Then, M is a linear manifold if and only if there exists a subspace $S\subset\mathbb{R}^n$ and a vector $a\in\mathbb{R}^n$ such that $M=S+\{a\}$.
Proof. Suppose $M$ is a linear manifold. Let $a\in M$ and put $S:=M-a$. We will prove that $S$ is a subspace of $\mathbb{R}^n$. Indeed, lẹt $x,y\in M-a, \lambda\in\mathbb{R}$. Then there exist $x_a, y_a\in M$ such that $$ x=x_a-a; y=y_a-a; $$ We have $\lambda x+(1-\lambda)y=\lambda (x_a-a)+(1-\lambda)(y_a-a)=[\lambda x_a+(1-\lambda)y_a]-a\in M-a=S$ since $M$ is a linear manifold. Hence $S$ is a linear manifold. Since $0=a-a\in M-a=S$, $M$ is a subspace by Proposition 2.
Suppose that $M=S+a$ with $S$ is subspace of $\mathbb{R}^n$ and $a\in \mathbb{R}^n$. Let $x,y\in M, \lambda\in\mathbb{R}$. Then there exists $x_a, y_a\in S$ such that $x=x_a+a, y=y_a+a$. We have $$ \lambda x+(1-\lambda)y=\lambda(x_a+a)+(1-\lambda)(y_a+a)=[\lambda x_a+(1-\lambda)y_a]+a\in S+a=M $$ since $S$ is subpsace. Hence, $M$ is a linear manifold.