Continuous global optimization of multivariable functions based on Sergeev and Kvasov diagonal approach

V. I. Zabotin ; P. A. Chernyshevsky

Žurnal Srednevolžskogo matematičeskogo obŝestva, Tome 24 (2022) no. 4, pp. 399-418.

Résumé

One of modern global optimization algorithms is method of Strongin and Piyavskii modified by Sergeev and Kvasov diagonal approach. In recent paper we propose an extension of this approach to continuous multivariable functions defined on the multidimensional parallelepiped. It is known that Sergeev and Kvasov method applies only to a Lipschitz continuous function though it effectively extends one-dimensional algorithm to multidimensional case. So authors modify We modify mentioned method to a continuous functions using introduced by Vanderbei $\varepsilon$-Lipschitz property that generalizes conventional Lipschitz inequality. Vanderbei proved that a real valued function is uniformly continuous on a convex domain if and only if it is $\varepsilon$-Lipschitz. Because multidimensional parallelepiped is a convex compact set, we demand objective function to be only continuous on a search domain. We describe extended Strongin’s and Piyavskii’s methods in the Sergeev and Kvasov modification and prove the sufficient conditions for the convergence. As an example of proposed method’s application, at the end of this article we show numerical optimization results of different continuous but not Lipschitz functions using three known partition strategies: “partition on 2”, “partition on 2N” and “effective”. For the first two of them we present formulas for computing a new iteration point and for recalculating the $\varepsilon$-Lipschitz constant estimate. We also show algorithm modification that allows to find a new search point on any algorithm's step.

Détail

Keywords: global optimization, non-Lipschitz optimization, nonconvex optimization, $\varepsilon $-Lipschitz function, continuous function
Mots-clés : convergence.

Bibliographie

[1] S. A. Piyavskii, “Odin algoritm otyskaniya absolyutnogo minimuma funktsii”, Teoriya optimalnykh reshenii, 2 (1967), 13–24 | MR

[2] S. A. Piyavskii, “Odin algoritm otyskaniya absolyutnogo ekstremuma funktsii”, Zh. vychisl. matem. i matem. fiz., 12:4 (1972), 57–67 | MR

[3] Yu. G. Evtushenko, “Chislennyi metod poiska globalnogo ekstremuma funktsii (perebor na neravnomernoi setke)”, Zh. vychisl. matem. i matem. fiz., 11:6 (1971), 38–54

[4] B. Shubert, “A sequential method seeking the global maximum of a function”, SIAM J. Numer. Anal., 9:3 (1972), 379–388 | DOI | MR

[5] R. G. Strongin, Chislennye metody v mnogoekstremalnykh zadachakh, Nauka, Moskva, 1978, 240 pp.

[6] Ya.D. Sergeev , D.E. Kvasov, Diagonalnye metody globalnoi optimizatsii, FIZMATLIT, M., 2008, 352 pp.

[7] B. Gelbaum,Dzh. Olmsted, Kontrprimery v analize, Mir, M., 1962, 224 pp.

[8] R. J. Vanderbei, “Extension of Piyavskii’s algorithm to continuous global optimization”, Journal of Global Optimization, 14 (1999), 205–216 | DOI | MR

[9] S. Romaguera, M. Sanchis, “Semi-Lipschitz functions and best approximation in quasi-metric space”, J. Approx. Theory., 103:2 (2000), 292–301 | DOI | MR

[10] E. Jouini, “Generalized Lipschitz functions”, Nonlinear Anal., 41 (2000), 371–382 | DOI | MR

[11] M.A. Sadygov, “Zadachi na ekstremum c ogranicheniyami v metricheskom prostranstve”, DAN, 52:5 (2013), 490–493

[12] Y. D. Sergeyev, A. Candelieri, D. E. Kvasov, R. Perego, “Safe global optimization of expensive noisy black-box functions in the $\delta $-Lipschitz framework”, Soft. Comput., 24 (2020), 17715–17735 | DOI

[13] V.I. Zabotin, P.A. Chernyshevskii, “Dve modifikatsii obobschennogo metoda Piyavskogo poiska globalnogo minimuma nepreryvnoi na otrezke funktsii i ikh skhodimost”, Vestnik Tverskogo gosudarstvennogo universiteta. Seriya: Prikladnaya matematika, 3 (2021), 70–85

[14] N. K. Arutyunova, “Metod Evtushenko poiska globalnogo minimuma $\varepsilon $-lipshitsevoi funktsii i ego prilozheniya”, Vestnik KGTU im. A.N. Tupoleva, 2 (2013), 154–157

[15] N. K. Arutyunova, A. M. Dulliev, V. I. Zabotin, “Models and methods for three external ballistics inverse problems”, Vestnik yuzhno-uralskogo gosudarstvennogo universiteta. Seriya: matematicheskoe modelirovanie i programmirovanie, 10:4 (2017), 78–91

[16] V. I. Zabotin, P. A. Chernyshevskij, “Extension of Strongin’s global optimization algorithm to a function continuous on a compact interval”, Computer Research and Modeling, 11:6 (2019), 1111–1119 | DOI

[17] N. K. Arutyunova, A. M. Dulliev, V. I. Zabotin, “Global optimization of multivariable functions satisfying the Vanderbei condition”, J. Appl. Math. Comput., 68:3 (2022), 1135–1161 | DOI | MR

[18] V.I. Zabotin, P.A. Chernyshevskii, “Algoritm vychisleniya minimalnoi otsenki $\varepsilon $-postoyannoi Lipshitsa nepreryvnoi funktsii”, Vestnik KGTU im. A.N. Tupoleva, 2 (2018), 127–132

[19] Y. D. Sergeyev, “Efficient strategy for adaptive partition of N-dimensional intervals in the framework of diagonal algorithms”, Journal of Optimization Theory and Applications, 107 (2000), 145–168 | DOI | MR