2
$\begingroup$

If $X$ is a Real Banach space with strictly convex norm, it is known that for any non-empty compact, convex set $K$ and point $x_0\notin K$, there exists a unique point $z_0\in K$ minimizing the quantity $\|z-x_0\|$ in $z\in K$.

My question is whether it is known if the obvious generalization holds:

Given two (or n) points $x_0,x_1\notin K$ so that the set $\{x_0,x_1\}$ is separated from $K$ by an affine hyperplane, then there exists a unique point $z_0\in K$ minimizing the quantity $\|z-x_0\|+\|z-x_1\|$ in $z\in K$.

My feeling is that this should have been investigated somewhere in the literature, but in my inexperience navigating that landscape I had thus far been unable to find it.

$\endgroup$
2
  • 3
    $\begingroup$ In two-dimensions the curves $\|z -x_0\| + \|z -x_1\| = d$ with $d > 0$ are "ellipses" in the normed plane and they were studied by Busemann among others (see his book Geometry of geodesics). In the higher dimensional case (or the general Banach space case) I have not seen the sets $\|z -x_0\| + \|z -x_1\| \leq d$ studied. It is easy to see that these (sort of) "ellipsoids" are convex, so I guess your question reduces to something like: if the unit ball of a Banach space is strictly convex, is the same true for all "ellipsoids"? $\endgroup$ Mar 29 '12 at 12:18
  • $\begingroup$ After talking to some colleagues over lunch, the implied strict convexity of 'ellipsoids' was exactly the conclusion we drew too. Thank you for the partial reference, I'll take a look. It's certainly a different direction than my attempts at finding something with the search term "convex optimization". $\endgroup$ Mar 29 '12 at 13:30
2
$\begingroup$

The answer is YES.

The function $\mathrm{dist}_x$ is strictly convex at any point $y$ and any direction different $x-y$.

It follows that $f=\sum \mathop{\rm dist}_{x_i}$ is strictly convex at any point if $x_i$ do not lie on one line; in this case uniquness is obvious.

If there is a line, say $\ell$ containing all $x_i$, then $f$ is strictly convex in any half-space not intersecting $\ell$. Hence the result.

$\endgroup$
1
  • $\begingroup$ Ah! Makes sense. Turned out not to be that hard after all. Thank you, Anton. $\endgroup$ Mar 29 '12 at 17:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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