A new separable property of the joint numerical range of quadratic functions and its applications to the Smallest Enclosing Ball Problem

Abstract

We explore separable property of the joint numerical range $G({\mathbb{R}}^n)$ of a special class of quadratic functions and apply it to solving the smallest enclosing ball (SEB) problem which asks to find a ball $B(a,r)$ in ${\mathbb{R}}^n$ with smallest radius $r$ such that $B(a,r)$ contains the intersection ${\cap }_{i=1}^{m}B(a_i,r_i)$ of $m$ given balls $B(a_i,r_i).$ We show that $G({\mathbb{R}}^n)$ is convex if and only if $\mathrm{rank}\{a_1-a,a_2-a,\dots ,a_m-a\}\le n-1.$ Otherwise, $\mathrm{rank}\{a_1-a,a_2-a,\dots ,a_m-a\}=n$ and $G({\mathbb{R}}^n)$ is not convex. In this case we propose a new set $G({\mathbb{R}}^n{)}^{\bullet }$ which allows to show that if $m=n$ then $G({\mathbb{R}}^n{)}^{\bullet }$ is convex even $G({\mathbb{R}}^n)$ is not. Importantly, the separable property of $G({\mathbb{R}}^n{)}^{\bullet }$ then implies the separable property for $G({\mathbb{R}}^n).$ As a result, a new progress on solving the SEB problem is obtained.