Geodesic
Multi-start method with deterministic restart mechanism
Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ, Tome 16 (2020) no. 2, pp. 100-111
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The work is devoted to the development and study of a method for solving global optimization problems with interval constraints. The paper proposes a global optimization algorithm based on a deterministic method of selecting starting points for local search methods. The starting points are the extremum points of functions of one variable, obtained by restricting the objective function to straight, collinear coordinate vectors. The effectiveness of the proposed algorithm is demonstrated by the example of the problem of minimizing the energy of a fragment of a flat crystal lattice. The energy of interatomic interaction is calculated using the Tersoff potential. An experimental comparison is made of the developed algorithm with the classical version of the multi-start method, in which pseudo-random points uniformly distributed in the parallelepiped are used to select starting points. As a local search method, in both cases, one of the modifications of the coordinate wise descent method is used. The developed method can be applied to problems with an unknown analytical expression for an objective function that is often encountered in practice.
Keywords: global optimization, multi-start method, fill sequences. 
@article{VSPUI_2020_16_2_a1,
     author = {G. A. Amirkhanova and A. Yu. Gorchakov and A. J. Duysenbaeva and M. A. Posypkin},
     title = {Multi-start method with deterministic restart mechanism},
     journal = {Vestnik Sankt-Peterburgskogo universiteta. Prikladna\^a matematika, informatika, processy upravleni\^a},
     pages = {100--111},
     year = {2020},
     volume = {16},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VSPUI_2020_16_2_a1/}
}
TY  - JOUR
AU  - G. A. Amirkhanova
AU  - A. Yu. Gorchakov
AU  - A. J. Duysenbaeva
AU  - M. A. Posypkin
TI  - Multi-start method with deterministic restart mechanism
JO  - Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ
PY  - 2020
SP  - 100
EP  - 111
VL  - 16
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/VSPUI_2020_16_2_a1/
LA  - ru
ID  - VSPUI_2020_16_2_a1
ER  - 
%0 Journal Article
%A G. A. Amirkhanova
%A A. Yu. Gorchakov
%A A. J. Duysenbaeva
%A M. A. Posypkin
%T Multi-start method with deterministic restart mechanism
%J Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ
%D 2020
%P 100-111
%V 16
%N 2
%U http://geodesic.mathdoc.fr/item/VSPUI_2020_16_2_a1/
%G ru
%F VSPUI_2020_16_2_a1
G. A. Amirkhanova; A. Yu. Gorchakov; A. J. Duysenbaeva; M. A. Posypkin. Multi-start method with deterministic restart mechanism. Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ, Tome 16 (2020) no. 2, pp. 100-111. http://geodesic.mathdoc.fr/item/VSPUI_2020_16_2_a1/

[1] Y. G. Evtushenko, M. A. Posypkin, “Variants of the method of non-uniform coverages for global optimization of partially integer nonlinear problems”, Doc. Academy of Sciences, 437:2 (2011), 168–172 (In Russian) | Zbl

[2] D. C. Karnopp, “Random search techniques for optimization problems”, Automatica, 1:2-3 (1963), 111–121 | DOI

[3] F. J. Solis, R. J. B. Wets, “Minimization by random search techniques”, Mathematics of operations research, 6:1 (1981), 19–30 | DOI | MR | Zbl

[4] G. Pagès, “The Quasi-Monte Carlo Method”, Numerical Probability, Springer, Cham, 2018, 95–132 | DOI | MR

[5] A. B. Owen, P. W. Glynn, Monte Carlo and Quasi-Monte Carlo methods, Springer, California, 2016, 478 pp. | MR

[6] O. Bousquet, S. Gelly, K. Kurach et al, Critical hyper-parameters: No random, no cry, 2017, arXiv: (accessed: 15.05.2019) 1706.03200

[7] J. H. Halton, “Algorithm 247: Radical-inverse quasi-random point sequence”, CACM, 7:12 (1964), 701–702 | DOI

[8] G. Muniraju, B. Kailkhura, J. Thiagarajan, P. T. Bremer, Controlled random search improves sample mining and hyper-parameter optimization, 2018, arXiv: (accessed: 15.05.2019) 1706.03200

[9] T. Gerstner, M. Griebel, “Sparse grids”, Encyclopedia of Quantitative Finance, 2010, 1–6 (accessed: 21.05.2019) | DOI

[10] I. M. Sobol, D. Asotsky, A. Kreinin, K. Kucherenko, “Construction and comparison of highdimensional Sobol' generators”, Wilmott, 2011:56 (2011), 64–79 | DOI

[11] I. M. Sobol, Points uniformly filling a multidimensional cube, Znanie, M., 1985, 125 pp. (In Russian)

[12] F. J. Hickernell, Y. Yuan, A simple multistart algorithm for global optimization, CiteSeerX Rreprint, 1997 (accessed: 10.05.2019) http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.46.1346

[13] R. Martí, J. A. Lozano, A. Mendiburu, L. Hernando, “Multi-start methods”, Handbook of Heuristics, Springer, Cham, 2016, 1–21

[14] R. Martí, J. M. Moreno-Vega, A. Duarte, “Advanced multi-start methods”, Handbook of Metaheuristics, Springer, Boston, 2010, 265–281 | DOI

[15] R. Martí, R. Aceves, M. T. Leonet et al., “Intelligent multi-start methods”, Handbook of Metaheuristics, Springer, Cham, 2019, 221–243 | DOI | MR

[16] A. Y. Gorchakov, M. A. Posypkin, “The effectiveness of local search methods in the problem of finding the minimum energy of a 2-D crystal”, Modern Information Technology and IT-education, 13:2 (2017), 97–102 (In Russian)

[17] M. D. McKay, R. J. Beckman, W. J. Conover, “Comparison of three methods for selecting values of input variables in the analysis of output from a computer code”, Technometrics, 21:2 (1979), 239–245 | MR | Zbl

[18] R. Hofer, P. Ktitzer, G. Larcher, F. Pillichshammer, “Distribution properties of generalized van der Corput-Halton sequences and their subsequences”, International Journal of Number Theory, 5:4 (2009), 719–746 | DOI | MR | Zbl

[19] J. P. Lambert, “Quasi-Monte Carlo, low discrepancy sequences, and ergodic transformations”, Journal of Computational and Applied Mathematics, 12 (1985), 419–423 | DOI | MR | Zbl

[20] H. Faure, “Discrépance de suites associées à un système de numération (en dimensions)”, Acta arithmetica, 41:4 (1982), 337–351 | DOI | MR | Zbl

[21] H. Niederreiter, Random number generation and quasi-Monte Carlo methods, CBMS-NSF Regional Conference Series in Applied Mathematics, 63, Siam, Philadelphia, 1992, 242 pp. | MR | Zbl

[22] S. A. Lurie, M. A. Posypkin, Yu. O. Solyaev, “Method of identification of scale parameters of gradient theory of elasticity on the basis of numerical experiments in flat composite structures”, International Journal of Open Information Technologies, 3:6 (2015), 1–5 (In Russian)

[23] Y. G. Evtushenko, S. A. Lurie, M. A. Posypkin, “Application of optimization methods for finding equilibrium states of two-dimensional crystals”, Computational Mathematics and Mathematical Physics, 56:12 (2016), 2032–2041 (In Russian) | Zbl

[24] G. A. Amirhanova, A. Y. Gorchakov, A. J. Dujsenbaeva, M. A. Posypkin, “Application of the exact penalty function method to the problem of minimizing the energy of a plane crystal”, XIV Intern. Asian School-Seminar “Problems of Optimizing Complex Systems” (20–31 Jule 2018, Kyrgyz Republic, Lake Issyk-Kul), IICT Publ, Almaty, 2018, 107–113 (In Russian)

[25] G. A. Amirhanova, A. Y. Gorchakov, A. J. Dujsenbaeva, “Hybridization of Monte Carlo methods, simulated annealing and local search”, III Intern. Scientific Conference “Informatics and Applied Mathematics” (26-29 September 2018, Almaty, Kazakhstan), 2018, 266–274 (In Russian)

[26] G. Amirkhanova, A. Gorchakov, A. Duysenbaeva, “The application of the methodology of fast automatic differentiation to calculate the gradient of the potential REBO (LAMMPS)”, DEStech Transactions on Computer Science and Engineering, N. optim, 2018, 103–113

[27] S. Plimpton, “Fast parallel algorithms for short-range molecular dynamics”, Journal of Computational Physics, 117:1 (1995), 1–19 | DOI | Zbl

[28] S. Plimpton, P. Crozier, A. Thompson, Lammps-large-scale atomic/molecular massively parallel simulator, Preprint No 18, Sandia National Laboratories, 2007, 43 pp.

[29] S. J. Wright, “Coordinate descent algorithms”, Mathematical Programming, 151:1 (2015), 3–34 | DOI | MR | Zbl

[30] O. V. Khamisov, M. Posypkin paper Univariate global optimization with point-dependent Lipschitz constants, AIP Conference Proceedings, 2070, AIP Publishing, 2019, 1–4

[31] O. Khamisov, M. Posypkin, A. Usov, “Piecewise linear bounding functions for univariate global optimization”, International Conference on Optimization and Applications, Springer, Cham, 2018, 170–185

[32] S. A. Piyavskii, “An algorithm for finding the absolute extremum of a function”, USSR Computational Mathematics and Mathematical Physics, 12:4 (1972), 57–67 | DOI | MR

[33] P. Hansen, B. Jaumard, Lu Shi-Hui, “Global optimization of univariate lipschitz functions: I. Survey and properties”, Mathematical Programming, 55:1-3 (1992), 251–272 | DOI | MR | Zbl

[34] J. Tersoff, “Modeling solid-state chemistry: Interatomic potentials for multicomponent systems”, Physical Review B, 39:8 (1989), 55–66 | DOI

[35] Y. G. Evtushenko, M. A. Posypkin, I. Sigal, “A framework for parallel large-scale global optimization”, Computer Science-Research and Development, 23:3-4 (2009), 211–215 | DOI

[36] I. V. Bychkov, M. O. Manzyuk, A. A. Semenov et al., “Technology for integrating idle computing cluster resources into volunteer computing projects”, 2015 5th International Workshop on Computer Science and Engineering: Information Processing and Control Engineering, WCSE 2015-IPCE, 2015, 109–114

[37] M. Posypkin, A. Usov, “Implementation and verification of global optimization benchmark problems”, Open Engineering, 7:1 (2017), 470–478 | DOI