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.
