×

Adaptive global optimization based on a block-recursive dimensionality reduction scheme. (English. Russian original) Zbl 1457.90117

Autom. Remote Control 81, No. 8, 1475-1485 (2020); translation from Avtom. Telemekh. 2020, No. 8, 136-148 (2020).
Summary: Multidimensional multiextremal optimization problems and numerical methods for solving them are studied. The objective function is supposed to satisfy the Lipschitz condition with an a priori unknown constant, which is the only general assumption imposed on it. Problems of this type often arise in applications. Two dimensionality reduction approaches to multidimensional optimization problems, i.e., the use of Peano curves (evolvents) and a recursive multistep scheme, are considered. A generalized scheme combining both approaches is proposed. In the new scheme, an original multidimensional problem is reduced to a family of lower-dimensional problems, which are solved using evolvents. An adaptive algorithm with the simultaneous solution of all resulting subproblems is implemented. Computational experiments on several hundred test problems are performed. In accordance with experimental evidence, the new dimensional reduction scheme is effective.

MSC:

90C26 Nonconvex programming, global optimization
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Evtushenko, YuG, Numerical Methods for Finding Global Extrema (Case of a Non-uniform Mesh), USSR Comput. Math. Math. Phys., 11, no. 6, 38-54 (1971) · Zbl 0258.90045
[2] Piyavskii, SA, An Algorithm for Finding the Absolute Extremum of a Function, USSR Comput. Math. Math. Phys., 12, no. 4, 57-67 (1972) · Zbl 0282.65052
[3] Shubert, BO, A Sequential Method Seeking the Global Maximum of a Function, SIAM J. Numer. Anal., 9, 379-388 (1972) · Zbl 0251.65052
[4] Jones, DR; Perttunen, CD; Stuckman, BE, Lipschitzian Optimization without the Lipschitz Constant, J. Optim. Theory Appl., 79, no. 1, 157-181 (1993) · Zbl 0796.49032
[5] Pinter, JD, Global Optimization in Action (Continuous and Lipschitz Optimization: Algorithms, Implementations and Applications) (1996), Dordrecht: Kluwer, Dordrecht · Zbl 0842.90110
[6] Žilinskas, J., Branch and Bound with Simplicial Partitions for Global Optimization, Math. Model. Anal., 13, no. 1, 145-159 (2008) · Zbl 1146.49029
[7] Evtushenko, YuG; Malkova, VU; Stanevichyus, AA, Parallelization of the Global Extremum Searching Process, Autom, Remote Control, 68, no. 5, 787-798 (2007) · Zbl 1151.68390
[8] Evtushenko, YG; Malkova, VU; Stanevichyus, AA, Parallel Global Optimization of Functions of Several Variables, Comput. Math. Math. Phys., 49, no. 2, 246-260 (2009)
[9] Jones, D.R.The DIRECT Global Optimization Algorithm, in The Encyclopedia of Optimization, Floudas, C.A., and Pardalos, P.M., Eds., Springer, 2009, 2nd ed., pp. 725-735.
[10] Paulavičius, R.; Žilinskas, J.; Grothey, A., Investigation of Selection Strategies in Branch and Bound Algorithm with Simplicial Partitions and Combination of Lipschitz Bounds, Optim. Lett., 4, no. 1, 173-83 (2010) · Zbl 1189.90203
[11] Evtushenko, YG; Posypkin, MA, A Deterministic Approach to Global Box-Constrained Optimization, Optim. Lett., 7, no. 4, 819-829 (2013) · Zbl 1269.90082
[12] Kvasov, DE; Sergeyev, YaD, Lipschitz Global Optimization Methods in Control Problems, Autom. Remote Control, 74, no. 9, 1435-1448 (2013) · Zbl 1282.90138
[13] Paulavičius, R.; Žilinskas, J., Advantages of Simplicial Partitioning for Lipschitz Optimization Problems with Linear Constraints, Optim. Lett., 10, no. 2, 237-246 (2016) · Zbl 1342.90151
[14] Gladkov, LA; Kureichik, VV; Kureichik, VM, Geneticheskie algoritmy (Genetic Algorithms) (2004), Moscow: Fizmatlit, Moscow
[15] Karpenko, AP, Sovremennye algoritmy poiskovoi optimizatsii. Algoritmy, vdokhnovlennye prirodoi (Modern Algorithms of Search Optimization. Nature-Inspired Algorithms) (2014), Moscow: Mosk. Gos. Tekh. Univ, Moscow
[16] Kvasov, DE; Mukhametzhanov, MS, Metaheuristic vs. Deterministic Global Optimization Algorithms. The Univariate Case, Appl. Math. Comput., 318, 245-259 (2018) · Zbl 1426.90208
[17] Sergeyev, Y., Kvasov, D., and Mukhametzhanov, M.On the Efficiency of Nature-Inspired Metaheuristics in Expensive Global Optimization with Limited Budget, Sci. Rep., 2018, vol. 8 (1), article no. 435.
[18] Neimark, JuI; Strongin, RG, Function Extremum Search with the Use of Information Maximum Principle, Autom. Remote Control, 27, no. 1, 101-105 (1966) · Zbl 0156.38902
[19] Neimark, JuI; Strongin, RG, An Information Approach to the Function Extremum Search, Izv. Akad. Nauk SSSR, Tekh. Kibern., no. 1, 17-26 (1966)
[20] Strongin, RG, Multiextremal Minimization, Autom. Remote Control, 31, no. 7, 1085-1088 (1970) · Zbl 0209.51501
[21] Strongin, RG, Chislennye metody v mnogoekstremalanykh zadachakh (informatsionno-statisticheskie algoritmy) (Numerical Methods in Multiextremal Problems: Information-Statistical Algorithms) (1978), Moscow: Nauka, Moscow · Zbl 0458.65062
[22] Strongin, RG; Markin, DL, Minimization of Multiextremal Functions under Non-convex Constraints, Kibernetika, no. 4, 63-69 (1986)
[23] Markin, DL; Strongin, RG, A Method for Solving Multi-extremal Problems with Non-convex Constraints, That Uses a Priori Information about Estimates of the Optimum, USSR Comput. Math. Math. Phys., 27, no. 1, 33-39 (1987) · Zbl 0648.90075
[24] Markin, DL; Strongin, RG, Uniform Estimates for the Set of Weakly Effective Points in Multi-extremum Multicriterion Optimization Problems, Comput. Math. Math. Phys., 33, no. 2, 171-179 (1993) · Zbl 0788.90064
[25] Strongin, RG; Gergel, VP; Grishagin, VA; Barkalov, KA, Parallelanye vychisleniya v zadachakh globalanoi optimizatsii (Parallel Computations in Global Optimization Problems) (2013), Moscow: Mosk. Gos. Univ., Moscow
[26] Strongin, RG, Parallel Multiextremal Optimization Using a Set of Evolvents, USSR Comput. Math. Math. Phys., 31, no. 8, 37-46 (1991) · Zbl 0785.90080
[27] Strongin, RG; Sergeev, YaD, Global Optimization with Non-Convex Constraints. Sequential and Parallel Algorithms (2000), Dordrecht: Kluwer, Dordrecht · Zbl 0987.90068
[28] Grishagin, VA; Sergeyev, YD; Strongin, RG, Parallel Characteristical Algorithms for Solving Problems of Global Optimization, J. Glob. Optim., 10, no. 2, 185-206 (1997) · Zbl 0880.90123
[29] Sergeyev, Y.; Grishagin, V., Parallel Asynchronous Global Search and the Nested Optimization Scheme, J. Comput. Anal. Appl., 3, no. 2, 123-145 (2001) · Zbl 1033.90093
[30] Gergel, V.; Grishagin, V.; Gergel, A., Adaptive Nested Optimization Scheme for Multidimensional Global Search, J. Glob. Optim., 66, no. 1, 35-51 (2016) · Zbl 1355.90072
[31] Barkalov, K. and Gergel, V.Multilevel Scheme of Dimensionality Reduction for Parallel Global Search Algorithms, Proc. 1st Int. Conf. on Engineering and Applied Sciences Optimization (OPT-i 2014), 2014, pp. 2111-2124.
[32] Sergeyev, Y.; Grishagin, V., Parallel Asynchronous Global Search and the Nested Optimization Scheme, J. Comput. Anal. Appl., 3, no. 2, 123-145 (2001) · Zbl 1033.90093
[33] Gergel, V.; Grishagin, V.; Israfilov, R., Local Tuning in Nested Scheme of Global Optimization, Procedia Comput. Sci., 51, no. 1, 865-874 (2015)
[34] Barkalov, K.; Lebedev, I., Solving Multidimensional Global Optimization Problems Using Graphics Accelerators, CCIS, 687, 224-235 (2016)
[35] Grishagin, V., Israfilov, R., and Sergeyev, Y. Comparative Efficiency of Dimensionality Reduction Schemes in Global Optimization, AIP Conf. Proc., 2016, vol. 1776, article no. 060011. · Zbl 1426.90204
[36] Grishagin, V.; Israfiov, R.; Sergeyev, Y., Convergence Conditions and Numerical Comparison of Global Optimization Methods Based on Dimensionality Reduction Schemes, Appl. Math. Comput., 318, 270-280 (2018) · Zbl 1426.90204
[37] Gergel, V.; Grishagin, V.; Israfilov, R., Parallel Dimensionality Reduction for Multiextremal Optimization Problems, in Lecture Notes on Computer Science, vol. 11657, 166-178 (2019), Berlin: Springer, Berlin
[38] Gaviano, M.; Lera, D.; Kvasov, DE; Sergeyev, YaD, Software for Generation of Classes of Test Functions with Known Local and Global Minima for Global Optimization, ACM Trans. Math. Software, 29, 469-480 (2003) · Zbl 1068.90600
[39] Sovrasov, V., Comparison of Several Stochastic and Deterministic Derivative-Free Global Optimization Algorithms, in Lecture Notes on Computer Science, 70-81 (2019), Berlin: Springer, Berlin · Zbl 1443.90285
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.