# American Institute of Mathematical Sciences

• Previous Article
Asymptotics for ruin probabilities of a non-standard renewal risk model with dependence structures and exponential Lévy process investment returns
• JIMO Home
• This Issue
• Next Article
$(Q,r)$ Model with $CVaR_α$ of costs minimization
January  2017, 13(1): 147-153. doi: 10.3934/jimo.2016009

## An efficient cutting plane algorithm for the smallest enclosing circle problem

 1 VC/VR Lab and Department of Mathematics, Sichuan Normal University, Chengdu, Sichuan 610066, China 2 Department of Mathematics, Sichuan Normal University, Chengdu, Sichuan 610066, China 3 Neijiang Vocational Technical College, Neijiang, Sichuan 641100, China

* Corresponding author

Received  April 2015 Revised  December 2015 Published  March 2016

Fund Project: The first author is supported by National Natural Science Foundation of China No.11126336 and No.11201324, New Teachers’ Fund for Doctor Stations, Ministry of Education No.20115134120001, Fok Ying Tuny Education Foundation No.141114, Youth fund of Sichuan province No.2013JQ0027.

In this paper, we consider the problem of computing the smallest enclosing circle. An efficient cutting plane algorithm is derived. It is based on finding the valid cut and reducing the problem into solving a series of linear programs. The numerical performance of this algorithm outperforms other existing algorithms in our computational experiments.

Citation: Yi Jiang, Chuan Luo, Shenggui Ling. An efficient cutting plane algorithm for the smallest enclosing circle problem. Journal of Industrial & Management Optimization, 2017, 13 (1) : 147-153. doi: 10.3934/jimo.2016009
##### References:

show all references

##### References:
The smallest enclosing circle for eight circles by the cutting plane method
Computational results for 12800 circles by the cutting plane method
 k R (x, y) Time 1 20.9058731071536 (0.545051135217305, 1.44782921739902) 3122 2 20.9105991582134 (0.299192662259897, 1.31150575665027) 3666 3 20.9125332765331 (0.298922131451905, 1.31135826866618) 4291 4 20.9125332765331 (0.298922131451905, 1.31135826866618) 4934
 k R (x, y) Time 1 20.9058731071536 (0.545051135217305, 1.44782921739902) 3122 2 20.9105991582134 (0.299192662259897, 1.31150575665027) 3666 3 20.9125332765331 (0.298922131451905, 1.31135826866618) 4291 4 20.9125332765331 (0.298922131451905, 1.31135826866618) 4934
The number of iterations on the cutting plane method
 m Average Maximum Minimum 50 3.14 5 2 200 3.08 4 3 800 3.22 4 3 3200 3.16 5 3 12800 3.46 7 3
 m Average Maximum Minimum 50 3.14 5 2 200 3.08 4 3 800 3.22 4 3 3200 3.16 5 3 12800 3.46 7 3
Objective function value
 Problem Obj Value m SOCP QP Algorithm 1 50 11.2096459 11.2096469 11.2096459 200 14.3832518 14.3832526 14.3832516 800 16.9222886 16.9222890 16.9222882 3200 19.1035735 19.1035733 19.1035728 12800 20.9684117 Out of Memory 20.9684103
 Problem Obj Value m SOCP QP Algorithm 1 50 11.2096459 11.2096469 11.2096459 200 14.3832518 14.3832526 14.3832516 800 16.9222886 16.9222890 16.9222882 3200 19.1035735 19.1035733 19.1035728 12800 20.9684117 Out of Memory 20.9684103
Average CPU time of three methods
 Problem Time m SOCP QP Algorithm 1 50 82.2 88.4 79.8 200 115.0 180.2 103.4 800 257.4 1859.4 254.6 3200 1041.6 34883.9 973.1 12800 8555.7 Out of Memory 5024.6
 Problem Time m SOCP QP Algorithm 1 50 82.2 88.4 79.8 200 115.0 180.2 103.4 800 257.4 1859.4 254.6 3200 1041.6 34883.9 973.1 12800 8555.7 Out of Memory 5024.6
 [1] Yi Zhang, Yong Jiang, Liwei Zhang, Jiangzhong Zhang. A perturbation approach for an inverse linear second-order cone programming. Journal of Industrial & Management Optimization, 2013, 9 (1) : 171-189. doi: 10.3934/jimo.2013.9.171 [2] Shiyun Wang, Yong-Jin Liu, Yong Jiang. A majorized penalty approach to inverse linear second order cone programming problems. Journal of Industrial & Management Optimization, 2014, 10 (3) : 965-976. doi: 10.3934/jimo.2014.10.965 [3] Xiaoni Chi, Zhongping Wan, Zijun Hao. Second order sufficient conditions for a class of bilevel programs with lower level second-order cone programming problem. Journal of Industrial & Management Optimization, 2015, 11 (4) : 1111-1125. doi: 10.3934/jimo.2015.11.1111 [4] Ye Tian, Shu-Cherng Fang, Zhibin Deng, Wenxun Xing. Computable representation of the cone of nonnegative quadratic forms over a general second-order cone and its application to completely positive programming. Journal of Industrial & Management Optimization, 2013, 9 (3) : 703-721. doi: 10.3934/jimo.2013.9.703 [5] Xinmin Yang. On second order symmetric duality in nondifferentiable multiobjective programming. Journal of Industrial & Management Optimization, 2009, 5 (4) : 697-703. doi: 10.3934/jimo.2009.5.697 [6] Liping Tang, Xinmin Yang, Ying Gao. Higher-order symmetric duality for multiobjective programming with cone constraints. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-12. doi: 10.3934/jimo.2019033 [7] Charles Fefferman. Interpolation by linear programming I. Discrete & Continuous Dynamical Systems - A, 2011, 30 (2) : 477-492. doi: 10.3934/dcds.2011.30.477 [8] Ziye Shi, Qingwei Jin. Second order optimality conditions and reformulations for nonconvex quadratically constrained quadratic programming problems. Journal of Industrial & Management Optimization, 2014, 10 (3) : 871-882. doi: 10.3934/jimo.2014.10.871 [9] Jean Creignou, Hervé Diet. Linear programming bounds for unitary codes. Advances in Mathematics of Communications, 2010, 4 (3) : 323-344. doi: 10.3934/amc.2010.4.323 [10] Yi Xu, Wenyu Sun. A filter successive linear programming method for nonlinear semidefinite programming problems. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 193-206. doi: 10.3934/naco.2012.2.193 [11] Yanqun Liu, Ming-Fang Ding. A ladder method for linear semi-infinite programming. Journal of Industrial & Management Optimization, 2014, 10 (2) : 397-412. doi: 10.3934/jimo.2014.10.397 [12] Yanqun Liu. Duality in linear programming: From trichotomy to quadrichotomy. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1003-1011. doi: 10.3934/jimo.2011.7.1003 [13] Ruotian Gao, Wenxun Xing. Robust sensitivity analysis for linear programming with ellipsoidal perturbation. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-16. doi: 10.3934/jimo.2019041 [14] Ali Tebbi, Terence Chan, Chi Wan Sung. Linear programming bounds for distributed storage codes. Advances in Mathematics of Communications, 2019, 0 (0) : 0-0. doi: 10.3934/amc.2020024 [15] Yanqin Bai, Pengfei Ma, Jing Zhang. A polynomial-time interior-point method for circular cone programming based on kernel functions. Journal of Industrial & Management Optimization, 2016, 12 (2) : 739-756. doi: 10.3934/jimo.2016.12.739 [16] Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399 [17] Yue Zheng, Zhongping Wan, Shihui Jia, Guangmin Wang. A new method for strong-weak linear bilevel programming problem. Journal of Industrial & Management Optimization, 2015, 11 (2) : 529-547. doi: 10.3934/jimo.2015.11.529 [18] Idan Goldenberg, David Burshtein. Error bounds for repeat-accumulate codes decoded via linear programming. Advances in Mathematics of Communications, 2011, 5 (4) : 555-570. doi: 10.3934/amc.2011.5.555 [19] Jiang-Xia Nan, Deng-Feng Li. Linear programming technique for solving interval-valued constraint matrix games. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1059-1070. doi: 10.3934/jimo.2014.10.1059 [20] Yanqun Liu. An exterior point linear programming method based on inclusive normal cones. Journal of Industrial & Management Optimization, 2010, 6 (4) : 825-846. doi: 10.3934/jimo.2010.6.825

2018 Impact Factor: 1.025