Binary scan search (biscan) for conditional minimization of weakly uniomodal functions
Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika, Tome 7 (2018) no. 4, pp. 59-66
Cet article a éte moissonné depuis la source Math-Net.Ru
A method of binary scan search (biscan) is proposed for conditional minimization of weakly unimodal functions. The application area of this method is the optimization of piecewise, stepwise, relay and other weakly unimodal functions, the extremum of which can be localized, both in narrow and extended regions, including the regions of constancy of the minimized function. The algorithm implementing the method is represented by two procedures, the block diagrams of which are given in the article. To evaluate the performance of the biscan, a comparative computational experiment was carried out using examples of minimizing a number of weakly unimodal functions. It is established that, in comparison with competing methods, the biscan gives better performance. The fastest method is provided by minimizing non-constant monotonic functions. To determine the extremum, only five calculations of such a function are required. In comparison with the golden section search, the biscain has a 1.5 times greater speed in solving problems of this type. In minimizing strictly weakly unimodal functions, to which the known methods of minimizing unimodal functions are not applicable, in particular, the golden section search, the biscan operates orders of magnitude faster than the competing sequential search method.
Keywords:
binary scanning, biscan, golden section search, direct search method, unimodal function, weakly unimodal function, minimization of function, method speed.
@article{VYURV_2018_7_4_a3,
author = {V. A. Kodnyanko},
title = {Binary scan search (biscan) for conditional minimization of weakly uniomodal functions},
journal = {Vestnik \^U\v{z}no-Uralʹskogo gosudarstvennogo universiteta. Seri\^a Vy\v{c}islitelʹna\^a matematika i informatika},
pages = {59--66},
year = {2018},
volume = {7},
number = {4},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/VYURV_2018_7_4_a3/}
}
TY - JOUR AU - V. A. Kodnyanko TI - Binary scan search (biscan) for conditional minimization of weakly uniomodal functions JO - Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika PY - 2018 SP - 59 EP - 66 VL - 7 IS - 4 UR - http://geodesic.mathdoc.fr/item/VYURV_2018_7_4_a3/ LA - ru ID - VYURV_2018_7_4_a3 ER -
%0 Journal Article %A V. A. Kodnyanko %T Binary scan search (biscan) for conditional minimization of weakly uniomodal functions %J Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika %D 2018 %P 59-66 %V 7 %N 4 %U http://geodesic.mathdoc.fr/item/VYURV_2018_7_4_a3/ %G ru %F VYURV_2018_7_4_a3
V. A. Kodnyanko. Binary scan search (biscan) for conditional minimization of weakly uniomodal functions. Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika, Tome 7 (2018) no. 4, pp. 59-66. http://geodesic.mathdoc.fr/item/VYURV_2018_7_4_a3/
[1] V. V. Fedorov, Numerical Methods of Maximin, Nauka, Moscow, 1979, 272 pp.
[2] D. J. Wilde, Optimum Seeking Methods, Englewood Cliffs, New Jersey, Prentice-Hall Inc., 1964, 202 pp.
[3] D. B. Bunday, Basic Optimization Methods, Hodder Arnold, 1984, 128 pp.
[4] J. K. Kiefer, “Sequential Minimax Search for a Maximum”, Proceedings of the American Mathematical Society 4, 1953, 502–506
[5] V. S. Irbenek, K. V. Kelenin, “Algorithms for Solving the Assignment Problem and Their Application”, Software Products and Systems, 1999, no. 1, 20–24
[6] V. S. Irbenek, “The Method of Local Full Busting and Its Application for Optimizing the Placement of Constructive Modules in the CAD of Electronic Equipment”, Information Technologies and Computer Systems, 1999, no. 1, 3–17