Two modifications of extension of Piyavskii's global optimization algorithm to a function continuous on a compact interval and its convergence

V. I. Zabotin   ; P. A. Chernyshevsky

Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika, no. 3 (2021), pp. 70-85

Résumé

R.J. Vanderbei in his works proves that any continuous on a compact set function has the $\varepsilon $-Lipschitz property which extends conventional Lipschitz continuity. Based on this feature Vanderbei proposed one extension of Piyavskii’s global optimization algorithm to the continuous function case. In this paper we propose one modification of the Vanderbei’s algorithm for a positive $\varepsilon $-constant and another modification for a positive $\varepsilon $-constant and $\varepsilon $ value independent termination condition. We prove proposed methods convergence and perform several computational experiments with designed software for known test functions.

Détail

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

Bibliographie

[1] Piyavskij S. A., “An algorithm for finding the absolute minimum of a function”, Theory of Optimal Solutions, 2 (1967), 13–24 (in Russian) | MR

[2] Piyavskij S. A., “An algorithm for finding the absolute extremum of a function”, USSR Computational Mathematics and Mathematical Physics, 12:4 (1972), 57–67 | DOI | MR

[3] Yevtushenko Yu. G., “Numerical methods for finding global extrema (Case of a non-uniform mesh)”, USSR Computational Mathematics and Mathematical Physics, 11:6 (1971), 38–54 | DOI | Zbl

[4] Shubert B., “A sequential method seeking the global maximum of a function”, SIAM Journal on Numerical Analysis, 9 (1972), 379–388 | DOI | MR | Zbl

[5] Strongin R. G., Numerical methods in multiextremal problems, Nauka Publ., Moscow, 1978, 240 pp. (in Russian)

[6] Sergeev Ya. D., Kvasov D. E., Diagonal methods of global optimization, Fizmatlit Publ., Moscow, 2008, 352 pp. (in Russian)

[7] Zabotin V. I., Arutyunova N. K., “Two algorithms for finding point projection on nonconvex set in normalized space”, Journal of Computational Mathematics and Mathematical Physics, 53:3 (2013), 344–349 (in Russian) | Zbl

[8] Arutyunova N. K., Dulliev A. M., Zabotin V. I., “Algorithms for projecting a point onto a level surface of a continuous function on a compact set”, Computational Mathematics and Mathematical Physics, 54:9 (2014), 1395–1401 | DOI | MR | Zbl

[9] Chernyaev Yu. A., “Numerical algorithm for solving mathematical programming problems with a smooth surface as a constraint”, Computational Mathematics and Mathematical Physics, 56:3 (2016), 376–381 | DOI | MR | Zbl

[10] Chernyaev Yu. A., “On a numerical algorithm for optimization problems with preconvex constraints”, Computational Mathematics and Mathematical Physics, 43:2 (2003), 162–167 | MR | Zbl

[11] Chernyaev Yu. A., “An extension of the gradient projection method and Newton's method to extremum problems constrained by a smooth surface”, Computational Mathematics and Mathematical Physics, 55:9 (2015), 1451–1460 | DOI | MR | Zbl

[12] Gelbaum B., Olmsted Dzh., Counterexamples in analysis, Mir Publ., Moscow, 1967, 251 pp. (in Russian)

[13] Vanderbei R. J., “Extension of Piyavskii's Algorithm to Continuous Global Optimization”, Journal of Global Optimization, 14 (1999), 205–216 | DOI | Zbl

[14] Arutyunova N. K., “Yevtushenko's method for finding $\varepsilon $-Lipschitzian function global minimum and its application”, Herald of the KSTU-KAI Named After A.N. Tupolev, 2013, no. 2, 154–157 (in Russian)

[15] Arutyunova N. K., Dulliev A. M., Zabotin V. I., “Models and methods for three external ballistics inverse problems”, Bulletin of the South Ural State University: Series “Mathematical modelling, Programming and Computer software”, 10:4 (2017), 78–91 | Zbl

[16] Zabotin V. I., Chernyshevskij P. A., “An algorithm for calculation the minimal estimate of the continuous function Lipschitz $\varepsilon $-constant”, Herald of the KSTU-KAI Named After A.N. Tupolev, 2018, no. 2, 127–132 (in Russian)

[17] Zabotin V. I., Chernyshevskij P. A., “Extension of Strongin’s Global Optimization Algorithm to a Function Continuous on a Compact Interval”, Computer Research and Modeling, 11 (2019), 1111–1119 | DOI

[18] Vasilev F. P., Chislennye metody resheniya ekstremalnykh zadach, Ucheb. posobie dlya vuzov, 2-e izd., pererab. i dop., Nauka Publ., Moscow, 1988, 552 pp. (in Russian)