Стохастическое программирование: метод выборочных средних (SAA)

Математическая структура стохастической задачи (например, двухэтапного программирования с регрессом) требует минимизации функции $f(x) = c^T x + \mathbb{E}[Q(x, \omega)]$, где $x$ — решения первого этапа (принимаемые до реализации неопределенности), а $Q(x, \omega)$ — оптимальная стоимость второго этапа для сценария $\omega$. Суть метода SAA заключается в генерации $N$ независимых одинаково распределенных (i.i.d.) сценариев $\omega_1, \omega_2, \dots, \omega_N$ из известного вероятностного распределения. Исходная непрерывная задача аппроксимируется детерминированной задачей: минимизировать $\hat{f}_N(x) = c^T x + \frac{1}{N} \sum_{i=1}^N Q(x, \omega_i)$. Полученная аппроксимированная задача является задачей крупномасштабного математического программирования, которая может быть решена с помощью декомпозиции Бендерса или прямых методов внутренней точки.

Теоретический фундамент SAA зиждется на Законе больших чисел и Теории больших уклонений. По мере увеличения размера выборки $N$, эмпирическая целевая функция $\hat{f}_N(x)$ сходится к истинной функции $f(x)$ с вероятностью 1 (почти наверное). Более того, математически доказано, что оптимальные решения $\hat{x}_N$ аппроксимирующей задачи экспоненциально быстро сходятся к множеству оптимальных решений истинной задачи. Это означает, что даже относительно небольшая, но репрезентативная выборка сценариев способна дать решение высочайшего качества, не перегружая вычислительные мощности, что делает метод SAA стандартом в современной робастной логистике и финансах.

Огромным преимуществом SAA является встроенный механизм статистической оценки качества полученного решения (Optimality Gap). Процесс выглядит следующим образом: генерируется $M$ независимых партий сценариев размером $N$. Для каждой партии решается SAA-задача. Усреднение полученных оптимумов дает строгую статистическую нижнюю оценку истинного глобального оптимума. Затем генерируется одна независимая "гигантская" выборка $N_{eval}$ (например, 100 000 сценариев). Вычисление значения целевой функции на этой гигантской выборке для лучшего найденного решения $\hat{x}_N$ дает строгую верхнюю оценку. Разность между этими оценками позволяет актуарию с 95% доверительным интервалом сказать, насколько найденное решение далеко от абсолютного недостижимого математического идеала.

Метод SAA перевернул индустрию планирования энергосистем, управления цепочками поставок и расчета инвестиционных портфелей. Он позволяет интегрировать сложнейшие нелинейные корреляции случайных величин в модель просто путем сэмплирования из правильных копул. Перекладывая тяжесть аналитического интегрирования на плечи статистического моделирования Монте-Карло, метод SAA позволяет специалистам по исследованию операций решать стохастические задачи такого масштаба, которые еще два десятилетия назад считались математически неразрешимыми.

Список литературы:
1. Shapiro A., Dentcheva D., Ruszczynski A. Lectures on Stochastic Programming: Modeling and Theory. — SIAM, 2009.
2. Kleywegt A.J., Shapiro A., Homem-de-Mello T. The Sample Average Approximation Method for Stochastic Discrete Optimization. — SIAM Journal on Optimization, 2002.
3. Бирге Дж., Лувев Ф. Введение в стохастическое программирование. — М.: Мир, 2000.