Distance from a convex set to a point

Question

Let $Y \in \mathbb{R}^n$ be a nonempty convex set such that $0 \notin Y$ and fix $y_1,\dots,y_n$ in $Y$, where $n \ge 2$. I know that there exist $i,j$ such that $\Vert y_i \Vert > \Vert y_j\Vert$. Define $ C = C(y_1,\dots,y_n)$, i.e. the set of convex combinations. Moreover, I know that there exists a unique $x\in C$ such that \begin{align*} \Vert x \Vert = d(0,C),\end{align*} where the latter is the distance from $0$ to $C$. Now I want to show that \begin{align*} \Vert x \Vert < \Vert (1-\lambda) x + \lambda y_l\Vert\end{align*} for all $\lambda \in (0,1)$, where $y_l$ such that $\Vert y_l \Vert = \max\{\Vert y_1 \Vert, \dots, \Vert y_n \Vert \}$.

Notice that the proof should be constructive, i.e. no law of excluded middle should be used.

I did already show that $\langle x , c \rangle \ge 0$ for all $ c \in C$.

So far I was only able to show \begin{align*} (1-\lambda)\lambda\Vert x \Vert < \Vert (1-\lambda) x + \lambda y_l\Vert. \end{align*}

Answer 1

Consider the function $$\begin{aligned} f(\lambda) = \Vert (1-\lambda) x + \lambda y_l\Vert^2 &= (1-\lambda)^2\Vert x\Vert^2 + 2(1-\lambda)\lambda \langle x, y_l \rangle + \lambda^2 \Vert y_l \Vert^2\\ &=\lambda^2 \Vert x - y_l \Vert^2 + 2 \lambda \left(\langle x, y_l \rangle - \Vert x \Vert^2\right) + \Vert x \Vert^2 \end{aligned}$$

defined on $I=[0,1]$.

$f$ is not constant on this interval as by hypothesis, you have $\Vert x \Vert \le \Vert y_j \Vert < \Vert y_i \Vert \le \Vert y_l \Vert$ using the original notations of your question and therefore $\Vert x - y_l \Vert > 0$. By definition of $x$ you also have $f(\lambda) \ge \Vert x \Vert^2$ for all $x \in I$.

$f$ is a non constant polynomial of degree $2$. It can take each real value at most twice at points that are symmetrical relatively to the minimum point.

The minimum is attained for $f^\prime(\lambda)= 2\left(\lambda\Vert x - y_l \Vert^2+\langle x, y_l \rangle - \Vert x \Vert^2\right) = 0$, i.e.

$$\lambda_0 = \frac{\Vert x \Vert^2-\langle x, y_l \rangle }{\Vert x - y_l \Vert^2} = \frac{\langle x , x-y_l \rangle}{\Vert x - y_l \Vert^2}$$

As $f(0) = \Vert x \Vert^2$ the only other value for which $f$ is equal to $\Vert x \Vert^2$ is $2 \lambda_0$.

But according to property of the projection on a convex set, you have $\lambda_0 \le 0$. Hence $f$ can only take a second time the value $\Vert x \Vert^2$ at a point less than $0$. That allows to conclude that $\Vert x \Vert < \Vert (1-\lambda) x + \lambda y_l\Vert$ for $\lambda \in (0,1]$ as desired.

Answer 2

If I am understanding correctly, this seems quite trivial if the aformentioned distance function, $d$, computes the distance between the origin and the cet $C$ by finding a point $x$ in $C$ with minimal $L_2$-norm, i.e., $$ d(\overset{\to}{0}, C) = \min_{x \in C} \left| \left| x\right| \right|_2.$$

If that's the case, then it's easy to see that for any $i \in [n]$, and $\lambda \in [0,1]$, the following holds: $$ \left| \left| x\right| \right|_2 < \left| \left| \lambda x + (1-\lambda) y_i\right| \right|_2.$$

The reason of why such inequality holds is by the fact that $x$ minimizes the distance to the origin (having the least norm, and such point being unique as assumed). Also note that each point $w$ displayed as $\lambda x + (1-\lambda) y_i$, by convexity of $C$, it holds that $w \in C$, thus $\left| \left| w\right| \right|_2 > \left| \left| x\right| \right|_2$.