Minimum volume sphere bounding all points as a linear programming problem

Question

I want to find the smallest sphere which encapsulate a set of points $x_i \in \mathbb{R}^d$.

I can formulate is as

$$ \arg \min_{a \in \mathbb{R}^d, r} r \quad\quad \text{s.t.} \quad || x_i - a|| \leq r $$

Can it be formulated as a linear programming problem?
If not, is there a reasonable approximation?

Answer 1

You can solve the problem directly via second-order cone programming.

Other approaches are described here: https://en.wikipedia.org/wiki/Bounding_sphere