An efficient algorithm for the smallest enclosing ball problem in high dimensions

被引：8

作者：

Pan, SH ^{[1
]}

Li, XS

机构：

[1] S China Univ Technol, Sch Math Sci, Guangzhou 510641, Peoples R China

[2] Dalian Univ Technol, State Key Lab Struct Anal Ind Equipment, Dalian 116023, Peoples R China

来源：

APPLIED MATHEMATICS AND COMPUTATION | 2006年 / 172卷 / 01期

关键词：

the smallest enclosing ball; nonsmooth; smooth approximation; CHKS function;

D O I：

10.1016/j.amc.2005.01.127

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Consider the problem of computing the smallest enclosing ball of a set of in balls in R-n. This problem arises in many applications such as location analysis, military operations, and pattern recognition, etc. In this paper, we reformulate this problem as an unconstrained convex optimization problem involving the maximum function max{0,t}, and then develop a simple algorithm particularly suitable for problems in high dimensions. This algorithm could efficiently handle problems of dimension m up to 10,000 under a moderately large m, as well as problems of dimension 171 up to 10,000 under a moderately large n. Numerical results are given to show the efficiency of algorithm. (c) 2005 Elsevier Inc. All rights reserved.

引用

页码：49 / 61

页数：13

共 18 条

[1] Support vector clustering
Ben-Hur, A
Horn, D
Siegelmann, HT
Vapnik, V
[J]. JOURNAL OF MACHINE LEARNING RESEARCH, 2002, 2 (02) : 125 - 137
[2] BULATOV Y, 2002, DIMACS WORKSH COMP G
[3] Chen C. H., 1996, COMPUTATIONAL OPTIMI, V5, P97
[4] Dyer M., 1992, Proceedings of the Eighth Annual Symposium on Computational Geometry, P9, DOI 10.1145/142675.142681
[5] MINIMUM COVERING SPHERE PROBLEM
ELZINGA, DJ
HEARN, DW
[J]. MANAGEMENT SCIENCE SERIES A-THEORY, 1972, 19 (01): : 96 - 104
[6] Fast smallest-enclosing-ball computation in high dimensions
Fischer, K
Gärtner, B
Kutz, M
[J]. ALGORITHMS - ESA 2003, PROCEEDINGS, 2003, 2832 : 630 - 641
[7] Gärtner B, 1999, LECT NOTES COMPUT SC, V1643, P325
[8] Gartner B, 2000, P 16 ANN S COMP GEOM, P110
[9] EFFICIENT ALGORITHMS FOR THE (WEIGHTED) MINIMUM CIRCLE PROBLEM
HEARN, DW
VIJAY, J
[J]. OPERATIONS RESEARCH, 1982, 30 (04) : 777 - 795
[10] Some noninterior continuation methods for linear complementarity problems
Kanzow, C
[J]. SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, 1996, 17 (04) : 851 - 868

← 1 2 →