American Institute of Mathematical Sciences

Advanced
November  2021, 17(6): 3633-3644. doi: 10.3934/jimo.2020136

A reformulation-linearization based algorithm for the smallest enclosing circle problem

Yi Jiang , and  Yuan Cai

School of Mathematical Sciences and VC/VR Key Lab, Sichuan Normal University, Chengdu, Sichuan 610066, China

* Corresponding author: yijiang103@163.com

Received  March 2020 Revised  June 2020 Published  November 2021 Early access  August 2020

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, an effective algorithm based on the reformulation-linearization technique (RLT) is developed to solve the smallest enclosing circle problem. Extensive computational experiments demonstrate that the algorithm based on the RLT outperforms the existing algorithms in terms of the solution time and quality in average.

Keywords: The smallest enclosing circle, second order cone programming, linear programming.
Mathematics Subject Classification: Primary: 90C30.
Citation: Yi Jiang, Yuan Cai. A reformulation-linearization based algorithm for the smallest enclosing circle problem. Journal of Industrial and Management Optimization, 2021, 17 (6) : 3633-3644. doi: 10.3934/jimo.2020136
References:
[1]

C. Audet, P. Hansen, B. Jaumard and G. Savard, A branch and cut algorithm for nonconvex quadratically constrained quadratic programming, Math. Program., 87 (2000), 131-152.  doi: 10.1007/s101079900106.

[2]

M. de Berg, O. Cheong, M. van Kreveld and M. Overmars, Computational Geometry: Algorithms and Applications, Springer, Berlin, Heidelberg, 2008. doi: 10.1007/978-3-540-77974-2.

[3]

P. Chrystal, On the problem to construct the minimum circle enclosing n given points in a plane, Proceedings of the Edinburgh Mathematical Society, 3 (1884), 30-33.  doi: 10.1017/S0013091500037238.

[4]

D. W. Hearn and J. Vijay, Efficient algorithms for the (weighted) minimum circle problem, Oper. Res., 30 (1982), 777-795.  doi: 10.1287/opre.30.4.777.

[5]

Y. Jiang, C. Luo and S. G. Ling, An efficient cutting plane algorithm for the smallest enclosing circle problem, J. Ind. Manag. Optim., 13 (2017), 147-153.  doi: 10.3934/jimo.2016009.

[6]

H. D. Sherali and C. H. Tuncbilek, Global optimization algorithm for polynomial programming using a reformulation-linearization technique, J. Global Optim., 2 (1992), 101-112.  doi: 10.1007/BF00121304.

[7]

H. D. Sherali and C. H. Tuncbilek, Reformulation-convexification approach for solving nonconvex quadratic programming problems, J. Global Optim., 7 (1995), 1-31. doi: 10.1007/BF01100203.

[8]

H. D. Sherali and C. H. Tuncbilek, Comparison of two reformulation-linearization technique based linear programming relaxations for polynomial programming problems, J. Global Optim., 10 (1997), 381-390.  doi: 10.1023/A:1008237515535.

[9]

S. H. Pan and X. S. Li, An efficient algorithm for the smallest enclosing ball problem in high dimension, Appl. Math. Comput., 172 (2006), 49-61.  doi: 10.1016/j.amc.2005.01.127.

[10]

S. Skyum, A simple algorithm for computing the smallest enclosing circle, Inform. Process. Lett., 37 (1991), 121-125.  doi: 10.1016/0020-0190(91)90030-L.

[11]

J. Sturm, Using SeDuMi 1.02, A MATLAB toolbox for optimization over symmetric cones. Interior point methods, Optim. Methods Softw. 11/12 (1999), 625-653. doi: 10.1080/10556789908805766.

[12]

J. J. Sylvester, A question in the geometry of situation, Quart. J. Math., 1 (1857), 79.

[13]

E. Welzl, Smallest enclosing disks (balls and ellipsoids), in New Results and New Trends in Computer Science, Springer, Berlin, 1991,359-370. doi: 10.1007/BFb0038202.

[14]

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.

[15]

E. A. Yildirim, Two algorithms for the minimum enclosing ball problem, SIAM J. Optim., 19 (2008), 1368-1391.  doi: 10.1137/070690419.

[16]

G. Zhou, K. C. Tohemail and J. Sun, Efficient algorithms for the smallest enclosing ball problem, Comput. Optim. Appl., 30 (2005), 147-160.  doi: 10.1007/s10589-005-4565-7.

show all references

References:
[1]

C. Audet, P. Hansen, B. Jaumard and G. Savard, A branch and cut algorithm for nonconvex quadratically constrained quadratic programming, Math. Program., 87 (2000), 131-152.  doi: 10.1007/s101079900106.

[2]

M. de Berg, O. Cheong, M. van Kreveld and M. Overmars, Computational Geometry: Algorithms and Applications, Springer, Berlin, Heidelberg, 2008. doi: 10.1007/978-3-540-77974-2.

[3]

P. Chrystal, On the problem to construct the minimum circle enclosing n given points in a plane, Proceedings of the Edinburgh Mathematical Society, 3 (1884), 30-33.  doi: 10.1017/S0013091500037238.

[4]

D. W. Hearn and J. Vijay, Efficient algorithms for the (weighted) minimum circle problem, Oper. Res., 30 (1982), 777-795.  doi: 10.1287/opre.30.4.777.

[5]

Y. Jiang, C. Luo and S. G. Ling, An efficient cutting plane algorithm for the smallest enclosing circle problem, J. Ind. Manag. Optim., 13 (2017), 147-153.  doi: 10.3934/jimo.2016009.

[6]

H. D. Sherali and C. H. Tuncbilek, Global optimization algorithm for polynomial programming using a reformulation-linearization technique, J. Global Optim., 2 (1992), 101-112.  doi: 10.1007/BF00121304.

[7]

H. D. Sherali and C. H. Tuncbilek, Reformulation-convexification approach for solving nonconvex quadratic programming problems, J. Global Optim., 7 (1995), 1-31. doi: 10.1007/BF01100203.

[8]

H. D. Sherali and C. H. Tuncbilek, Comparison of two reformulation-linearization technique based linear programming relaxations for polynomial programming problems, J. Global Optim., 10 (1997), 381-390.  doi: 10.1023/A:1008237515535.

[9]

S. H. Pan and X. S. Li, An efficient algorithm for the smallest enclosing ball problem in high dimension, Appl. Math. Comput., 172 (2006), 49-61.  doi: 10.1016/j.amc.2005.01.127.

[10]

S. Skyum, A simple algorithm for computing the smallest enclosing circle, Inform. Process. Lett., 37 (1991), 121-125.  doi: 10.1016/0020-0190(91)90030-L.

[11]

J. Sturm, Using SeDuMi 1.02, A MATLAB toolbox for optimization over symmetric cones. Interior point methods, Optim. Methods Softw. 11/12 (1999), 625-653. doi: 10.1080/10556789908805766.

[12]

J. J. Sylvester, A question in the geometry of situation, Quart. J. Math., 1 (1857), 79.

[13]

E. Welzl, Smallest enclosing disks (balls and ellipsoids), in New Results and New Trends in Computer Science, Springer, Berlin, 1991,359-370. doi: 10.1007/BFb0038202.

[14]

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.

[15]

E. A. Yildirim, Two algorithms for the minimum enclosing ball problem, SIAM J. Optim., 19 (2008), 1368-1391.  doi: 10.1137/070690419.

[16]

G. Zhou, K. C. Tohemail and J. Sun, Efficient algorithms for the smallest enclosing ball problem, Comput. Optim. Appl., 30 (2005), 147-160.  doi: 10.1007/s10589-005-4565-7.

Figure 1.  The error for under-estimating a square
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.  Average CPU time of three methods in 2D
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3.  Average CPU time of three methods in 3D
Figure Options

Download full-size image

Download as PowerPoint slide

Table 1.  Computational results for 30000 circles by Algorithm Ⅰ in 2D
k R (x, y) Time
$ 1 $ 22.39739458 (-0.23034495, 1.54096380) 1256
$ 2 $ 22.45136334 (-0.22954489, 1.54016746) 4437
$ 3 $ 22.45378444 (-0.22950900, 1.54013173) 4705
$ 4 $ 22.45382627 (-0.22950838, 1.54013111) 4817
Table Options

Download as excel

k R (x, y) Time
$ 1 $ 22.39739458 (-0.23034495, 1.54096380) 1256
$ 2 $ 22.45136334 (-0.22954489, 1.54016746) 4437
$ 3 $ 22.45378444 (-0.22950900, 1.54013173) 4705
$ 4 $ 22.45382627 (-0.22950838, 1.54013111) 4817
Table 2.  The number of iterations on Algorithm Ⅰ in 2D
Problem Iteration
m Average Maximum Minimum
$ 30 $ 4.48 6 4
$ 300 $ 4.12 5 3
$ 3000 $ 3.78 4 3
$ 30000 $ 3.70 4 3
Table Options

Download as excel

Problem Iteration
m Average Maximum Minimum
$ 30 $ 4.48 6 4
$ 300 $ 4.12 5 3
$ 3000 $ 3.78 4 3
$ 30000 $ 3.70 4 3
Table 3.  Objective function value and average CPU time of four methods in 2D
Problem SOCP CP SDPT3 Algorithm Ⅰ
m Obj Value Time Obj Value Time Obj Value Time Obj Value Time
$ 30 $ 9.13411 128.98 9.13411 125.80 9.13411 1744.45 9.13411 66.50
$ 300 $ 15.05421 179.80 15.05421 165.26 15.05421 6848.30 15.05421 70.60
$ 3000 $ 18.31612 781.82 18.31612 918.92 18.31612 65688.71 18.31612 530.66
$ 30000 $ 21.21799 25641.96 21.21799 15716.18 21.21799 1548266.51 21.21799 5052.26
Table Options

Download as excel

Problem SOCP CP SDPT3 Algorithm Ⅰ
m Obj Value Time Obj Value Time Obj Value Time Obj Value Time
$ 30 $ 9.13411 128.98 9.13411 125.80 9.13411 1744.45 9.13411 66.50
$ 300 $ 15.05421 179.80 15.05421 165.26 15.05421 6848.30 15.05421 70.60
$ 3000 $ 18.31612 781.82 18.31612 918.92 18.31612 65688.71 18.31612 530.66
$ 30000 $ 21.21799 25641.96 21.21799 15716.18 21.21799 1548266.51 21.21799 5052.26
Table 4.  Computational results for 20000 balls by Algorithm Ⅰ in 3D
k R (x, y, z) Time
$ 1 $ 21.18238030 (-0.41033399, 0.50362615, -1.77470296) 2682
$ 2 $ 21.25471838 (-0.40932025, 0.50524350, -1.77617447) 4658
$ 3 $ 21.25805248 (-0.40927352, 0.50531805, -1.77624230) 6623
$ 4 $ 21.25808485 (-0.40927307, 0.50531877, -1.77624296) 10525
$ 5 $ 21.25808512 (-0.40927306, 0.50531878, -1.77624296) 14668
Table Options

Download as excel

k R (x, y, z) Time
$ 1 $ 21.18238030 (-0.41033399, 0.50362615, -1.77470296) 2682
$ 2 $ 21.25471838 (-0.40932025, 0.50524350, -1.77617447) 4658
$ 3 $ 21.25805248 (-0.40927352, 0.50531805, -1.77624230) 6623
$ 4 $ 21.25808485 (-0.40927307, 0.50531877, -1.77624296) 10525
$ 5 $ 21.25808512 (-0.40927306, 0.50531878, -1.77624296) 14668
Table 5.  The number of iterations on Algorithm Ⅰ in 3D
Problem Iteration
m Average Maximum Minimum
$ 20 $ 8.96 13 5
$ 200 $ 6.54 11 4
$ 2000 $ 6.68 12 4
$ 20000 $ 5.84 10 4
Table Options

Download as excel

Problem Iteration
m Average Maximum Minimum
$ 20 $ 8.96 13 5
$ 200 $ 6.54 11 4
$ 2000 $ 6.68 12 4
$ 20000 $ 5.84 10 4
Table 6.  Objective function value and average CPU time of four methods in 3D
Problem SOCP CP SDPT3 Algorithm 1
m Obj Value Time Obj Value Time Obj Value Time Obj Value Time
$ 20 $ 10.20133 131.26 10.20133 138.96 10.20133 1589.39 10.20133 120.92
$ 200 $ 13.90667 168.56 13.90667 251.66 13.90667 5157.42 13.90667 123.88
$ 2000 $ 16.47548 633.00 16.47548 1694.06 16.47548 43022.79 16.47548 161.02
$ 20000 $ 20.54257 16953.74 20.54257 18185.18 20.54257 907801.50 20.54257 1462.04
Table Options

Download as excel

Problem SOCP CP SDPT3 Algorithm 1
m Obj Value Time Obj Value Time Obj Value Time Obj Value Time
$ 20 $ 10.20133 131.26 10.20133 138.96 10.20133 1589.39 10.20133 120.92
$ 200 $ 13.90667 168.56 13.90667 251.66 13.90667 5157.42 13.90667 123.88
$ 2000 $ 16.47548 633.00 16.47548 1694.06 16.47548 43022.79 16.47548 161.02
$ 20000 $ 20.54257 16953.74 20.54257 18185.18 20.54257 907801.50 20.54257 1462.04
[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]

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
[5]

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
[6]

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
[7]

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
[8]

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
[9]

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
[10]

Charles Fefferman. Interpolation by linear programming I. Discrete and Continuous Dynamical Systems, 2011, 30 (2) : 477-492. doi: 10.3934/dcds.2011.30.477
[11]

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
[12]

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
[13]

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
[14]

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
[15]

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
[16]

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
[17]

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
[18]

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
[19]

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
[20]

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

2021 Impact Factor: 1.411

Tools

Metrics

  • PDF downloads (207)
  • HTML views (602)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy