Find a vector minimizing the distance from set

Question

Find a vector $\Pi_Z(x)$ minimizing the distance between $x=(5,10)\in\mathbb{R}^2$ and set $Z=\{(x,y)\in\mathbb{R}^2:x\ge0, y\le\sqrt{x}\}$

Answer 1

Your set $Z$ is convex and has a $C^1$ boundary, so if $\Pi_Z(x) = (a,b)$ you have $$ (a-5,b-10) \cdot (t,t') = 0$$ where $(t,t')$ is any nonzero tangent vector of the boundary $\partial Z$ at the point $(a,b)$. As $Z$ is convex this condition is also sufficient.

One such tangent vector is $(2b,1)$ and $(a,b)$ being on $\partial Z$ gives $a = b^2$ so you get the equation

$$2b^3 - 9b - 10 = 0.$$

This polynomial has two negative roots and one positive root $r$, so your point is $(r^2,r)$.

Note that here I ignored the component of $\partial Z$ consisting of $\left\{(0,y) | y \in \mathbb{R}^{-} \right\}$ because I already found a solution (and because it was visually quite clear that the projection didn't lie on this component) but in the general case you have to examine every component of $\partial Z$.

Answer 2

Obviously, the point $P \in Z$ minimizing the distance to $(5,10)$ must lie on the 'upper' boundary of $Z$, i.e. the curve $y=\sqrt{x}$. Then, the desired distance is

$$ d_P = \sqrt{(x-5)^2+(\sqrt{x}-10)^2}. $$

We now have to minimize $d_P$, or better, $d_P^2$. The first derivative of $d_P^2$ is

$$ 2x - \frac{10}{\sqrt{x}} - 9.$$

This latter function has a zero at $x \approx 6.4663$, and it yields a minimum of $d_P^2$. That's the $x$ of your $P$. Therefore, the desired vector is $(5-6.4663, 10-\sqrt{6.4663})$. Hope this helps.

By the way, if this is a homework you should tag it as such.

Answer 3

$Z$ is convex, closed and non-empty, hence for any point $q \in \mathbb{R}^2$ there is a unique nearest point $\Pi_C(q) \in Z$.

Suppose $p=(p_1,p_2) \notin Z$ and $p_1>0$. Then $p_2 > \sqrt{p_1}$.

While it is visually obvious,we should analytically establish that $\Pi_C(p)$ lies on the curve $y = \sqrt{x}$, $x>0$.

Note that if $q \in Z^\circ$, then the point $\lambda p + (1-\lambda)q$ is closer to $p$ for some small $\lambda \in (0,1)$, hence $\Pi_C(p) \notin Z^\circ$. Hence $\Pi_C(p)$ must lie on $\partial Z$.

We see that $\partial Z = \{(0,-\alpha) | \alpha \ge 0 \} \cup \{ (x,\sqrt{x}) \}_{x > 0}$.

Hence we just need to show that $\Pi_C(p)$ cannot have the form $(0,-\alpha)$, with $\alpha \ge 0$.

First consider $\alpha = 0$, let $\lambda = {p_1 \over p_2^2} \in (0,1)$, note that $\lambda p \in Z$ and $\|p -\lambda p \| < \|p\|$, hence $\lambda p$ is closer to $p$ than $0$. Hence $\Pi_C(p) \neq 0$. Now suppose $\alpha >0$, then we have $\|p-0\| < \|p-(0,-\alpha)\|$, hence $0$ is closer to $p$ than $(0,-\alpha)$. Hence $\Pi_C(p) \neq (0,-\alpha)$.

Consequently, $\Pi_C(p)$ has the form $(x , \sqrt{x})$ with $ x>0$. The distance (squared) satisfies $\delta(x)=\|p-(x,\sqrt{x})\|^2 = (p_1-x)^2 + (p_2-\sqrt{x})^2$, hence the minimizing $x$ satisfies $\delta'(x) = 0$. Since $\delta'(x) = 2x -2p_1 +1 - { p_2 \over \sqrt{x}}$ is strictly increasing, $\lim_{x \downarrow 0} \delta'(x) = -\infty$ and $\lim_{x \to \infty} \delta'(x) = \infty$ we see that there is a unique $x$ satisfying $\delta'(x) = 0$. Applying Newton's method to $\delta'(x) = 0$ yields a numeric solution (Starting from $x=5$, two iterations gives $x \approx 6.466$).