How to find the smallest sphere that encloses a set of k points p_i \in R^n.The intuitive formulation is to minimize the radius r of the sphere centered in p_0 \in R^n, i.e.
\begin{align} & \min r \\ & s.t. \\ & & || p_i - p_0||_2 \leq r, & i=1,\ldots,k \end{align}
The inspiration came from a recent book¹ where the problem, probably taken from the GAMS repository², is presented as a difficult test for nonlinear local optimizers.
At the same time (what a coincidence!), O'Neil and Puget published interesting post about the Chebyshev centers of polygons...which turns out to be equivalent to what I was looking at! As Puget pointed out, the problem is known to be simple: Megiddo³ showed back in 1982 that it can be solved in linear time by a specialized algorithm.
Anyway, we will use it as an example of conic programming modeling example. First we introduce auxiliary variables such that w_i = p_i - p_0, yielding
\begin{align} & \min r \\ & s.t.\\ & & || w_i ||_2 \leq r, & i=1,\ldots,k\\ & & w_i = p_i - p_0, & i=1,\ldots,k \end{align}
Constraints (6) define quadratic (Lorentz) cones Q^{(n+1)}, i.e.
\begin{equation} || w_i ||_2 \leq r \Rightarrow (r, w_i) \in Q^{(k+1)}.\end{equation}
For the second order cones to be disjointed, we introduce auxiliary variables r_i, i=1,\ldots,n that must be equal to r. The final formulation of our problem is
\begin{align} & \min r\\ & s.t.\\ & & r_i = r, & i=1,\ldots,k\\ & & w_i = p_i - p_0, & i=1,\ldots,k\\ & & (r_i,w_i) \in Q^{(n+1)}, & i=1,\ldots,k \end{align}
which is a fairly simple conic quadratic optimization problem!
In the next post we will show how to easily implement this problem using the Mosek Fusion API.
¹ Neculai, Andrei, "Nonlinear Optimization Application Using the GAMS Technology", Springer 2013
² http://www.gams.com/testlib/libhtml/circlen.htm
³ Megiddo, Nimrod. "Linear-time algorithms for linear programming in R3 and related problems." Foundations of Computer Science, 1982. SFCS'08. 23rd Annual Symposium on. IEEE, 1982.
