Constrained optimization of l2 norm

Question

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$ :

Answer 1

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.