1
$\begingroup$

Suppose $S = \{x \in \mathbb{R}^n : \Vert x \Vert \leq 1\}$. Find the projection of a point to $S$, so find the shortest distance subject to the unit disk. That is we need to solve the following problem

min $\frac{1}{2} \Vert x - x_0 \Vert^2$

s.t $\Vert x \Vert^2 - 1 = 0$

So doing the work I got

$\nabla \frac{1}{2} \Vert x - x_0 \Vert^2 = \lambda\nabla (\Vert x \Vert^2 - 1) \implies x - x_0=\lambda (2x)$. And I need to solve

$\left\{\begin{matrix} x - x_0=\lambda (2x) \\ \Vert x \Vert^2 - 1 = 0 \end{matrix}\right.$

Now apparently the answer is

$P_s(x_0)= \left\{\begin{matrix} \frac{x_0}{\Vert x_0 \Vert} & \Vert x_0\Vert > 1\\ x_0 & \Vert x_0 \Vert \leq 1 \end{matrix}\right.$

I am having problems solving the set of equations (I honestly lost track of which is the variable and parameter)

  • 0
    @ShuhaoCao, I think you are right. Because the second case doesn't seem relevant to the problem. But I think I am curious to see it anyways. I modified the original constraint from everything inside the disk to the boundary2012-11-14

1 Answers 1

1

The problem (imho) is you solved for the constraint $g(x) = \| x^2 \| - 1 = 0$, which gives the unit circle, as opposed to $\| x^2 \| - 1 \leqslant 0$, which is the unit disk.

The two cases you're seeing are the following: if $x_0$ lies in the disk, the distance from it to itself is 0, which on the nose minimizes a distance function.

If $x_0$ lies outside the disk, you can look at the partials of $\| x - x_0 \|$ to deduce it has no critical points in the interior of the disk, so the minimum is achieved on the boundary, reducing to your computation.

To see that the answer you get is $\frac{x_0}{\| x_0 \| }$, it suffices to minimize the square of the distance, $f(x) = \sum_{i=1}^n (x^i - x_0^i)^2$. From here, we use Lagrange multipliers: which tell us $df_x = 2(x - x_0) \varpropto 2x = dg_x $That is, we have $x \varpropto x_0$, which gives us 2 points on the unit circle: $\pm \frac{x_0}{\|x_0\|}$; with a plus sign is a minimum and a minus a sign a maximum (of $f$)

  • 0
    Ah okay I do it thank you2012-11-14