Combined Newton’s third-order convergence method for minimize one variable functions

Abstract

EN: Contex. The article deals with the actual problem of numerical optimization of slowly computed unimodal functions of one variable. The analysis of existing methods of minimization of the first and second orders of convergence, which showed that these methods can be used to quickly solve these problems for functions, the values of which can be obtained without difficulty. For slowly computed functions, these methods give slow algorithms; therefore, the problem of developing fast methods for minimizing such functions is urgent. Objective. Development of a combined third-order Newtonian method of convergence to minimize predominantly slowly computed unimodal functions, as well as the development of a database, including smooth, monotonic and partially constant functions, to test the method and compare its effectiveness with other known methods. Method. A technique and an algorithm for solving the problem of fast minimization of a unimodal function of one variable by a combined numerical Newtonian method of the third order of convergence presented. The method is capable of recognizing strictly unimodal, monotonic and constant functions, as well as functions with partial or complete sections of a flat minimum. Results. The results of comparison of the proposed method with other methods, including the fast Brent method, presented. 6954 problems were solved using the combined Newtonian method, while the method turned out to be faster than other methods in 95.5% of problems, Brent’s method worked faster in only 4.5% of problems. In general, the analysis of the calculation results showed that the combined method worked 1.64 times faster than the Brent method. Conclusions. A combined third-order Newtonian method of convergence proposed for minimizing predominantly slowly computed unimodal functions of one variable. A database of problems developed, including smooth, monotone and partially constant functions, to test the method and compare its effectiveness with other known methods. It is shown that the proposed method, in comparison with other methods, including the fast Brent method, has a higher performance. UK: Актуальність. У статті розглядається актуальна проблема чисельної оптимізації повільно обчислюваних унімодальних функцій однієї змінної. Проведено аналіз існуючих методів мінімізації першого і другого порядку збіжності, який показав, що ці методи можуть бути використані для швидкого вирішення цих завдань для функцій, значення яких можуть бути отримані без труднощів. Для повільно обчислюваних функцій ці методи дають повільні алгоритми, тому актуальною є задача розробки швидких методів для мінімізації таких функцій. Мета. Розробка комбінованого ньютоновского методу третього порядку збіжності для мінімізації переважно повільно обчислюваних унімодальних функцій, а також розробка бази даних, що включає гладкі, монотонні і частково постійні функції, для перевірки методу і порівняння його ефективності з іншими відомими методами. Метод. Викладається методика і алгоритм вирішення завдання швидкої мінімізації унімодальної функції однієї змінної комбінованим чисельним ньютоновским методом третього порядку збіжності. Метод здатний розпізнавати строго унімодальне, монотонні і постійні функції, а також функції з частковими або повними ділянками плоского мінімуму. Результати. Наводяться результати порівняння запропонованого методу з іншими методами, в тому числі швидким методом Брента. За допомогою комбінованого ньютоновского методу вирішено 6954 завдання, при цьому метод виявився швидше за інших методів в 95,5% завдань, метод Брента працював швидше лише в 4,5% завдань.В цілому аналіз результатів розрахунку показав, що комбінований метод працював в 1,64 рази швидше, ніж метод Брента. Висновки. Запропоновано комбінований ньютоновский метод третього порядку збіжності для мінімізації переважно повільно обчислюваних унімодальних функцій однієї змінної. Розроблено базу даних завдань, включаючи гладкі, монотонні і частково постійні функції, для перевірки методу і порівняння його ефективності з іншими відомими методами. Показано, що запропонований метод в порівнянні з іншими методами, включаючи швидкий метод Брента, має більш високу швидкодію.