Constrained optimization of l2 norm Consider the problem $min_{x}||x-a||_{2}^{2}$ such that $||x||_{p}\leq 1$ in two dimension. Solve the problem geometrically for the cases $p=1, 2, \infty $ Sketch the solution in the case $||a||_{p}\ge1$
My Attempt for $p =1$ : 

 A: Partial answer:
In all cases, if $\|a\|_p \le 1$ then the solution is $x=a$.
So, suppose $\|a\|_p > 1$.
If $p=2$, the unit ball is a sphere, and so geometrically we see that the
nearest point is on the line through the origin and $a$, and so the solution
is $x = {1 \over \|a\|_2} a$.
In particular, note that we can always write $x = t a +v$, where $v \bot a$. Then
$\|x-a\|_2^2 = \| (t-1)a + v\|_2^2 = |t-1|\|a\|_2^2 + \|v\|_2^2$, hence we can take
$v=0$, so the solution lies on the line passing through the origin and $a$. Since
$\|x\|_2 \le 1$, we have $|t| \le {1 \over \|a\|_2} < 1$, so the solution is $t={1 \over \|a\|_2}$, or $x = {1 \over \|a\|_2} a$.
The cases $p=1, p=\infty$ do not have such a straightforward solution.
First a geometric characterisation of a solution: Suppose we have a closed
convex set $C$ and some point $a \notin C$. Then $n \in C$ is the nearest
point in $C$ to $a$ iff there is some hyperplane (line in the plane) $H$
containing $n$ such that $C$ lies on the other side of $H$ to $a$ and the normal
of $H$ is parallel to $a-n$.

Now consider the situation for $p=\infty$ as this is easier to illustrate
and the case for $p=1$ similar. 
Note the 8 regions outside $C$ in the diagram below. Basically there are
two types, 'corner' regions and 'edge' regions.
Suppose $a_1$ is in an
edge region as below. Then the upper edge of $\overline{B}_\infty(0,1)$
defines a hyperplane $H_1$ and we can find a point $n_1$ on the hyperplane such that
$a_1-n_1$ is perpendicular to the hyperplane. Hence $n_1$ is a solution.
If $a_2$ is in the corner region, then we can find a hyperplane $H_2$ passing
through the corner such that the normal is parallel to $a_2 - n_2$. Hence
the corner is the solution.

To convert this into an algebraic solution, observe that the above procedure
just projects each coordinate separately to the nearest point in $[-1,1]$.
Hence the solution is $n= (\operatorname{sat} a_1, \operatorname{sat} a_2)$,
where $\operatorname{sat} t = \max(-1,\min(1,t))$.
To deal with $p=1$, note that this case is just a rotated and scaled version of $p=\infty$. The geometry is essentially the same except that the regions are
rotated and scaled.
Let $\phi= \begin{bmatrix} 1 & 1 \\ 1 & -1  \end{bmatrix}$ and let $\phi_1(x) = x_1+x_2, \phi_2(x) = x_1-x_2$ (the two rows). Note that $\phi^2 = 2I$, so 
$\|\phi(x)\|_2 = \sqrt{2} \|x\|_2$. 
Hence minimising $\|x-a\|_2$ over $x \in \overline{B}_1(0,1)$ is the same
as minimising $\|\phi(x)-\phi(a)\|_2$ over $x \in \overline{B}_1(0,1)$.
Since $\phi(\overline{B}_1(0,1)) = \overline{B}_\infty(0,1)$, we see that
this is the same as minimising $\|y-\phi(a)\|_2$ over $y \in \overline{B}_1(0,1)$.
When we find a minimiser (using the $\operatorname{sat}$ operator as above) to find a solution $y^*$, we then must compute $x^* = \phi^{-1}(y^*)$ (which is $=\phi(y)$). This is
much easier to see geometrically than algebraically. 
