The intuitive formulation is to minimize the radius r of the sphere centered in $p_0 \in R^n$, i.e.How to find the smallest sphere that encloses a set of $k$ points $p_i \in R^n$.

\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.