Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
3  
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"? –  alvarezpaiva Mar 29 '12 at 12:18
    
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". –  Miek Messerschmidt Mar 29 '12 at 13:30
add comment

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
Ah! Makes sense. Turned out not to be that hard after all. Thank you, Anton. –  Miek Messerschmidt Mar 29 '12 at 17:57
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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