American Institute of Mathematical Sciences

doi: 10.3934/jimo.2020136

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

* Corresponding author: yijiang103@163.com

Received  March 2020 Revised  June 2020 Published  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.

Citation: Yi Jiang, Yuan Cai. A reformulation-linearization based algorithm for the smallest enclosing circle problem. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2020136
References:

show all references

References:
The error for under-estimating a square
Average CPU time of three methods in 2D
Average CPU time of three methods in 3D
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
 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
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
 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
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
 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
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
 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
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
 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
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
 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] 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] 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 [10] 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 [11] 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 [12] 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 [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] 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 [17] 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 [18] 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 [19] 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 [20] Marita Holtmannspötter, Arnd Rösch, Boris Vexler. A priori error estimates for the space-time finite element discretization of an optimal control problem governed by a coupled linear PDE-ODE system. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021014

2019 Impact Factor: 1.366