
-
Previous Article
On the optimal control problems with characteristic time control constraints
- JIMO Home
- This Issue
-
Next Article
Quality choice and capacity rationing in advance selling
A reformulation-linearization based algorithm for the smallest enclosing circle problem
School of Mathematical Sciences and VC/VR Key Lab, Sichuan Normal University, Chengdu, Sichuan 610066, China |
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.
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. Google Scholar |
[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. Google Scholar |
[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. |



k | R | (x, y) | Time | |||
22.39739458 | (-0.23034495, 1.54096380) | 1256 | ||||
22.45136334 | (-0.22954489, 1.54016746) | 4437 | ||||
22.45378444 | (-0.22950900, 1.54013173) | 4705 | ||||
22.45382627 | (-0.22950838, 1.54013111) | 4817 |
k | R | (x, y) | Time | |||
22.39739458 | (-0.23034495, 1.54096380) | 1256 | ||||
22.45136334 | (-0.22954489, 1.54016746) | 4437 | ||||
22.45378444 | (-0.22950900, 1.54013173) | 4705 | ||||
22.45382627 | (-0.22950838, 1.54013111) | 4817 |
Problem | Iteration | |||
m | Average | Maximum | Minimum | |
4.48 | 6 | 4 | ||
4.12 | 5 | 3 | ||
3.78 | 4 | 3 | ||
3.70 | 4 | 3 |
Problem | Iteration | |||
m | Average | Maximum | Minimum | |
4.48 | 6 | 4 | ||
4.12 | 5 | 3 | ||
3.78 | 4 | 3 | ||
3.70 | 4 | 3 |
Problem | SOCP | CP | SDPT3 | Algorithm Ⅰ | ||||||||
m | Obj Value | Time | Obj Value | Time | Obj Value | Time | Obj Value | Time | ||||
9.13411 | 128.98 | 9.13411 | 125.80 | 9.13411 | 1744.45 | 9.13411 | 66.50 | |||||
15.05421 | 179.80 | 15.05421 | 165.26 | 15.05421 | 6848.30 | 15.05421 | 70.60 | |||||
18.31612 | 781.82 | 18.31612 | 918.92 | 18.31612 | 65688.71 | 18.31612 | 530.66 | |||||
21.21799 | 25641.96 | 21.21799 | 15716.18 | 21.21799 | 1548266.51 | 21.21799 | 5052.26 |
Problem | SOCP | CP | SDPT3 | Algorithm Ⅰ | ||||||||
m | Obj Value | Time | Obj Value | Time | Obj Value | Time | Obj Value | Time | ||||
9.13411 | 128.98 | 9.13411 | 125.80 | 9.13411 | 1744.45 | 9.13411 | 66.50 | |||||
15.05421 | 179.80 | 15.05421 | 165.26 | 15.05421 | 6848.30 | 15.05421 | 70.60 | |||||
18.31612 | 781.82 | 18.31612 | 918.92 | 18.31612 | 65688.71 | 18.31612 | 530.66 | |||||
21.21799 | 25641.96 | 21.21799 | 15716.18 | 21.21799 | 1548266.51 | 21.21799 | 5052.26 |
k | R | (x, y, z) | Time | |||
21.18238030 | (-0.41033399, 0.50362615, -1.77470296) | 2682 | ||||
21.25471838 | (-0.40932025, 0.50524350, -1.77617447) | 4658 | ||||
21.25805248 | (-0.40927352, 0.50531805, -1.77624230) | 6623 | ||||
21.25808485 | (-0.40927307, 0.50531877, -1.77624296) | 10525 | ||||
21.25808512 | (-0.40927306, 0.50531878, -1.77624296) | 14668 |
k | R | (x, y, z) | Time | |||
21.18238030 | (-0.41033399, 0.50362615, -1.77470296) | 2682 | ||||
21.25471838 | (-0.40932025, 0.50524350, -1.77617447) | 4658 | ||||
21.25805248 | (-0.40927352, 0.50531805, -1.77624230) | 6623 | ||||
21.25808485 | (-0.40927307, 0.50531877, -1.77624296) | 10525 | ||||
21.25808512 | (-0.40927306, 0.50531878, -1.77624296) | 14668 |
Problem | Iteration | |||
m | Average | Maximum | Minimum | |
8.96 | 13 | 5 | ||
6.54 | 11 | 4 | ||
6.68 | 12 | 4 | ||
5.84 | 10 | 4 |
Problem | Iteration | |||
m | Average | Maximum | Minimum | |
8.96 | 13 | 5 | ||
6.54 | 11 | 4 | ||
6.68 | 12 | 4 | ||
5.84 | 10 | 4 |
Problem | SOCP | CP | SDPT3 | Algorithm 1 | ||||||||
m | Obj Value | Time | Obj Value | Time | Obj Value | Time | Obj Value | Time | ||||
10.20133 | 131.26 | 10.20133 | 138.96 | 10.20133 | 1589.39 | 10.20133 | 120.92 | |||||
13.90667 | 168.56 | 13.90667 | 251.66 | 13.90667 | 5157.42 | 13.90667 | 123.88 | |||||
16.47548 | 633.00 | 16.47548 | 1694.06 | 16.47548 | 43022.79 | 16.47548 | 161.02 | |||||
20.54257 | 16953.74 | 20.54257 | 18185.18 | 20.54257 | 907801.50 | 20.54257 | 1462.04 |
Problem | SOCP | CP | SDPT3 | Algorithm 1 | ||||||||
m | Obj Value | Time | Obj Value | Time | Obj Value | Time | Obj Value | Time | ||||
10.20133 | 131.26 | 10.20133 | 138.96 | 10.20133 | 1589.39 | 10.20133 | 120.92 | |||||
13.90667 | 168.56 | 13.90667 | 251.66 | 13.90667 | 5157.42 | 13.90667 | 123.88 | |||||
16.47548 | 633.00 | 16.47548 | 1694.06 | 16.47548 | 43022.79 | 16.47548 | 161.02 | |||||
20.54257 | 16953.74 | 20.54257 | 18185.18 | 20.54257 | 907801.50 | 20.54257 | 1462.04 |
[1] |
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 |
[2] |
Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023 |
[3] |
Anton Schiela, Julian Ortiz. Second order directional shape derivatives of integrals on submanifolds. Mathematical Control & Related Fields, 2021 doi: 10.3934/mcrf.2021017 |
[4] |
Qian Liu. The lower bounds on the second-order nonlinearity of three classes of Boolean functions. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2020136 |
[5] |
Xiaoming Wang. Quasi-periodic solutions for a class of second order differential equations with a nonlinear damping term. Discrete & Continuous Dynamical Systems - S, 2017, 10 (3) : 543-556. doi: 10.3934/dcdss.2017027 |
[6] |
Kaifang Liu, Lunji Song, Shan Zhao. A new over-penalized weak galerkin method. Part Ⅰ: Second-order elliptic problems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2411-2428. doi: 10.3934/dcdsb.2020184 |
[7] |
Caifang Wang, Tie Zhou. The order of convergence for Landweber Scheme with $\alpha,\beta$-rule. Inverse Problems & Imaging, 2012, 6 (1) : 133-146. doi: 10.3934/ipi.2012.6.133 |
[8] |
Alexandre B. Simas, Fábio J. Valentim. $W$-Sobolev spaces: Higher order and regularity. Communications on Pure & Applied Analysis, 2015, 14 (2) : 597-607. doi: 10.3934/cpaa.2015.14.597 |
[9] |
Pavel I. Naumkin, Isahi Sánchez-Suárez. Asymptotics for the higher-order derivative nonlinear Schrödinger equation. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021028 |
[10] |
Diana Keller. Optimal control of a linear stochastic Schrödinger equation. Conference Publications, 2013, 2013 (special) : 437-446. doi: 10.3934/proc.2013.2013.437 |
[11] |
Guillaume Bal, Wenjia Jing. Homogenization and corrector theory for linear transport in random media. Discrete & Continuous Dynamical Systems - A, 2010, 28 (4) : 1311-1343. doi: 10.3934/dcds.2010.28.1311 |
[12] |
Nizami A. Gasilov. Solving a system of linear differential equations with interval coefficients. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2739-2747. doi: 10.3934/dcdsb.2020203 |
[13] |
Alexander A. Davydov, Massimo Giulietti, Stefano Marcugini, Fernanda Pambianco. Linear nonbinary covering codes and saturating sets in projective spaces. Advances in Mathematics of Communications, 2011, 5 (1) : 119-147. doi: 10.3934/amc.2011.5.119 |
[14] |
W. Cary Huffman. On the theory of $\mathbb{F}_q$-linear $\mathbb{F}_{q^t}$-codes. Advances in Mathematics of Communications, 2013, 7 (3) : 349-378. doi: 10.3934/amc.2013.7.349 |
[15] |
Arunima Bhattacharya, Micah Warren. $ C^{2, \alpha} $ estimates for solutions to almost Linear elliptic equations. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021024 |
[16] |
A. Aghajani, S. F. Mottaghi. Regularity of extremal solutions of semilinaer fourth-order elliptic problems with general nonlinearities. Communications on Pure & Applied Analysis, 2018, 17 (3) : 887-898. doi: 10.3934/cpaa.2018044 |
[17] |
Misha Bialy, Andrey E. Mironov. Rich quasi-linear system for integrable geodesic flows on 2-torus. Discrete & Continuous Dynamical Systems - A, 2011, 29 (1) : 81-90. doi: 10.3934/dcds.2011.29.81 |
[18] |
Fumihiko Nakamura. Asymptotic behavior of non-expanding piecewise linear maps in the presence of random noise. Discrete & Continuous Dynamical Systems - B, 2018, 23 (6) : 2457-2473. doi: 10.3934/dcdsb.2018055 |
[19] |
Christophe Zhang. Internal rapid stabilization of a 1-D linear transport equation with a scalar feedback. Mathematical Control & Related Fields, 2021 doi: 10.3934/mcrf.2021006 |
[20] |
Hirofumi Notsu, Masato Kimura. Symmetry and positive definiteness of the tensor-valued spring constant derived from P1-FEM for the equations of linear elasticity. Networks & Heterogeneous Media, 2014, 9 (4) : 617-634. doi: 10.3934/nhm.2014.9.617 |
2019 Impact Factor: 1.366
Tools
Article outline
Figures and Tables
[Back to Top]