# ECONOMICAL DICHOTOMOUS SEARCH FOR MINIMIZING ONE-VARIABLE FUNCTIONS

## Authors

• V. A. Kodnyanko Polytechnic Institute, Siberian Federal University, Krasnoyarsk, Russian Federation

## Keywords:

Unimodal function, dichotomous search, golden section search, economical dichotomous search, monotone function, method speed

## Abstract

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.

## Author Biography

### V. A. Kodnyanko, Polytechnic Institute, Siberian Federal University, Krasnoyarsk

Dr. Sc., Professor

## References

Kiefer J. K. Sequential minimax search for a maximum, Proceedings of the American Mathematical Society, 1953, Vol. 4, No. 3, pp. 502–506.

Rao S. S. Engineering optimization: theory and practice. 4th ed. Hoboken (New Jersey), John Wiley & Sons, 2009, 320 p.

Wilde D. J. Optimum Seeking Methods. New Jersey, Prentice Hall, 1964, 196 p.

Panteleev A. V., Letova T. A.. Metody optimizacii v primerah i zadachah. Moscow, Vysshaya shkola, 2005, 544 p.

Attetkov A. V., Galkin S. V., Zarubin B. C. Metody optimizacii, 2-e izd. stereotip. Moscow, MGTU im. N. E. Baumana, 2003, 139 p.

Izmajlov A. F., Solodov M. V. CHislennye metody optimizacii. Moscow, Fizmatlit, 2005, 156 p.

Abbasov M. E. Metody optimizacii. Sankt-Peterburg, VVM, 2014, 263 p.

Pshenichnyj B. N., Danilin YU. M. CHislennye metody v ekstremal'nyh zadachah. Moscow, Nauka, 1975, 278 p.

Moiseev N. N., Ivanilov YU. P., Stolyarova Е. M. Metody optimizacii. Moscow, Nauka, 1978, 245 p.

Aoki M. Introduction to optimization techniques:Fundamentals and Applications of Nonlinear Programming. London, Macmillan, 1971, 335 p.

ZHadan V. G. Metody optimizacii. Moscow, MFTI, 2015, CH. 2: CHislennye algoritmy, 320 p.

Hassin R., Reuven H. Asymptotic analysis of dichotomous search with search and travel costs, European Journal of Operational Research, 1992, Vol. 58(1), pp. 78–89.

Fletcher R. Practical Methods of Optimization, 2nd ed. Chichester, Wiley, 1987, pp. 78–89.

Gill P. E., Murray W., Wright M. H. Practical Optimization. London, Academic Press, 1981, 509 p.

Himmelblau, D. M. Applied Nonlinear Programming. New York, McGraw-Hill, 1972, 310 p.

Suharev A. G., Timohov A. V., Fedorov V. V. Kurs metodov optimizacii : ucheb. posobie, 2-e izd. Moscow, Fizmatlit, 2005. – 368 p.

Gottfried B. S., Weisman J. Weisman, Introduction to Optimization Theory. New Jersey, Prentice-Hall, 1973, 372 p.

Adbyand P. R., Dempster M. A. H.. Introduction to Optimization Methods. London, Chapman and Hall, 1974, 423 p.

Beightler C. S., Phillips D. T., Wilde D. J. Foundations of Optimization. New Jersey, Prentice-Hall, 1979, 584 p.

Bazaraa M. S., Shetty C. M. Nonlinear Programming, Theory and Algorithms. New York, Wiley, 1979, 406 p.

Vasil’ev, F. P. Metody optimizacii. Moscow, Faktorial Press, 2002, 824 p.

Еvtushenko YU. G. Metody resheniya ekstremal'nyh zadach i ih primenenie v sistemah optimizacii. Moscow, Nauka, 1982, 521 p.

Box M. J., Davies D., Swann W. H. Nonlinear Optimization Techniques. London, Oliver and Boyd, 1969, 416 p.

2019-10-01

## How to Cite

Kodnyanko, V. A. (2019). ECONOMICAL DICHOTOMOUS SEARCH FOR MINIMIZING ONE-VARIABLE FUNCTIONS. Radio Electronics, Computer Science, Control, (3), 34–39. https://doi.org/10.15588/1607-3274-2019-3-4

## Section

Mathematical and computer modelling