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 / 213 Views

DOWNLOAD

REPORT


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