×

zbMATH — the first resource for mathematics

Deterministic global optimization using space-filling curves and multiple estimates of Lipschitz and Hölder constants. (English) Zbl 1356.90112
Summary: In this paper, the global optimization problem \(\min_{y\in S}F(y)\) with \(S\) being a hyperinterval in \(\mathbb R^N\) and \(F(y)\) satisfying the Lipschitz condition with an unknown Lipschitz constant is considered. It is supposed that the function \(F(y)\) can be multiextremal, non-differentiable, and given as a ‘black-box’. To attack the problem, a new global optimization algorithm based on the following two ideas is proposed and studied both theoretically and numerically. First, the new algorithm uses numerical approximations to space-filling curves to reduce the original Lipschitz multi-dimensional problem to a univariate one satisfying the Hölder condition. Second, the algorithm at each iteration applies a new geometric technique working with a number of possible Hölder constants chosen from a set of values varying from zero to infinity showing so that ideas introduced in a popular DIRECT method can be used in the Hölder global optimization. Convergence conditions of the resulting deterministic global optimization method are established. Numerical experiments carried out on several hundreds of test functions show quite a promising performance of the new algorithm in comparison with its direct competitors.

MSC:
90C26 Nonconvex programming, global optimization
Software:
Algorithm 829
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Butz, A. R., Space filling curves and mathematical programming, Inf Control, 12, 4, 313-330, (1968) · Zbl 0187.12702
[2] Calvin, J.; Žilinskas, A., One-dimensional P-algorithm with convergence rate \(O(n^{- 3 + \delta})\) for smooth functions, J Optim Theory Appl, 106, 2, 297-307, (2000) · Zbl 0992.90053
[3] Casado, L. G.; García, I.; Sergeyev, Ya. D., Interval algorithms for finding the minimal root in a set of multiextremal non-differentiable one-dimensional functions, SIAM J Sci Comput, 24, 2, 359-376, (2002) · Zbl 1014.65054
[4] Evtushenko, Yu. G.; Posypkin, M., A deterministic approach to global box-constrained optimization, Optim Lett, 7, 4, 819-829, (2013) · Zbl 1269.90082
[5] Famularo, D.; Pugliese, P.; Sergeyev, Ya. D., A global optimization technique for checking parametric robustness, Automatica, 35, 1605-1611, (1999) · Zbl 0948.93505
[6] Gablonsky MJ. DIRECT v2.04 FORTRAN code with documentation, 2001, http://www4.ncsu.edu/ctk/SOFTWARE/DIRECTv204.tar.gz.
[7] Gablonsky MJ. Modifications of the DIRECT Algorithm [Ph.D thesis]. Raleigh: North Carolina State University; NC, 2001.
[8] Gablonsky, M. J.; Kelley, C. T., A locally-biased form of the DIRECT algorithm, J Global Optim, 21, 27-37, (2001) · Zbl 1039.90049
[9] Gaviano, M.; Kvasov, D. E.; Lera, D.; Sergeyev, Ya. D., Software for generation of classes of test functions with known local and global minima for global optimization, ACM TOMS, 29, 4, 469-480, (2003) · Zbl 1068.90600
[10] Horst, R.; Pardalos, P. M., Handbook of global optimization, (1995), Kluwer Doordrecht · Zbl 0805.00009
[11] Horst, R.; Tuy, H., Global optimization: deterministic approaches, (1996), Springer Berlin · Zbl 0867.90105
[12] Gourdin, E.; Jaumard, B.; Ellaia, R., Global optimization of Hölder functions, J Global Optim, 8, 323-348, (1996) · Zbl 0848.90110
[13] Gergel, V. P.; Sergeyev, Ya. D., Sequential and parallel global optimization algorithms using derivatives, Comput Math Appl, 37, 4-5, 163-180, (1999) · Zbl 0931.90049
[14] Grishagin, V. A., Operating characteristics of some global search algorithms, (Problems of Stochastic Search, 7, (1978), Zinatne Riga), 198-206, (in Russian) · Zbl 0442.90087
[15] Jones, D. R.; Perttunen, C. D.; Stuckman, B. E., Lipschitzian optimization without the Lipschitz constant, J Optim Theory Appl, 79, 157-181, (1993) · Zbl 0796.49032
[16] Kvasov, D. E.; Pizzuti, C.; Sergeyev, Ya. D., Local tuning and partition strategies for diagonal GO methods, Numer Math, 94, 1, 93-106, (2003) · Zbl 1056.65059
[17] Kvasov, D. E.; Sergeyev, Ya. D., A univariate global search working with a set of Lipschitz constants for the first derivative, Optim Lett, 3, 303-318, (2009) · Zbl 1173.90544
[18] Kvasov, D. E.; Sergeyev, Ya. D., Lipschitz gradients for global optimization in a one-point-based partitioning scheme, J Comput Appl Math, 236, 16, 4042-4054, (2012) · Zbl 1246.65091
[19] Kvasov, D. E.; Sergeyev, Ya. D., Lipschitz global optimization methods in control problems, Autom Remote Control, 74, 9, 1435-1448, (2013) · Zbl 1282.90138
[20] Sergeyev, Ya. D.; Kvasov, D. E., A deterministic global optimization using smooth diagonal auxiliary functions, Comm Nonlinear Sci Numer Simulat, 21, 1, 99-111, (2015) · Zbl 1329.90112
[21] Lera, D.; Sergeyev, Ya. D., Global minimization algorithms for Hölder functions, BIT, 42, 1, 119-133, (2002) · Zbl 1003.65064
[22] Lera, D.; Sergeyev, Ya. D., An information global minimization algorithm using the local improvement technique, J Global Optim, 48, 99-112, (2010) · Zbl 1202.90216
[23] Lera, D.; Sergeyev, Ya. D., Lipschitz and Hölder global optimization using space-filling curves, Appl Numer Math, 60, 115-129, (2010) · Zbl 1201.65101
[24] Lera, D.; Sergeyev, Ya. 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
[25] Martínez, J. A.; Casado, L. G.; García, I.; Sergeyev, Ya. D.; Toth, B., On an efficient use of gradient information for accelerating interval global optimization algorithms, Numer Algorithms, 37, 61-69, (2004) · Zbl 1078.65053
[26] Paulavičius, R.; Sergeyev, Ya. D.; Kvasov, D. E.; Žilinskas, J., Globally-biased disimpl algorithm for expensive global optimization, J Global Optim, 59, 2-3, 545-567, (2014) · Zbl 1297.90130
[27] Paulavičius, R.; Žilinskas, J., Simplicial global optimization, (2014), Springer New York · Zbl 1401.90017
[28] Pintér, J. D., Global optimization in action, (1996), Kluwer Dordrecht
[29] Piyavskii, S. A., An algorithm for finding the absolute extremum of a function, USSR Comput Math Math Phys, 12, 57-67, (1972) · Zbl 0249.65046
[30] Preparata, F. P.; Shamos, M. I., Computational geometry: an introduction, (1993), Springer-Verlag New York
[31] Sagan, H., Space-filling curves, (1994), Springer New York · Zbl 0806.01019
[32] Sergeyev, Ya. D., An information global optimization algorithm with local tuning, SIAM J Optim, 5, 858-870, (1995) · Zbl 0847.90128
[33] Sergeyev, Ya. D., On convergence of divide the best global optimization algorithms, Optimization, 44, 3, 303-325, (1998) · Zbl 0986.90058
[34] Sergeyev, Ya. D., Global one-dimensional optimization using smooth auxiliary functions, Math Program, 81, 1, 127-146, (1998) · Zbl 0920.90133
[35] Sergeyev, Ya. D.; Daponte, P.; Grimaldi, D.; Molinaro, A., Two methods for solving optimization problems arising in electronic measurements and electrical engineering, SIAM J Optim, 10, 1, 1-21, (1999) · Zbl 0953.90054
[36] Sergeyev, Ya. D.; Kvasov, D. E., Global search based on efficient diagonal partitions and a set of Lipschitz constants, SIAM J Optim, 16, 3, 910-937, (2006) · Zbl 1097.65068
[37] Sergeyev, Ya. D.; Kvasov, D. E., Diagonal global optimization methods, (2008), Fizmatlit Moscow, (in Russian) · Zbl 1282.90138
[38] Sergeyev, Ya. D.; Strongin, R. G.; Lera, D., Introduction to global optimization exploiting space-filling curves, (2013), Springer New York · Zbl 1278.90005
[39] Strongin, R. G., Numerical methods in multiextremal problems: information-statistical algorithms, (1978), Nauka Moscow, (In Russian) · Zbl 0458.65062
[40] Strongin, R. G.; Sergeyev, Ya. D., Global optimization with non-convex constraints: sequential and parallel algorithms, (2000), Kluwer Dordrecht · Zbl 0987.90068
[41] Strongin, R. G.; Sergeyev, Ya. D., Global optimization: fractal approach and non-redundant parallelism, J Global Optim, 27, 1, 25-50, (2003) · Zbl 1035.90086
[42] Zhigljavsky, A. A.; Žilinskas, A., Stochastic global optimization, (2008), Springer New York · Zbl 1136.90003
[43] Žilinskas, A., On similarities between two models of global optimization: statistical models and radial basis functions, J Global Optim, 48, 1, 173-182, (2010) · Zbl 1202.90210
[44] Žilinskas, A.; Žilinskas, J., Interval arithmetic based optimization in nonlinear regression, Informatica, 21, 1, 149-158, (2010) · Zbl 1205.90227
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.