Figure 1.
The smallest enclosing circle for eight circles by the cutting plane method
-
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 |
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.
Mathematics Subject Classification:
Primary: 90C30.
Citation:
Yi Jiang, Chuan Luo, Shenggui Ling. An efficient cutting plane algorithm for the smallest enclosing circle problem. Journal of Industrial and Management Optimization,
2017, 13
(1)
: 147-153.
doi: 10.3934/jimo.2016009
![]()
References:
| [1] |
M. Berg,
Computational Geometry: Algorithms and Applicaions, Springer, New York, 1997.
doi: 10.1007/978-3-662-03427-9. |
| [2] |
P. Chrystal, On the problem to construct the minimum circle enclosing n given points in a plan, in Proceedings of the Edinburgh Mathematical Society, Tird Meeting, 1885, 30. |
| [3] |
J. Eliosoff and R. Unger, Minimal spanning circle of a set of points, Computer Science: Computational Geometry Project, School of Computer Science, McGill University, 1998,308– 507. |
| [4] |
J. Elzinga and D. Hearn,
The minimum covering sphere problem, Management Sci., 19 (1972), 96-104.
doi: 10.1287/mnsc.19.1.96. |
| [5] |
B. Gärtner, Fast and robust smallest enclosing balls, in Algorithms-ESA' 99: 7th Annual European Symposium, Proceedings (eds. J. Nestril), Lecture Notes in Computer Science, 1643, Springer-Verlag, 1999,325–338. |
| [6] |
D. W. Hearn and J. Vijan,
Efficient algorithms for the minimum circle problem, Oper. Res., 30 (1982), 777-795.
doi: 10.1287/opre.30.4.777. |
| [7] |
M. Lobo, L. Vandenberghe, S. Boyd and H. Lebret,
Applications of second-order cone programming, Linear Albebra and its Applications, 284 (1998), 193-228.
doi: 10.1016/S0024-3795(98)10032-0. |
| [8] |
J. Sturm, Using SeDuMi 1. 02, a MATLAB toolbox for optimization over symmetric cones Optim. Methods Softw., 11/12 (1999), 625-653.
doi: 10.1080/10556789908805766. |
| [9] |
Y. Tian, S. C. Fang, Z. B. Deng and W. X. 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 and Management Optimization, 9 (2013), 703-721.
doi: 10.3934/jimo.2013.9.703. |
| [10] |
S. Y. Wang, Y. J. Liu and Y. Jiang,
A majorized penalty approach to inverse linear second order cone programming problems, Journal of Industrial and Management Optimization, 10 (2014), 965-976.
doi: 10.3934/jimo.2014.10.965. |
| [11] |
E. Welzl, Smalleat enclosing disks (balls and ellipsoids), in New Results and New Trends in Computer Science, Springer-Verlag, 1991,359–370.
doi: 10.1007/BFb0038202. |
| [12] |
S. Xu, R. Freund and J. Sun,
Solution methodologies for the smallest enclosing circle problem, Comput. Optim. Appl., 25 (2003), 283-292.
doi: 10.1023/A:1022977709811. |
| [13] |
Y. Zhang, Y. Jiang, L. Zhang and J. Zhang,
A perturbation approach for an inverse linear second-order cone programming, Journal of Industrial and Management Optimization, 9 (2013), 171-189.
doi: 10.3934/jimo.2013.9.171. |
show all references
References:
| [1] |
M. Berg,
Computational Geometry: Algorithms and Applicaions, Springer, New York, 1997.
doi: 10.1007/978-3-662-03427-9. |
| [2] |
P. Chrystal, On the problem to construct the minimum circle enclosing n given points in a plan, in Proceedings of the Edinburgh Mathematical Society, Tird Meeting, 1885, 30. |
| [3] |
J. Eliosoff and R. Unger, Minimal spanning circle of a set of points, Computer Science: Computational Geometry Project, School of Computer Science, McGill University, 1998,308– 507. |
| [4] |
J. Elzinga and D. Hearn,
The minimum covering sphere problem, Management Sci., 19 (1972), 96-104.
doi: 10.1287/mnsc.19.1.96. |
| [5] |
B. Gärtner, Fast and robust smallest enclosing balls, in Algorithms-ESA' 99: 7th Annual European Symposium, Proceedings (eds. J. Nestril), Lecture Notes in Computer Science, 1643, Springer-Verlag, 1999,325–338. |
| [6] |
D. W. Hearn and J. Vijan,
Efficient algorithms for the minimum circle problem, Oper. Res., 30 (1982), 777-795.
doi: 10.1287/opre.30.4.777. |
| [7] |
M. Lobo, L. Vandenberghe, S. Boyd and H. Lebret,
Applications of second-order cone programming, Linear Albebra and its Applications, 284 (1998), 193-228.
doi: 10.1016/S0024-3795(98)10032-0. |
| [8] |
J. Sturm, Using SeDuMi 1. 02, a MATLAB toolbox for optimization over symmetric cones Optim. Methods Softw., 11/12 (1999), 625-653.
doi: 10.1080/10556789908805766. |
| [9] |
Y. Tian, S. C. Fang, Z. B. Deng and W. X. 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 and Management Optimization, 9 (2013), 703-721.
doi: 10.3934/jimo.2013.9.703. |
| [10] |
S. Y. Wang, Y. J. Liu and Y. Jiang,
A majorized penalty approach to inverse linear second order cone programming problems, Journal of Industrial and Management Optimization, 10 (2014), 965-976.
doi: 10.3934/jimo.2014.10.965. |
| [11] |
E. Welzl, Smalleat enclosing disks (balls and ellipsoids), in New Results and New Trends in Computer Science, Springer-Verlag, 1991,359–370.
doi: 10.1007/BFb0038202. |
| [12] |
S. Xu, R. Freund and J. Sun,
Solution methodologies for the smallest enclosing circle problem, Comput. Optim. Appl., 25 (2003), 283-292.
doi: 10.1023/A:1022977709811. |
| [13] |
Y. Zhang, Y. Jiang, L. Zhang and J. Zhang,
A perturbation approach for an inverse linear second-order cone programming, Journal of Industrial and Management Optimization, 9 (2013), 171-189.
doi: 10.3934/jimo.2013.9.171. |
Table 1.
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 |
Table 2.
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 |
Table 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 |
Table 4.
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 and 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 and 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 and Management Optimization, 2015, 11 (4) : 1111-1125. doi: 10.3934/jimo.2015.11.1111 |
| [4] |
Narges Torabi Golsefid, Maziar Salahi. Second order cone programming formulation of the fixed cost allocation in DEA based on Nash bargaining game. Numerical Algebra, Control and Optimization, 2021 doi: 10.3934/naco.2021032 |
| [5] |
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 and Management Optimization, 2013, 9 (3) : 703-721. doi: 10.3934/jimo.2013.9.703 |
| [6] |
Xinmin Yang. On second order symmetric duality in nondifferentiable multiobjective programming. Journal of Industrial and Management Optimization, 2009, 5 (4) : 697-703. doi: 10.3934/jimo.2009.5.697 |
| [7] |
Liping Tang, Xinmin Yang, Ying Gao. Higher-order symmetric duality for multiobjective programming with cone constraints. Journal of Industrial and Management Optimization, 2020, 16 (4) : 1873-1884. doi: 10.3934/jimo.2019033 |
| [8] |
Qingsong Duan, Mengwei Xu, Liwei Zhang, Sainan Zhang. Hadamard directional differentiability of the optimal value of a linear second-order conic programming problem. Journal of Industrial and Management Optimization, 2021, 17 (6) : 3085-3098. doi: 10.3934/jimo.2020108 |
| [9] |
Charles Fefferman. Interpolation by linear programming I. Discrete and Continuous Dynamical Systems, 2011, 30 (2) : 477-492. doi: 10.3934/dcds.2011.30.477 |
| [10] |
Ziye Shi, Qingwei Jin. Second order optimality conditions and reformulations for nonconvex quadratically constrained quadratic programming problems. Journal of Industrial and Management Optimization, 2014, 10 (3) : 871-882. doi: 10.3934/jimo.2014.10.871 |
| [11] |
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 |
| [12] |
Yi Xu, Wenyu Sun. A filter successive linear programming method for nonlinear semidefinite programming problems. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 193-206. doi: 10.3934/naco.2012.2.193 |
| [13] |
Yanqun Liu, Ming-Fang Ding. A ladder method for linear semi-infinite programming. Journal of Industrial and Management Optimization, 2014, 10 (2) : 397-412. doi: 10.3934/jimo.2014.10.397 |
| [14] |
Ali Tebbi, Terence Chan, Chi Wan Sung. Linear programming bounds for distributed storage codes. Advances in Mathematics of Communications, 2020, 14 (2) : 333-357. doi: 10.3934/amc.2020024 |
| [15] |
Yanqun Liu. Duality in linear programming: From trichotomy to quadrichotomy. Journal of Industrial and Management Optimization, 2011, 7 (4) : 1003-1011. doi: 10.3934/jimo.2011.7.1003 |
| [16] |
Ruotian Gao, Wenxun Xing. Robust sensitivity analysis for linear programming with ellipsoidal perturbation. Journal of Industrial and Management Optimization, 2020, 16 (4) : 2029-2044. doi: 10.3934/jimo.2019041 |
| [17] |
Yanqin Bai, Pengfei Ma, Jing Zhang. A polynomial-time interior-point method for circular cone programming based on kernel functions. Journal of Industrial and Management Optimization, 2016, 12 (2) : 739-756. doi: 10.3934/jimo.2016.12.739 |
| [18] |
Yue Zheng, Zhongping Wan, Shihui Jia, Guangmin Wang. A new method for strong-weak linear bilevel programming problem. Journal of Industrial and Management Optimization, 2015, 11 (2) : 529-547. doi: 10.3934/jimo.2015.11.529 |
| [19] |
Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial and Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399 |
| [20] |
Liming Sun, Li-Zhi Liao. An interior point continuous path-following trajectory for linear programming. Journal of Industrial and Management Optimization, 2019, 15 (4) : 1517-1534. doi: 10.3934/jimo.2018107 |
2021 Impact Factor: 1.411
Tools
Metrics
Other articles
by authors
[Back to Top]