Economical dichotomous search for minimizing one-variable functions

Abstract

EN: Context. The hypothesis about computational redundancy of the dichotomy method used for conditional minimization of unimodal functions was formulated, and on this basis the idea of the possibility creating a more efficient method was suggested. Objective. The aim of the work is to develop a technique for eliminating computational redundancy of the dichotomy method and the creation numerical method of increased speed called the economical dichotomy method. The algorithm and program code implementing the method are also subjected to development. Method. The method is based on the unimodality property of the function being minimized, which, under certain conditions, allows to reduce the number of calculations of the function being optimized, which helps to increase the speed of the economical search. Results. The given results of the computational experiment showed that, according to speed, determined by the number of calculations of the minimized function, the economical method is not less than 1.5 times more efficient than the classical dichotomous search. This means that, on average, of the three calculations of the minimized function using the dichotomy method, one is redundant. Compared with the golden section search, which is the fastest method of the cut-off family, and the dichotomous search, in the average statistical terms, the economical method has approximately 1.3 and 1.7 times faster response, respectively. That is, the economical method works so many times faster than the golden section search, how many times the latter works faster than the classical dichotomous search. Conclusions. These findings make it possible to take a critical look at the well-established notion that the dichotomous search is the worst of the series methods for cutting off segments. Taking into account the obtained results, the economical method of dichotomy is noticeably superior in speed to the best of them – the golden section search and can reasonably claim to be a leader in this series of methods. UK: Актуальність. Висунута ідея усунення обчислювальної надмірності методу дихотомії, використовуваного для умовної мінімізації унімодальних функцій, та на її основі сформульовано похід до створення більш ефективного методу оптимізації функцій однієї змінної. Метою даної роботи є розробка методики усунення обчислювальної надмірності методу дихотомії і створення чисельного методу підвищеної швидкодії, названого методом економної дихотомії. Розробці підлягають алгоритм і програмний код, що реалізують метод. Метод. В основі методу лежить властивість унімодальне мінімізується, яке за певних умов дозволяє скоротити кількість обчислень оптимізується функції, що дозволяє підвищити швидкість економічного пошуку методом дихотомії. Результати. Наведені результати обчислювального експерименту показали, що за швидкодією, що визначається кількістю обчислень функції, що мінімізується, економічний метод не менш ніж в 1,5 рази ефективніше класичного методу дихотомії. Це означає, що в середньому з трьох обчислень мінімізованої функції з використанням методу дихотомії один є надмірною. У порівнянні з пошуком по методу золотого перетину, який є найшвидшим методом в сімействі методів відсікання відрізків, і методом дихотомії в середньостатистичному щодо економний метод дає приблизно в 1,3 і 1,7 рази швидший пошук, відповідно. Висновки. Отримані результати дозволяють висновок про те, що запропонований економний метод дихотомії може обгрунтовано претендувати на лідерство в сімействі методів відділення відрізків.