How to find a point to minimize the maximal difference of squared distances to a set of points?

Question

Let me define my question formally. Suppose we have a set of points $C = \{x_i|x_i \in \mathbb R^d, i=1,\dots, n\}$, $n>d$. The goal is to find a "center" point $x\in \mathbb R^d$, such that $$ x = \arg\min_{u\in \mathbb R^d} (\max_{x_i\in C}\|u - x_i\|^2 - \min_{x_i\in C}\|u - x_i\|^2) $$ My first thought was that $x$ must be at the center of $C$. But the mass center is the minimizer of the sum of squared distances and does not satisfy our requirement. Also, I noticed that the function to minimize is actually convex. (The objective is convex when $n=2$ and for $C>2$ it can be viewed as a pointwise maximization for ($x_i,x_j$) pairs).

So here is my question: Is there any closed-form solution for this seemingly concise problem? If not, is there any way to give a lower bound for this objective given the set of points $C$? Thanks!

Answer 1

This is known as the bounding sphere problem (a special case of the 1-center problem), and it does not appear to a have a closed-form solution.

Answer 2

I'm not sure this is a well-formed goal, if the intent is to find some analog to a center. If you take $\lim_{u \to \infty^d}$, we trivially minimize the objective, as $$\lim_{u \to \infty^d} \left( \max_{x_i\in C}\|u - x_i\|^2 - \min_{x_i\in C}\|u - x_i\|^2 \right) = 0$$ (Also, as a result, save for under specific conditions / trivial cases on the set of points $C$ such as a single point or all points on the surface of a $d$-dim sphere, we only have an infinum, no achievable min).

Adding some form of regularization or constraints could fix that property, but would also continue to complicate your question and possibly skew the final answer; if you were just looking to encode a specific property it may be easier to consider different problem formulations to capture the dynamics you want. What's the larger context of the problem you're trying to solve?