RUS  ENG
Полная версия
СЕМИНАРЫ
Математический кружок
6 марта 2012 г., г. Долгопрудный, 115 КПМ МФТИ
Цикл "Весна 2012"

В окрестностях Монте-Карло. Часть 1

Б. Т. Поляк

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


http://www.youtube.com/watch?v=JgRFIqLeAf8

Аннотация: Лекции будут посвящены нескольким алгоритмам, связанным с методом Монте-Карло. В них будут также предложены как учебные, так и исследовательские задачи.
Часть 1 (2 лекции). Генерация точек, равномерно распределенных в заданной области.
А. Краткая история метода Монте-Карло. Псевдослучайные числа. Выборка из равномерного распределения в кубе, на сфере, в шаре. Метод отсеивания, его неэффективность.
Б. Метод HR (Hit-and-Run). Случайное блуждание по области как пример MCMC (Markov-chain-Monte-Carlo) методов. Теорема о предельном равномерном распределении HR. Реализация HR для различных множеств (многогранников, решений линейных матричных неравенств). Граничный оракул. Трудности, связанные с HR для множеств «плохой» геометрии.
В. Ускорение сходимости HR. Использование барьеров выпуклых множеств и эллипсоидов Дикина.
Г. Метод SB (Shake-and-Brake). Использование идей бильярдов со случайными отражениями для генерации равномерно распределенных точек.
Часть 2 (2 лекции). Приложения.
А. Использование равномерных выборок для оценки геометрических характеристик тел и их аппроксимаций. Вычисление многомерных интегралов на сложных областях.
Б. Выпуклая оптимизация. Метод центра тяжести. Его рандомизированный вариант. Оценка центра тяжести с помощью процедур стохастической аппроксимации.
В. Глобальная оптимизация. Метод мультистарта. Минимизация вогнутой функции на выпуклом многограннике.
Г. Использование в управлении. Генерация точек на невыпуклых областях устойчивых полиномов и матриц.

Список литературы
  1. Rubinstein R.Y., Kroese D.P., Simulation and the Monte Carlo method, Wiley, 2008  mathscinet
  2. Diaconis P., “Markov chain Monte Carlo revolution”, Bull. AMS, 46:2 (2009), 179–205  crossref  mathscinet  zmath  scopus
  3. Турчин В.Ф., “К вычислению многомерных интегралов по методу Монте-Карло”, ТВП, 16:4 (1971), 738–743  mathnet
  4. Smith R.L., “Efficient Monte Carlo procedures for generating points uniformly distributed over bounded regions”, Oper. Res., 32:6 (1984), 1296-1308  crossref  mathscinet  zmath  isi  scopus
  5. Боровков К.А., “Об одном новом варианте метода Монте-Карло”, ТВП, 36:2 (1991), 342–346  mathnet  mathscinet
  6. Polyak B.T., Gryazina E.N., “Randomized methods based on new Monte Carlo schemes for control and optimization”, Ann. Oper. Res., 189:1 (2011), 343–356  crossref  mathscinet  zmath  isi  scopus
  7. Polyak B.T., Gryazina E.N., “Hit-and-Run: randomized technique for control problemsrecastedas concave programming”, 18th IFAC World Congress, Milan, Italy, 2011, 2321–232

Цикл докладов

© МИАН, 2026