In this paper,we consider the problem of computing the smallest enclosing ball(SEB)of a set of m balls in Rn,where the product mn is large.We first approximate the non-differentiable SEB problem by its log-exponentia...In this paper,we consider the problem of computing the smallest enclosing ball(SEB)of a set of m balls in Rn,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.展开更多
基金the National Natural Science Foundation of China(Nos.11331012 and 11301516).
文摘In this paper,we consider the problem of computing the smallest enclosing ball(SEB)of a set of m balls in Rn,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.
