Борис Поляк
Институт проблем управления им. В.А. Трапезникова РАН

Монте-Карло и рандомизация в задачах оптимизации

Метод Монте-Карло, изобретенный в конце 1940-х годов выдающимися физиками и математиками Фон-Нейманом, Теллером, Метрополисом и Уламом, нашел многочисленные применения в задачах моделирования, интегрирования, оценивания. Естественны и попытки его применения в задачах оптимизации. Мы рассмотрим варианты его использования в задачах выпуклой и глобальной оптимизации и поясним, почему эти попытки недостаточно эффективны в условиях большой размерности. В то же время оказывается, что сама идея рандомизации для решения детерминированных задач оптимизации иногда весьма плодотворна; будет приведено несколько примеров такого рода.