Theorem 8.7.4 — the smallest enclosing ball from a convex quadratic program

Let $p_1,\dots,p_n$ be points in $\mathbb{R}^d$ with $n\ge 1$, let $P=\{p_1,\dots,p_n\}$, and let $Q$ be the $d\times n$ matrix whose $j$th column is formed by the $d$ coordinates of $p_j$. Consider the optimization problem

in the variables $x_1,\dots,x_n$. Then the objective function $f(x)=x^TQ^TQx-\sum_{j}x_jp_j^Tp_j$ is convex on $\mathbb{R}^n$, and:

1. Problem (8.15) has an optimal solution $x^*$.
2. There exists a point $p^*$ such that $p^*=Qx^*$ for every optimal solution $x^*$. Moreover, for every optimal solution $x^*$, $-f(x^*)\ge 0$, and the ball with center $p^*$ and squared radius $-f(x^*)$ (radius $\sqrt{-f(x^*)}$) is the unique ball of smallest radius containing $P$.

In particular the smallest enclosing ball of a finite point set exists and is unique, and it is computed by a convex quadratic program.

Formalization Note Points live in EuclideanSpace ℝ (Fin d) and $x\in\mathbb{R}^n$ is Fin n → ℝ (0-based indices). The hypothesis $n\ge 1$ is the book's "points $p_1,\dots,p_n$"; for $n=0$ the feasible set is empty and (i) fails. "Unique ball of smallest radius" is the definition IsUniqueSmallestEnclosingBall: the ball contains $P$, no ball containing $P$ is smaller, and any ball containing $P$ of radius at most the optimum has center $p^*$. The equation $p^*=Qx^*$ is stated coordinatewise. Convexity is stated on all of $\mathbb{R}^n$.