ECONOMICAL DICHOTOMOUS SEARCH FOR MINIMIZING ONE-VARIABLE FUNCTIONS
DOI:
https://doi.org/10.15588/1607-3274-2019-3-4Keywords:
Unimodal function, dichotomous search, golden section search, economical dichotomous search, monotone function, method speedAbstract
Context. The hypothesis about computational redundancy of the dichotomy method used for conditional minimization ofunimodal 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.
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.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2019 V. A. Kodnyanko
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Creative Commons Licensing Notifications in the Copyright Notices
The journal allows the authors to hold the copyright without restrictions and to retain publishing rights without restrictions.
The journal allows readers to read, download, copy, distribute, print, search, or link to the full texts of its articles.
The journal allows to reuse and remixing of its content, in accordance with a Creative Commons license СС BY -SA.
Authors who publish with this journal agree to the following terms:
-
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License CC BY-SA that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
-
Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
-
Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
