|
Article information
2024 , Volume 29, ¹ 1, p.32-44
Skorik D.A.
Using the geometric properties of quadratic functional intervals to reduce the search area for the minimum of a function on an interval
The paper addresses the practical application of functional intervals, whose boundaries are quadratic polynomials of one variable, in order to solve one of the classical problems of computational mathematics — finding the absolute minimum of a smooth function of one variable on an interval. Currently, this problem is solved in various ways. In particular, interval methods of global optimization based on adaptive fragmentation of the domain of function definition and estimation of its values by the resulting sub-domains have become widespread. The interval methods, which provide a high order of estimation for the range of values of the function on the interval, are more advantegeous over the lower-order methods only whena the width of the functional interval is small. Therefore, when using such methods, it is necessary to quickly remove from consideration the areas in which cannot be a minimum of the considered function. Algorithms based on the “branches-and-bounds” method cut off such areas when considering the splitting tree, based on interval estimates for the range of values of the function. Additionally, at each iteration of the crushing, the reduction of the search area is achieved using various techniques. The application of these techniques requires additional calculations of values or interval estimates for the areas of values of the function and/or its derivatives. The article proposes a method for reducing the search area of the minimum function, which uses a geometric interpretation of quadratic functional intervals. The method can be widely appllied as an integral part of popular interval algorithms of global optimization based on adaptive fragmentation for the domain of definition of the considered function. It was shown that the method of reducing the minimum search area indicated in the work is promising for use, for example, for solving the problem of global optimization by the “branches-andbounds” method.
[link to elibrary.ru]
Keywords: minimum of a function, interval analysis, functional interval, search area reduction, two-sided estimate
doi: 10.25743/ICT.2024.29.1.004
Author(s):
Skorik Dmitry Alexandrovich
Position: Student
Office: Federal Research Center for information and computational technologies
Address: 630090, Russia, Novosibirsk, 6, acad. Lavrentiev ave.
E-mail: dimakro2010@yandex.ru
SPIN-code: 9530-0666 References:
1. Shary S.P. Konechnomernyy interval’nyy analiz [Interval analysis with finite dimensions]. Novosibirsk: “XYZ”; 2022: 654. Available at: http://www.nsc.ru/interval/Library/InteBooks/SharyBook.pdf.
2. Hansen E., Walster G.W. Global optimization using interval analysis. Boca Raton: CRC Press; 2003: 728.
3. Berz M., Bischof C., Griewank A., Corliss G. Computational differentiation: techniques, applications, and tools. Philadelphia: SIAM; 1996: 421.
4. Griewank A., Corliss G. Automatic differentiation of algorithms. Philadelphia: SIAM; 1992: 353.
5. Griewank A., Walther A. Evaluating derivatives: principles and techniques of algorithmic differentiation. Second edition. Cambridge: Cambridge University Press; 2008: 460.
6. Skorik D.A., Shary S.P. On a high order interval estimation of the minimum of a function. Computational Technologies. 2022; 27(4):77–83. DOI:10.25743/ICT.2022.27.4.006. (In Russ.)
7. Kearfott R.B., Nakao M., Neumaier A., Rump S., Shary S.P., van Hentenryck P. Standardized notation in interval analysis. Computational Technologies. 2010; 15(1):7–13.
8. Bourbaki N., Spain P. Functions of a real variable. Heidelberg: Springer Berlin; 2004: 338.
9. Neumaier A. Interval methods for systems of equations. Cambridge: Cambridge University Press; 1991: 256.
10. Ratschek H., Rokne J. Computer methods for the range of functions. Chichester, N.Y.: Ellis Horwood, Halsted Press; 1984: 168.
11. Skorik D.A. Razvitie lineynoy funktsional’noy arifmetiki i ee prilozhenie k resheniyu zadach interval’nogo analiza [Development of linear functional arithmetic and its application for solving problems of interval analysis]. Available at: https://arxiv.org/abs/2210.14782. (In Russ.)
Bibliography link:
Skorik D.A. Using the geometric properties of quadratic functional intervals to reduce the search area for the minimum of a function on an interval // Computational technologies. 2024. V. 29. ¹ 1. P. 32-44
|
