Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)

share|improve this question
    
I thought in both cases the answer should be $x_0/\|x_0\|$, since the constraint is $\|x\|^2-1=0$. –  Shuhao Cao Nov 14 '12 at 0:28
    
@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 boundary –  sidht Nov 14 '12 at 0:34

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer
    
that's right i thought if I were just to do the boundary, it would easier and maybe the solution didn't do that? –  sidht Nov 14 '12 at 0:38
    
Ah okay I do it thank you –  sidht Nov 14 '12 at 0:49
    
you're welcome! –  uncookedfalcon Nov 14 '12 at 0:53

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.