MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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
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|cite|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

Your Answer


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.