Abstract:

In this paper, we consider the problem of computing the smallest enclosing ball (SEB) of a set of m balls in Rⁿ ,where the product mn is large. We first approximate the non-differentiable SEB problem by its log-exponential aggregation function and then propose a computationally efficient inexact Newton-CG algorithm for the smoothing approximation problem by exploiting its special (approximate) sparsity structure. The key difference between the proposed inexact Newton-CG algorithm and the classical Newton-CG algorithm is that the gradient and the Hessian-vector product are inexactly computed in the proposed algorithm, which makes it capable of solving the large-scale SEB problem. We give an adaptive criterion of inexactly computing the gradient/Hessian and establish global convergence of the proposed algorithm.We illustrate the efficiency of the proposed algorithm by using the classical Newton-CG algorithm as well as the algorithm from Zhou et al. (Comput Optim Appl 30:147–160, 2005) as benchmarks.

Key words: Smallest enclosing ball , Smoothing approximation , Inexact gradient , Inexact Newton-CG algorithm , Global convergence