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.

Improve this question
$\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$
    – alvarezpaiva
    Commented Mar 29, 2012 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$
    – Miek Messerschmidt
    Commented Mar 29, 2012 at 13:30

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Ah! Makes sense. Turned out not to be that hard after all. Thank you, Anton. $\endgroup$
    – Miek Messerschmidt
    Commented Mar 29, 2012 at 17:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .