Randomized algorithms in interval global optimization

S. P. Shary

Sibirskij žurnal vyčislitelʹnoj matematiki, Tome 11 (2008) no. 4, pp. 457-474.

Résumé

This paper is a critical survey of the interval optimization methods aimed at computing the global optima of multivariable functions. To overcome some drawbacks of traditional deterministic interval techniques, we outline the ways of constructing stochastic (randomized) algorithms in interval global optimization, in particular those based on the ideas of a random search and simulated annealing.

Bibliographie

[1] Azenkott R., “Protsedura “otpuska””, Tr. seminara N. Burbaki za 1988 god, Mir, Moskva, 1990, 235–251

[2] Alefeld G., Khertsberger Yu., Vvedenie v intervalnye vychisleniya, Mir, Moskva, 1987 | MR

[3] GaganovA. A., “O slozhnosti vychisleniya intervala znachenii polinoma ot mnogikh peremennykh”, Kibernetika, 1985, no. 4, 6–8

[4] Evtushenko Yu. G., Ratkin V. A., “Metod polovinnykh delenii dlya globalnoi optimizatsii funktsii mnogikh peremennykh”, Izvestiya AN SSSR “Tekhnicheskaya kibernetika”, 1987, no. 1, 119–128 | MR

[5] Zhiglyavskii A. A.,Zhilinskas A. G., Metody poiska globalnogo ekstremuma, Nauka, Moskva, 1991 | MR

[6] Intervalnyi analiz i ego prilozheniya, http://www.nsc.ru/interval/

[7] Kalmykov S. A., Shokin Yu. I., Yuldashev Z. Kh., Metody intervalnogo analiza, Nauka, Novosibirsk, 1986 | MR | Zbl

[8] Panov N. V., Koldakov V. V., “Programmnyi kompleks dlya graficheskogo predstavleniya protsessa i rezultatov raboty intervalnykh algoritmov”, Pyataya Mezhdunar. konf. “Perspektivy sistem informatiki” pamyati akad. A. P. Ershova v PSI'03. Mezhdunar. soveschanie po intervalnoi matematike i metodam rasprostraneniya ogranichenii (8–9 iyulya 2003 g., Novosibirsk, Akademgorodok), ISI SO RAN, Novosibirsk, 2003, 38–45

[9] Panov N. V., Sharyi S. P., “Stokhasticheskie podkhody v intervalnykh metodakh globalnoi optimizatsii”, Vserossiiskoe (s mezhdunarodnym uchastiem) soveschanie po intervalnomu analizu i ego prilozheniyam INTERVAL-06, Rasshirennye tezisy dokladov (1–4 iyulya 2006 goda, Petergof, Rossiya), VVM, S.-Peterburg, 2006, 101–105

[10] Rastrigin L. A., Statisticheskie metody poiska, Nauka, M., 1968 | MR

[11] Sharyi S. P., “Stokhasticheskie podkhody v intervalnoi globalnoi optimizatsii”, Tr. XIII Baikalskoi Mezhdunar. shkoly-seminara “Metody optimizatsii i ikh prilozheniya” (Irkutsk–Severobaikalsk, 2–8 iyulya 2005 g.), Intervalnyi analiz, 4, ISEM SO RAN, Irkutsk, 2005, 85–105

[12] Aarts E., Korst J., Simulated Annealing and Boltzmann Machines: A Stochastic Approach to Combinatorial Optimization and Neural Computing, J. Wiley Sons, Chichester, 1989 | MR

[13] Corliss G. F., Kearfott R. B., “Rigorous global search: Industrial applications”, Developments in Reliable Computing, ed. T. Csendes, Kluwer, Dordrecht, 1999, 1–16 ; http://interval.louisiana.edu/preprints/scan98.pdf/ | Zbl

[14] Dixon L. C. W., Szegő G. P., “The global optimization problem: an introduction”, Towards Global Optimization, II, eds. Dixon L. C. W. and Szegő G. P., North Holland, Amsterdam, 1978, 1–15 | MR

[15] C. A. Floudas and P. M. Pardalos (eds.), Encyclopedia of Optimization, Vol. I–VI, Kluwer, Dordrecht, 2001 | MR

[16] Hansen E., Walster G. W., Global Optimization Using Interval Analysis, Marcel Dekker, New York, 2004 | MR

[17] Kearfott R. B., Rigorous Global Search: Continuous Problems, Kluwer, Dordrecht, 1996 | MR

[18] Kreinovich V., Kearfott R. B., “Beyond convex? Global optimization is feasible only for convex objective functions: a theorem”, J. of Global Optimization, 33:4 (2005), 617–624 | DOI | MR | Zbl

[19] Kirkpatrick S., Gelatt C. D., and Vecchi M. P., “Optimization by simulated annealing”, Science, 220 (1983), 671–680 | DOI | MR

[20] Moore R. E., Methods and Applications of Interval Analysis, SIAM, Philadelphia, 1979 | MR | Zbl

[21] Neumaier A., Interval Methods for Systems of Equations, Cambridge University Press, Cambridge, 1990 | MR | Zbl

[22] Ratschek H., Rokne J., New Computer Methods for Global Optimization, Ellis Horwood, Halsted Press, Chichester–New York, 1988 | MR | Zbl