A deterministic method for continuous global optimization using a dense curve. (English) Zbl 07318129

Summary: In this paper, we develop a new approach for solving a large class of global optimization problems for objective functions which are only continuous on a rectangle of \(\mathbb{R}^n\). This method is based on the reducing transformation technique by running in the feasible domain a single parametrized Lissajous curve, which becomes increasingly denser and progressively fills the feasible domain. By means of the one-dimensional Evtushenko algorithm, we realize a mixed method which explores the feasible domain. To speed up the mixed exploration algorithm, we have incorporated a DIRECT local search type algorithm to explore promising regions. This method converges in a finite number of iterations to the global minimum within a prescribed accuracy \(\varepsilon > 0\). Simulations on some typical test problems with diverse properties and different dimensions indicate that the algorithm is promising and competitive.


90Cxx Mathematical programming
90-XX Operations research, mathematical programming


Full Text: DOI


[1] https://www.encyclopediaofmath.org//index.php?title=Kronecker_theorem.
[2] https://www.mathworks.com/products/global-optimization.html.
[3] Virtual Library of Simulation Experiments: Test Functions and Datasets. https://www.sfu.ca/
[4] https://www.mat.univie.ac.at/ neum/software/mcs/.
[5] http://www.glopt.net/softwares.html.
[6] http://yarpiz.com/231/ypea107-differential-evolution.
[7] https://yarpiz.com/235/ypea108-cma-es.
[8] https://yarpiz.com/297/ypea114-artificial-bee-colony.
[9] http://www.particleswarm.info/Programs.html.
[10] https://www.mathworks.com/matlabcentral/fileexchange/28850-harmony-search-algorithm.
[11] https://www.mathworks.com/matlabcentral/fileexchange/73352-equilibrium-optimizer-eo.
[12] https://www.mathworks.com/matlabcentral/fileexchange/68373-coa.
[13] Al-Khazali, H. A.; Askari, M. R., Geometrical and graphical representations analysis of Lissajous figures in rotor dynamic system, IOSR J. Eng., 2, 5, 971-978 (2012)
[14] Ali, M. M.; Khompatraporn, C.; Zabinsky, Z. B., A numerical evaluation of several stochastic algorithms on selected continuous global optimization test problems, J. Global Optim., 31, 635-672 (2005) · Zbl 1093.90028
[15] Anuar, S.; Selamat, A.; Sallehuddin, R., A modified scout bee for artificial bee colony algorithm and its performance on optimization problems, J. King Saud Univ. Comput. Inf. Sci., 28, 4, 395-406 (2016)
[16] Bagirov, A. M.; Rubinov, A. M.; Zhang, J., A multidimensional descent method for global optimization, Optimization, 58, 611-625 (2009) · Zbl 1167.49028
[17] Bos, L.; De Marchi, S.; Vianello, M., Polynomial approximation on Lissajous curves in the d-cube, Appl. Numer. Math., 116, 47-56 (2017) · Zbl 1372.65028
[18] Brachetti, P.; Ciccoli, M. D.F.; Di Pillo, G.; Lucidi, S., A new version of the Price’s algorithm for global optimization, J. Glob. Opt., 10, 2, 165-184 (1997) · Zbl 0877.65038
[19] Brownlee, J., Clever Algorithms: Nature-Inspired Programming Recipes (2011), Jason Brownlee
[20] Cherruault, Y., Optimisation, Méthodes Locales Et Globales (1999), Presses Universitaires de France · Zbl 0928.49001
[21] Cherruault, Y., A new reducing transformation for global optimization (with Alienor method), Kybernetes, 34, 1084-1089 (2005) · Zbl 1130.90398
[22] Chivers, I.; Sleightholme, J., An introduction to algorithms and the big o notation, (Introduction To Programming with Fortran (2015), Springer: Springer Cham), 359-364
[23] Cundy, H.; Rollett, A., Lissajous’s figures, (Mathematical Models (1989)), 242-244
[24] Dolan, E. D.; Moré, J. J., Benchmarking optimization software with performance profiles, Math. Prog., 91, 201-213 (2002) · Zbl 1049.90004
[25] Ellaia, R.; Es-Sadek, M. Z.; Kasbioui, H., Modified Piyavskii’s global one-dimensional optimization of a differentiable function, Appl. Math., 3, 10, 1306 (2012)
[26] Evtushenko, Y. G., Numerical Optimization Techniques (1985), Springer: Springer Berlin
[27] Faramarzi, A.; Heidarinejad, M.; Stephens, B.; Mirjalili, S., Equilibrium optimizer: A novel optimization algorithm, Knowl.-Based Syst., 191, Article 105190 pp. (2020)
[28] Ferreiro, A. M.; Garcia-Rodrí guez, J. A.; Vázquez, C.; e Silva, E. C.; Correia, A., Parallel two-phase methods for global optimization on GPU, Math. Comput. Simulation, 156, 67-90 (2019)
[29] García, S.; Molina, D.; Lozano, M.; Herrera, F., A study on the use of non-parametric tests for analyzing the evolutionary algorithms’ behaviour: a case study on the CEC’2005 special session on real parameter optimization, J. Heuristics, 15, 6, 617 (2009) · Zbl 1191.68828
[30] Geem, Z. W.; Kim, J. H.; Loganathan, G. V., A new heuristic optimization algorithm: harmony search, Simulation, 76, 2, 60-68 (2001)
[31] Greenslade, T. B., All about lissajous figures, Phys. Teach., 31, 6, 364-370 (1993)
[32] N. Hansen, A. Ostermeier, Adapting arbitrary normal mutation distributions in evolution strategies: the covariance matrix adaptation, in: Proceedings of the 1996 IEEE International Conference on Evolutionary Computation, 1996, pp. 312-317.
[33] Hou, Y.; Chen, W.; Yu, Y.; Duan, X.; Xu, M.; Ye, M., Study of nonlinear mode-mode couplings between Alfvénic modes by the Fourier bicoherence and Lissajous-curve technique in HL-2A, (Plasma Science and Technology (2019))
[34] Huyer, W.; Neumaier, A., Global optimization by multilevel coordinate search, J. Glob. Opt., 14, 4, 331-355 (1999) · Zbl 0956.90045
[35] Karaboga, D.; Basturk, B., A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm, J. Glob. Opt., 39, 3, 459-471 (2007) · Zbl 1149.90186
[36] Ketfi-Cherif, A.; Ziadi, A., Global descent method for constrained continuous global optimization, Appl. Math. Comput., 244, 209-221 (2014) · Zbl 1335.90073
[37] Kolda, T. G.; Lewis, R. M.; Torczon, V. J., Optimization by direct search: New perspectives on some classical and modern methods, SIAM Rev., 45, 385-482 (2003) · Zbl 1059.90146
[38] Kvasov, D. E.; Mukhametzhanov, M. S., Metaheuristic vs deterministic global optimization algorithms: The univariate case, Appl. Math. Comput., 318, 245-259 (2018) · Zbl 1426.90208
[39] Kvasov, D. E.; Sergeyev, Y. D., A univariate global search working with a set of Lipschitz constants for the first derivative, Optim. Lett., 3, 2, 303-318 (2009) · Zbl 1173.90544
[40] Lera, D.; Sergeyev, Y. D., Acceleration of univariate global optimization algorithms working with Lipschitz functions and Lipschitz first derivatives, SIAM J. Optim., 23, 1, 508-529 (2013) · Zbl 1270.90049
[41] Lera, D.; Sergeyev, Y. D., Deterministic global optimization using space-filling curves and multiple estimates of Lipschitz and Holder constants, Commun. Non. Sci. Num. Sim., 23, 1-3, 328-342 (2015) · Zbl 1356.90112
[42] Lera, D.; Sergeyev, Y. D., GOSH: derivative-free global optimization using multi-dimensional space-filling curves, J. Glob. Opt., 71, 1, 193-211 (2018) · Zbl 1402.90133
[43] Levine, H. B., Sensitivity analysis of a chemical laser system (no. SSS-R-75-2684), (Systems Science and Software La Jolla CA (1975))
[44] Lewis, R. M.; Torczon, V., Pattern search algorithms for bound constrained minimization, SIAM J. Optim., 9, 1082-1099 (1999) · Zbl 1031.90047
[45] Lewis, R. M.; Torczon, V., Pattern search methods for linearly constrained minimization, SIAM J. Optim., 10, 917-941 (2000) · Zbl 1031.90048
[46] Malajovich, G., An Effective Version of Kronecker’S Theorem on Simultaneous Diophantine ApproximationTechnical Report (1996), City University of Hong Kong
[47] McRae, G. J.; Tilden, J. W.; Seinfeld, J. H., Global sensitivity analysis-a computational implementation of the Fourier amplitude sensitivity test (FAST), Comput. Chem. Eng., 6, 1, 15-25 (1982)
[48] Paulavic̃ius, R.; Sergeyev, Y. D.; Kvasov, D. E.; Zilinskas, J., Globally-biased BIRECT algorithm with local accelerators for expensive global optimization, Exp. Syst. Appl., Article 113052 pp. (2019)
[49] J. Pierezan, L.S. Coelho, Coyote Optimization Algorithm: A new metaheuristic for global optimization problems, in: Proceedings of the IEEE Congress on Evolutionary Computation, CEC, Rio de Janeiro, Brazil, July 2018, pp. 2633-2640.
[50] Pintér, J. D., Global optimization: software, test problems, and applications, (Pardalos, P. M.; Romeijn, H. E., Handbook of Global Optimization, vol. 2 (2002), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht), 515-569 · Zbl 1029.90058
[51] Pintér, J. D., Global Optimization: Scientific and Engineering Case Studies, Vol. 85 (2006), Springer Science & Business Media · Zbl 1103.90011
[52] Rahal, M.; Ziadi, A., A new extension of piyavskii’s method to Hölder functions of several variables, Appl. Math. Comput., 197, 478-488 (2008) · Zbl 1154.65050
[53] O. Schutze, E.G. Talbi, C.A. Coello Coello, L.V. Santana Quintero, A Memetic PSO Algorithm for Scalar Optimization Problems, in: Proceedings of the 2007 IEEE Swarm Intelligence Symposium, SIS 2007.
[54] Sergeyev, Y. D.; Kvasov, D. E., On deterministic diagonal methods for solving global optimization problems with Lipschitz gradients, (Optimization, Control, and Applications in the Information Age (2015)), 315-334 · Zbl 1365.90222
[55] Sergeyev, Y. D.; Strongin, R. G.; Lera, D., Introduction To Global Optimization Exploiting Space-Filling Curves (2013), Springer Science & Business Media · Zbl 1278.90005
[56] Shen, P.; Wang, Y., A new pruning test for finding all global minimizers of nonsmooth functions, Appl. Math. Comput., 168, 739-755 (2005) · Zbl 1107.65322
[57] Storn, R.; Price, K., Differential evolution - a simple and efficient heuristic for global optimization over continuous spaces, J. Glob. Opt., 11, 4, 341-359 (1997) · Zbl 0888.90135
[58] P.N. Suganthan, N. Hansen, J.J. Liang, K. Deb, Y.P. Chen, A. Auger, S. Tiwari, Problem Definitions and Evaluation Criteria for the Cec 2005 Special Session on Real-Parameter Optimization, KanGAL Report.
[59] Torczon, V., On the convergence of pattern search algorithms, SIAM J. Optim., 7, 1-25 (1997) · Zbl 0884.65053
[60] Y. D. Sergeyev, D. E.; Mukhametzhanov, M. S., Operational zones for comparing metaheuristic and deterministic one-dimensional global optimization algorithms, Math. Comput. Simulation, 141, 96-109 (2017)
[61] Zambrano-Bigiarini, M.; Maurice, C.; Rodrigo, R., Standard particle swarm optimisation 2011 at cec-2013: A baseline for future pso improvements, (Evolutionary Computation (CEC), (2013) IEEE Congress on (2013), IEEE)
[62] Ziadi, R.; Bencherif-Madani, A.; Ellaia, R., Continuous global optimization through the generation of parametric curves, Appl. Math. Comput., 282, 65-83 (2016) · Zbl 1410.90172
[63] Ziadi, A.; Cherruault, Y., Generation of \(\alpha \)-dense curves and application to global optimization, Kybernetes, 29, 1, 71-82 (2000) · Zbl 0978.90090
[64] Ziadi, A.; Cherruault, Y.; Mora, G., Global optimization: A new variant of the Alienor method, Comput. Math. Appl., 41, 63-71 (2001) · Zbl 0980.90069
[65] Ziadi, R.; Ellaia, R.; Bencherif-Madani, A., Global optimization through a stochastic perturbation of the Polak-Ribière conjugate gradient method, J. Comput. Appl. Math., 317, 672-684 (2017) · Zbl 1381.90069
[66] Ziadi, A.; Guettal, D.; Cherruault, Y., Global optimization: The Alienor mixed method with Piyavskii-Shubert technique, Kybernetes, 34, 7/8, 1049-1058 (2005) · Zbl 1130.90405
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.