An Efficient Inexact Newton-CG Algorithm for the Smallest Enclosing Ball Problem of Large Dimensions
- PDF / 594,435 Bytes
- 25 Pages / 439.37 x 666.142 pts Page_size
- 44 Downloads / 220 Views
An Efficient Inexact Newton-CG Algorithm for the Smallest Enclosing Ball Problem of Large Dimensions Ya-Feng Liu1 · Rui Diao1 · Feng Ye2 · Hong-Wei Liu2
Received: 22 June 2015 / Revised: 21 September 2015 / Accepted: 21 September 2015 / Published online: 22 October 2015 © Operations Research Society of China, Periodicals Agency of Shanghai University, Science Press, and Springer-Verlag Berlin Heidelberg 2015
Abstract 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.
This work was partially supported by the National Natural Science Foundation of China (Nos. 11331012 and 11301516).
B
Ya-Feng Liu [email protected] Rui Diao [email protected] Feng Ye [email protected] Hong-Wei Liu [email protected]
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
123
168
Y.-F. Liu et al.
Keywords Smallest enclosing ball · Smoothing approximation · Inexact gradient · Inexact Newton-CG algorithm · Global convergence Mathematics Subject Classification 90C47 · 90C06 · 90C90 · 90C25
1 Introduction The smallest enclosing ball (SEB) problem is considered in this paper. The SEB problem is to find a ball with the smallest radius that can enclose the union of all given balls Bi (i = 1, 2, · · · , m) with center ci and radius ri 0 in Rn , i.e., Bi = x ∈ Rn | x − ci ri . Define f (x) = max { f i (x)} , 1i m
where f i (x) = x − ci + ri , i = 1, 2, · · · , m. Then, the SEB problem can be formulated as the following non-smooth convex optimization problem [1]: min f (x).
x∈Rn
(1.1)
It is shown in [1] that problem (1.1) has a unique solution. The SEB problem arises in a large number of important applications, often requiring that it should be solved in large dimensions, such as location analysis [2], gap tolerant classifiers in machine learning [3–5], tuning support vector machine parameters [6], suppor
Data Loading...
