On the elimination of inessential points in the smallest enclosing ball problem. (4th March 2019)

• Record Type: Journal Article
• Authors: Pronzato, Luc
• Is Part Of: Optimization methods and software. Volume 34:Number 2(2019)
• Page Start: 225
• Page End: 247
• Publication Date: 2019-03-04
• Subjects: minimum enclosing ball -- smallest ball -- Chebyshev centre -- core sets -- optimal design of experiments; 90C25 -- 90C46 -- 62K05; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2017.1359266
• Languages: English
• ISSNs: 1055-6788

Abstract

Abstract : We consider the construction of the smallest ballB ∗ enclosing a setX n formed by n points inR d . We show that any probability measure onX n, with mean c and variance matrix V, provides a lower bound b on the distance to c of any point on the boundary ofB ∗, with b having a simple expression in terms of c and V . This inequality permits to remove inessential points fromX n, which do not participate to the definition ofB ∗, and can be used to accelerate algorithms for the construction ofB ∗ . We show that this inequality is, in some sense, the best possible. A series of numerical examples indicates that, when d is reasonably small (d ≤ 10, say) and n is large (up to10 5 ), the elimination of inessential points by a suitable two-point measure, followed by a direct (exact) solution by quadratic programming, outperforms iterative methods that compute an approximate solution by solving the dual problem.