Proof regarding center of an optimal Euclidean ball containing distinct points

Question

Suppose we are given $k$ distinct points $a_i \in \mathbb{R}^n$ for $i = 1, 2, \dots, k$, and our objective is to determine the Euclidean ball with the smallest radius that contains all these points ($k > 1$). I am seeking a proof or demonstration to establish the following claim:

For any optimal Euclidean ball, its center can be represented as a convex combination of the points lying on its boundary. I want to solve this by formulating it as a convex second-order cone program (SOCP) or a quadratically-constrained quadratic program (QCQP).

Could someone provide a proof or explanation supporting this claim? Additionally, how can this problem be effectively formulated as a convex optimization problem, utilizing either SOCP or QCQP techniques, to demonstrate the convex combination property of the ball's center?

Answer 1

Define the following problem:

$$ \min_{r>0,c\in\mathbb{R}^n} r^2\quad \mathrm{s.t}\quad (a_i-c)^T(a_i-c)\le r^2,\ i=1,\ldots,k. $$

The Lagrangian is given by

$$ L(r,c,\lambda)=r^2+\sum_{i=1}^l\lambda_i((a_i-c)^T(a_i-c)-r^2). $$

We have that

$$ \dfrac{\partial}{\partial r}L(r,c,\lambda)=2r-2r\sum_{i=1}^k\lambda_i $$ and $$ \dfrac{\partial}{\partial c}L(r,c,\lambda)=\sum_{i=1}^k\lambda_i(2c^T-2a_i^T). $$

Looking for stationary points yields (using $r>0$)

$$\sum_{i=1}^k\lambda_i=1$$

which implies that

$$c=\sum_{i=1}^k\lambda_ia_i,$$

which shows that the center $c$ is represented as a convex combination of all the points $a_i$, $i=1,\ldots,k$.

From the transversality conditions, we have that $$\lambda_i(((a_i-c)^T(a_i-c)-r^2)=0,$$ which means that $\lambda_i=0$ for all the points $a_i$ in the interior of the ball and $\lambda_i\ne0$ for all the points $a_i$ on its boundary.

This proves the statement that the center $c$ can be represented as a convex combination of all the points $a_i$, $i=1,\ldots,k$ on the boundary of the ball, which is the desired statement.

Answer 2

Rephrasing, given $n \geq 2$ distinct points, ${\bf p}_1, \dots, {\bf p}_n \in {\Bbb R}^d$, find the smallest Euclidean ball containing all $n$ points.

---

The point ${\bf x} \in {\Bbb R}^d$ is in the Euclidean ball centered at ${\bf c} \in {\Bbb R}^d$ and of radius $r > 0$ if and only if $\left( {\bf x} - {\bf c} \right)^\top \left( {\bf x} - {\bf c} \right) \leq r^2$. Dividing both sides of this inequality by $r > 0$, we obtain

$$ r - \left( {\bf x} - {\bf c} \right)^\top r^{-1} \left( {\bf x} - {\bf c} \right) \geq 0 $$

which looks very much like a Schur complement. Rewriting, we obtain

$$ \begin{bmatrix} r & \left( {\bf x} - {\bf c} \right)^\top \\ \left( {\bf x} - {\bf c} \right) & r {\bf I}_d \end{bmatrix} \succeq {\bf O}_{1+d} $$

and, thus, we have the following semidefinite program (SDP)

$$\boxed{\begin{array}{ll} \underset{{\bf c} \in \Bbb R^d, r \in {\Bbb R}}{\text{minimize}} & \qquad\qquad r \\ \text{subject to} & \begin{bmatrix} r & \left( {\bf x} - {\bf c} \right)^\top \\ \left( {\bf x} - {\bf c} \right) & r {\bf I}_d \end{bmatrix} \succeq {\bf O}_{1+d}, \quad \forall {\bf x} \in \left\{ {\bf p}_1, \dots, {\bf p}_n \right\} \end{array}}$$

---

Related

• Smallest ellipse by area to enclose 2D points