BSU Bulletin. Mathematics, Informatics
Bibliographic description:
SOFTWARE IMPLEMENTATION OF NONLOCAL ONE-DIMENSIONAL OPTIMIZATION ALGORITHMS BASED ON THE HÖLDER CONDITION // BSU Bulletin. Mathematics, Informatics. - 2019. №4. . - С. 40-56.
Title:
SOFTWARE IMPLEMENTATION OF NONLOCAL ONE-DIMENSIONAL OPTIMIZATION ALGORITHMS BASED ON THE HÖLDER CONDITION
Financing:
Работа выполнена при финансовой поддержке РФФИ, проект №19-37-90065.
Codes:
Annotation:
The problem of one-dimensional search for a global minimum of a nonconvex func- tion often appears as an auxiliary for solving multidimensional optimization problems. For many years, nonlocal one-dimensional optimization methods have been developed by a number of specialists from Russia and foreign countries. The article considers the proposed modifications of nonlocal one-dimensional search algorithms based on the Hölder condition. These modifications are implemented as an algorithms library and integrated into a single software package. The library includes modifications of Yu. G. Evtushenko’s, R. G. Strongin’s methods and a combined algorithm based on the Strongin’s method of "parabolas". We have made multivariant computational experi- ments to compare the implemented algorithms for various values of the Hölder index. An analysis of the performed experiments showed that the generalization of algorithms based on the Hölder condition gives in some cases a significant acceleration effect over algorithms based on the Lipschitz condition. During testing the most preferred values of the Hölder index and leading algorithms were identified. The conducted experimen- tal studies confirmed the suitability of the implemented modifications for finding the global minimum of the non-convex function of one variable.
Keywords:
nonlocal one-dimensional search; the Hölder condition; Evtushenko’s method; Strongin’s method; global minimum; algorithms library; software implementa- tion.
List of references:
Evtushenko Yu. G. Metody poiska globalnogo ekstremuma [Global Extremum Search Methods]. Issledovanie operatsii. 1974. No. 4. Pp. 39–68.
Zhiglyavskii A. A., Zhilinskas A. G. Metody poiska globalnogo ekstremuma [Global Extremum Search Methods]. Moscow: Nauka Publ., 1991. 248 p.
Piyavskii S. A. Odin algoritm otyskaniya absolyutnogo ekstremuma funktsii [An Algorithm for Search of the Absolute Extremum of Functions]. Computational Mathe- matics and Mathematical Physics. 1972. Vol. 12. Pp. 885–896.
Strongin R. G. Chislennye metody v mnogoekstremalnykh zadachakh (infor- matsionno-statisticheskie algoritmy) [Numerical Methods in Multi-Extremum Prob- lems (information and statistical algorithms)]. Moscow: Nauka Publ., 1978. 240 p.
Brent R. P. Algorithms for Minimization without Derivatives. New Jersey: Pren- tice Hall, 1973. 195 p.
Timonov L. N. An Algorithm for Search of a Global Extremum. Engineering Cybernetics. 1977. Vol. 15, No. 3. Pp. 38–44.
Horst R., Pardalos P. M. Handbook of Global Optimization. Springer Science & Business Media, 2013. 880 p.
Kushner H. J. A New Method of Locating the Maximum Point of an Arbitrary Multipeak Curve in the Presence of Noise. Journal of Basic Engineering. 1964. Vol. 86, No. 1. Pp. 97–106.
ВЕСТНИК БГУ. МАТЕМАТИКА, ИНФОРМАТИКА 2019/4
image
Schoen F. On a Sequential Search Strategy in Global Optimization Problems.
Calcolo. 1982. Vol. 19, No. 3. Pp. 321–334.
Galperin E. A. The Cubic Algorithm. Journal of Mathematical Analysis and Applications. 1985. Vol. 112, No. 2. Pp. 635–640.
Hansen P., Jaumard B., Lu S. H. Global Optimization of Univariate Lipschitz Functions: I. Survey and Properties. Mathematical Programming. 1992. Vol. 55, No. 1. Pp. 251–272.
Zhiglyavsky A., Zilinskas A. Stochastic Global Optimization. Springer Sci- ence-Business Media, 2008. 262 p.
Zhiglyavsky A. A. Matematicheskaya teoriya sluchainogo globalnogo poiska [Mathematical Theory of Random Global Search]. Leningrad: Leningrad University Publishing Department, 1985. 296 p.
Gornov A. Yu. Primenenie splain-approksimatsii dlya konstruirovaniya algorit- mov optimizatsii s novymi vychislitelnymi svoistvami [Application of Spline Ap- proximation for Constructing Optimization Algorithms with New Computational Prop- erties]. Trudy vserossiiskoi konferentsii “Diskretnaya optimizatsiya i issledovanie op- eratsii”— Proc. All-Rus. Conf. “Discrete Optimization and Operations research”. Vladivostok. 2007. Pp. 99.
Pintér J. D. Convergence Properties of Stochastic Optimization Proce- dures. Optimization. 1984. Vol. 15, No. 3. Pp. 405–427.
Goryachikh A. A Class of Smooth Modification of Space-Filling Curves for Global Optimization Problems. Models, Algorithms, and Technologies for Network Analysis. 2016. Pp. 57–65.
Bulatov V. P., Khamisov O. V. Metod otsecheniya v E^n+1 dlya resheniya zadach globalnoi optimizatsii na odnom klasse funktsii [Cut-Off Method in E^n+1 for Solving Global Optimization Problems on One Class of Functions]. Computational Mathematics and Mathematical Physics. 2007. Vol. 47, No. 11. Pp. 1830–1842.
Zarodnyuk T. S., Gornov A. Yu. Tekhnologiya poiska globalnogo ekstremuma v zadache optimalnogo upravleniya [Global Extremum Search Technology in an Opti- mal Control Problem]. Sovremennye tekhnologii. Sistemnyi analiz. Modelirovanie. 2008. No. 3. Pp. 70–76.
Rastrigin L. A. Sistemy ekstremalnogo upravleniia [Extremal Control Systems]. Moscow: Nauka Publ., 1974. 632 p.
Zhiglyavskii A. A., Zhilinskas A. G. Metody poiska globalnogo ekstremuma [Global Extremum Search Methods]. Moscow: Nauka Publ., 1991. 248 p.
Piyavskii S. A. Odin algoritm otyskaniya absolyutnogo ekstremuma funktsii [An Algorithm for Search of the Absolute Extremum of Functions]. Computational Mathe- matics and Mathematical Physics. 1972. Vol. 12. Pp. 885–896.
Strongin R. G. Chislennye metody v mnogoekstremalnykh zadachakh (infor- matsionno-statisticheskie algoritmy) [Numerical Methods in Multi-Extremum Prob- lems (information and statistical algorithms)]. Moscow: Nauka Publ., 1978. 240 p.
Brent R. P. Algorithms for Minimization without Derivatives. New Jersey: Pren- tice Hall, 1973. 195 p.
Timonov L. N. An Algorithm for Search of a Global Extremum. Engineering Cybernetics. 1977. Vol. 15, No. 3. Pp. 38–44.
Horst R., Pardalos P. M. Handbook of Global Optimization. Springer Science & Business Media, 2013. 880 p.
Kushner H. J. A New Method of Locating the Maximum Point of an Arbitrary Multipeak Curve in the Presence of Noise. Journal of Basic Engineering. 1964. Vol. 86, No. 1. Pp. 97–106.
ВЕСТНИК БГУ. МАТЕМАТИКА, ИНФОРМАТИКА 2019/4
image
Schoen F. On a Sequential Search Strategy in Global Optimization Problems.
Calcolo. 1982. Vol. 19, No. 3. Pp. 321–334.
Galperin E. A. The Cubic Algorithm. Journal of Mathematical Analysis and Applications. 1985. Vol. 112, No. 2. Pp. 635–640.
Hansen P., Jaumard B., Lu S. H. Global Optimization of Univariate Lipschitz Functions: I. Survey and Properties. Mathematical Programming. 1992. Vol. 55, No. 1. Pp. 251–272.
Zhiglyavsky A., Zilinskas A. Stochastic Global Optimization. Springer Sci- ence-Business Media, 2008. 262 p.
Zhiglyavsky A. A. Matematicheskaya teoriya sluchainogo globalnogo poiska [Mathematical Theory of Random Global Search]. Leningrad: Leningrad University Publishing Department, 1985. 296 p.
Gornov A. Yu. Primenenie splain-approksimatsii dlya konstruirovaniya algorit- mov optimizatsii s novymi vychislitelnymi svoistvami [Application of Spline Ap- proximation for Constructing Optimization Algorithms with New Computational Prop- erties]. Trudy vserossiiskoi konferentsii “Diskretnaya optimizatsiya i issledovanie op- eratsii”— Proc. All-Rus. Conf. “Discrete Optimization and Operations research”. Vladivostok. 2007. Pp. 99.
Pintér J. D. Convergence Properties of Stochastic Optimization Proce- dures. Optimization. 1984. Vol. 15, No. 3. Pp. 405–427.
Goryachikh A. A Class of Smooth Modification of Space-Filling Curves for Global Optimization Problems. Models, Algorithms, and Technologies for Network Analysis. 2016. Pp. 57–65.
Bulatov V. P., Khamisov O. V. Metod otsecheniya v E^n+1 dlya resheniya zadach globalnoi optimizatsii na odnom klasse funktsii [Cut-Off Method in E^n+1 for Solving Global Optimization Problems on One Class of Functions]. Computational Mathematics and Mathematical Physics. 2007. Vol. 47, No. 11. Pp. 1830–1842.
Zarodnyuk T. S., Gornov A. Yu. Tekhnologiya poiska globalnogo ekstremuma v zadache optimalnogo upravleniya [Global Extremum Search Technology in an Opti- mal Control Problem]. Sovremennye tekhnologii. Sistemnyi analiz. Modelirovanie. 2008. No. 3. Pp. 70–76.
Rastrigin L. A. Sistemy ekstremalnogo upravleniia [Extremal Control Systems]. Moscow: Nauka Publ., 1974. 632 p.
Article.pdf