An Efficient Inexact Newton-CG Algorithm for the Smallest Enclosing Ball Problem of Large Dimensions  

作　　者：Ya-Feng Liu Rui Diao Feng Ye Hong-Wei Liu 

机构地区：[1]State Key Laboratory of Scientific and Engineering Computing,Institute of Computational Mathematics and Scientific/Engineering Computing,Academy of Mathematics and Systems Science,Chinese Academy of Sciences,Beijing 100190,China [2]Department of Applied Mathematics,Xidian University,Xi’an 710071,China

出　　处：《Journal of the Operations Research Society of China》2016年第2期167-191,共25页中国运筹学会会刊（英文）

基　　金：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.

关 键 词：Smallest enclosing ball Smoothing approximation Inexact gradient Inexact Newton-CG algorithm Global convergence 

分 类 号：O24[理学—计算数学]