2

Suppose $Z$ is a closed convex set and $x\not\in Z$. We need to show that there exists $z'\in Z$ such that $||z'-x||\leq||z-x||~~\forall z\in Z$.

I know that the distance function is continuous hence has a minimum on any compact subset of $Z$ but how do I guarantee that for the convex set?

QED
  • 12,644
  • the problem is particularly easy when $Z\subset\mathbb R$, so what is $Z$ ? That is, $Z$ is a subset of what space? – Mirko May 28 '17 at 06:35
  • Yeah i have considered this case. I this case any closed convex set is compact. But what about the general case – QED May 28 '17 at 06:45
  • 1
    You did not state the general case, as you did not specify the space of which $Z$ is a subset. A closed convex subset of $\mathbb R$ need not be compact, for example $(-\infty,2]$. How do you define convexity? If your space is the rationals (where convex could be taken to mean order-convex), then $Z=(-\infty,\sqrt2\ )=(-\infty,\sqrt2\ ]$ and $x=2$ is a counterexample. I assume you mean a vector space over $\mathbb R$, but more details, what kind of vector spaces are considered (apart form $\mathbb R^n$)? – Mirko May 28 '17 at 06:53
  • Apart from $\mathbb{R}^{n}$, this is the Hilbert Projection Theorem: https://en.wikipedia.org/wiki/Hilbert_projection_theorem – R. W. Prado Aug 17 '23 at 04:27

1 Answers1

0

In general, there is a known result, see Proposition A.8(b) in Bertsekas book, that says that, given a coercive and continuous function $f:\mathbb{R}^{n} \rightarrow \mathbb{R}$, i.e., satisfying $$\lim_{\| {\boldsymbol x\|}\rightarrow \infty } f(\boldsymbol x) =\infty, $$ for all closed set $Z \subset \mathbb{R}^{n}$, the optimization problem \begin{equation*} \begin{array}{c c} \text{minimize}_{\boldsymbol x \in \mathbb{R}^n} & f(\boldsymbol x) \\ \text{subject to } & \boldsymbol x\in Z, \end{array} \end{equation*} has at least a global minimizier $\boldsymbol x^{*} \in Z$. Since, for any $\boldsymbol x$, the function $g_{\boldsymbol x }: \mathbb{R}^{n}\rightarrow \mathbb{R}$ given by $g_{\boldsymbol x }(z)=\|z-x\|$, for all $\boldsymbol z \in \mathbb{R}^{n}$, is coercive, the optimization problem \begin{equation*} \begin{array}{c c} \text{minimize}_{\boldsymbol x \in \mathbb{R}^n} & g_{\boldsymbol x }(z) \\ \text{subject to } & \boldsymbol z\in Z, \end{array} \end{equation*} must have a solution, by this result, which is your desired result.

It's import to note that it's needed that $Z$ to be closed and convex, otherwise the problem does not necessarily have a solution. For example, for the open and bounded ball $B(\boldsymbol 0 , 1 ) = \{\boldsymbol x \in \mathbb{R}^{n}: \|\boldsymbol x \| < 1\}$, given an $\boldsymbol z$ with $\|\boldsymbol z\|>1$ your minimum distance is never achieved.

R. W. Prado
  • 787