Systems and Means of Informatics

2019, Volume 29, Issue 1, pp 164-173

ON COMPUTATIONAL REDUNDANCY OF THE DICHOTOMOUS SEARCH AND CONDITIONAL MINIMIZATION OF UNIMODAL FUNCTIONS BY THE ECONOMICAL DICHOTOMOUS SEARCH

  • V. A. Kodnyanko

Abstract

The hypothesis about the computational redundancy of the well- known dichotomous search, applied along with other known numerical methods, in particular, the golden section search, for the conditional minimization of unimodal functions, is discussed. The technique for eliminating the computational redundancy of the method is formulated and on its basis, a method for minimizing such functions, called the economical dichotomous search, is developed. The author developed the algorithms and code that implement the method in Delphi.
The results of a computational experiment are described. They show that the economical method is about 1.5 times more efficient than the classical dichotomous search by a speed determined by the number of calculations of the minimized function. It means that, on average, in three calculations of the function being minimized by dichotomous search, one is redundant. In comparison with the golden section search and the dichotomous search in the average statistical plan, the method is approximately 1.3 and 1.7 times faster, respectively. In other words, the method works as many times faster than the method of the golden section search, as the latter works faster than the classical dichotomous search. This conclusion allows us to take a critical view of the established notion that the dichotomous search is the worst method of cutting off segments. Taking into account the obtained results, the dichotomous search significantly exceeds the speed of the best of them - the golden section search and can reasonably claim to have the leading position in this family of methods.

[+] References (12)

[+] About this article