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

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