Three-Point Iterated Interval Half-Cutting for Finding All Local Minima of Unknown Single-Variable Function

Vadim Romanuke

doi:10.2478/ecce-2022-0004

Three-Point Iterated Interval Half-Cutting for Finding All Local Minima of Unknown Single-Variable Function

Authors

Vadim Romanuke Vinnytsia Institute of Trade and Economics of State University of Trade and Economics https://orcid.org/0000-0001-9638-9572

DOI:

https://doi.org/10.2478/ecce-2022-0004

Keywords:

Finding extrema, interval half-cutting, local minima, subintervals, unknown single-variable function

Abstract

A numerical method is suggested to find all local minima and the global minimum of an unknown single-variable function bounded on a given interval regardless of the interval length. The method has six inputs: three inputs defined straightforwardly and three inputs, which are adjustable. The endpoints of the initial interval and a formula for evaluating the single-variable function at any point of this interval are the straightforward inputs. The three adjustable inputs are a tolerance with the minimal and maximal numbers of subintervals. The tolerance is the secondary adjustable input. Having broken the initial interval into a set of subintervals, the three-point iterated half-cutting “gropes” around every local minimum by successively cutting off a half of the subinterval or dividing the subinterval in two. A range of subinterval sets defined by the minimal and maximal numbers of subintervals is covered by running the threepoint half-cutting on every set of subintervals. As a set of values of currently found local minima points changes less than by the tolerance, the set of local minimum points and the respective set of function values at these points are returned. The presented approach is applicable to whichever task of finding local extrema is. If primarily the purpose is to find all local maxima or the global maximum of the function, the presented approach is applied to the function taken with the negative sign. The presented approach is a significant and important contribution to the field of numerical estimation and approximate analysis. Although the method does not assure obtaining all local minima (or maxima) for any function, setting appropriate minimal and maximal numbers of subintervals makes missing some minima (or maxima) very unlikely.

References

M. L. Lial, R. N. Greenwell, and N. P. Ritchey, Calculus with Applications (11th edition). Pearson, 2016.

I. Zelinka, V. Snášel, A. Abraham, Eds. Handbook of Optimization. From Classical to Modern Approach. Springer-Verlag Berlin Heidelberg, 2013. https://doi.org/10.1007/978-3-642-30504-7

S. A. Vavasis, “Complexity issues in global optimization: A survey,” in Handbook of Global Optimization. Nonconvex Optimization and Its Applications, vol. 2, R. Horst and P. M. Pardalos, Eds. Springer, Boston, MA, 1995, pp. 27–41. https://doi.org/10.1007/978-1-4615-2025-2_2

J. Stewart, Calculus: Early Transcendentals (6th edition). Brooks/Cole, 2008.

E. Hewitt and K. R. Stromberg, Real and Abstract Analysis. Springer, 1965. https://doi.org/10.1007/978-3-642-88044-5

K. R. Stromberg, Introduction to Classical Real Analysis. Wadsworth, 1981.

L. D. Hoffmann, G. L. Bradley, and K. H. Rosen, Applied Calculus for Business, Economics, and the Social and Life Sciences. McGraw-Hill Higher Education, 2005.

R. Fletcher, Practical Methods of Optimization (2nd edition). J. Wiley and Sons, Chichester, 1987.

V. V. Romanuke, “Appropriate number and allocation of ReLUs in convolutional neural networks,” Research Bulletin of NTUU “Kyiv Polytechnic Institute”, no. 1, pp. 69–78, Mar. 2017. https://doi.org/10.20535/1810-0546.2017.1.88156

V. V. Romanuke, “Appropriateness of DropOut layers and allocation of their 0.5 rates across convolutional neural networks for CIFAR-10, EEACL26, and NORB datasets,” Applied Computer Systems, vol. 22, no. 1, pp. 54–63, Dec. 2017. https://doi.org/10.1515/acss-2017-0018

V. V. Romanuke, “Wind farm energy and costs optimization algorithm under uncertain parameters of wind speed distribution,” Studies in Informatics and Control, vol. 27, no. 2, pp. 155–164, 2018. https://doi.org/10.24846/v27i2y201803

V. V. Romanuke, “Time series smoothing and downsampling for improving forecasting accuracy,” Applied Computer Systems, vol. 26, no. 1, pp. 60–70, May 2021. https://doi.org/10.2478/acss-2021-0008

V. V. Romanuke, “Multiple direction interference suppression by uniform linear phased array sidelobe efficient canceller,” Information and Telecommunication Sciences, vol. 12, no. 1, pp. 33–40, Jun. 2021. https://doi.org/10.20535/2411-2976.12021.33-40

P. von Butovitsch (ed.), Advanced Antenna Systems for 5G Network Deployments: Bridging the Gap Between Theory and Practice. Cambridge, Massachusetts, USA, Academic Press, 2020. https://doi.org/10.1016/C2018-0-05274-3

J. Kiefer, “Sequential minimax search for a maximum,” Proceedings of the American Mathematical Society, vol. 4, no. 3, pp. 502–506, 1953. https://doi.org/10.2307/2032161

M. Avriel and D. J. Wilde, “Optimality proof for the symmetric Fibonacci search technique,” Fibonacci Quarterly, no. 4, pp. 265–269, 1966.

W. H. Press, “Minimization or maximization of functions,” in Numerical Recipes: The Art of Scientific Computing (3rd edition), W. H. Press, S. A. Teukolsky, W. T. Vetterling, B. P. Flannery, Eds. Cambridge University Press, New York, 2007, pp. 487–562.

A. Kheldoun, R. Bradai, R. Boukenoui, and A. Mellit, “A new Golden Section method-based maximum power point tracking algorithm for photovoltaic systems,” Energy Conversion and Management, no. 111, pp. 125–136, Mar. 2016. https://doi.org/10.1016/j.enconman.2015.12.039

K. J. Overholt, “Efficiency of the Fibonacci search method,” BIT Numerical Mathematics, vol. 13, no. 1, pp. 92–96, Mar. 1973. https://doi.org/10.1007/BF01933527

J.-D. Lee, C.-H. Chen, J.-Y. Lee, L.-M. Chien, and Y.-Y. Sun, “The Fibonacci search for cornerpoint detection of two-dimensional images,” Mathematical and Computer Modelling: An International Journal, vol. 16, no. 11, pp. 15–20, Nov. 1992. https://doi.org/10.1016/0895-7177(92)90102-Q

S. Edelkamp and S. Schrödl, “Chapter 7 – Symbolic search,” in Heuristic Search, S. Edelkamp, S. Schrödl, Eds. Morgan Kaufmann, 2012, pp. 283–318. https://doi.org/10.1016/B978-0-12-372512-7.00007-9

Ş. E. Amrahov, A. S. Mohammed, and F. V. Çelebi, “New and improved search algorithms and precise analysis of their average-case complexity,” Future Generation Computer Systems, vol. 95, pp. 743–753, Jun. 2019. https://doi.org/10.1016/j.future.2019.01.043

L. D. Chambers, Ed. The Practical Handbook of Genetic Algorithms: Applications (2nd edition). Chapman and Hall/CRC, 2000. https://doi.org/10.1201/9781420035568

D. E. Goldberg, Genetic Algorithms in Search, Optimization & Machine Learning. Addison-Wesley, 1989.