Systems and Means of Informatics
2019, Volume 29, Issue 1, pp 164173
ON COMPUTATIONAL REDUNDANCY OF THE DICHOTOMOUS SEARCH AND CONDITIONAL MINIMIZATION OF UNIMODAL FUNCTIONS BY THE ECONOMICAL DICHOTOMOUS SEARCH
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)
 Wilde, D. J. 1964. Optimum seeking methods. Englewood Cliffs, NJ: Prentice Hall, Inc. 423 p.
 Attetkov, A. V., S. V. Galkin, and V. S. Zarubin. 2003. Metody optimizatsii [Optimization methods]. Moscow: Bauman Moscow State Technical University. 139 p.
 Panteleev, A. V., andT. A. Letova. 2005. Metody optimizatsii v primerakh i zadachakh [Optimization methods in examples and problems]. Moscow: Vysshaya shkola. 245 p.
 Izmailov, A. F., and M. V. Solodov. 2005. Chislennye metody optimizatsii [Numerical optimization methods]. Moscow: Fizmatlit. 156 p.
 Abbasov, M. E. 2014. Metody optimizatsii [Optimizationmethods]. SaintPetersburg: VVM. 263 p.
 Kiefer, J.K. 1953. Sequential minimax search for a maximum. P. Am. Math. Soc. 4:502506.
 Aoki, M. 1971. Introduction to optimization techniques, fundamentals and applications of nonlinear programming. Macmillan ser. in applied computer sciences. New York, NY: The Macmillan Co. 344 p.
 Pshenichny, B.N., and Y. M. Danilin. 1975. Chislennye metody v ekstremal'nykh zadachakh [Numerical methods in extremal problems]. Moscow: Nauka. 278 p.
 Moiseev, N.N., Yu. P. Ivanilov, and E. M. Stolyarova. 1978. Metody optimizatsii [Methods of optimization]. Moscow: Nauka. 276 p.
 Rao, S. S. 2009. Engineering optimization: Theory and practice. 4th ed. Hoboken, NJ: John Wiley & Sons. 320 p.
 Zhadan, V. G. 2015. Metody optimizatsii. Ch. 2. Chislennye algoritmy [Optimization methods. Part 2: Numerical algorithms]. Moscow: MIPT. 320 p.
 Kodnyanko, V.A. 2018. Metod ekonomnoy dikhotomii [Economical dichotomous search]. Krasnoyarsk: Siberian Federal University. 13p. Availableat: http://smiuk.sfu kras.ru/kodnyanko/site/ (accessed February 21, 2019).
[+] About this article
Title
ON COMPUTATIONAL REDUNDANCY OF THE DICHOTOMOUS SEARCH AND CONDITIONAL MINIMIZATION OF UNIMODAL FUNCTIONS BY THE ECONOMICAL DICHOTOMOUS SEARCH
Journal
Systems and Means of Informatics
Volume 29, Issue 1, pp 164173
Cover Date
20190330
DOI
10.14357/08696527190113
Print ISSN
08696527
Publisher
Institute of Informatics Problems, Russian Academy of Sciences
Additional Links
Key words
unimodal function; dichotomous search; golden section search; Fibonacci number method; economical dichotomous search; monotone function; method speed
Authors
V. A. Kodnyanko
Author Affiliations
Polytechnical Institute, Siberian Federal University, 26 Kirensky Str., Krasnoyarsk 660074, Russian Federation
