Робастная оптимизация: защита математических моделей от параметрической неопределенности

Математическая философия робастной оптимизации строится на концепции минимакса из теории игр: мы ищем такое управленческое решение, которое минимизирует целевую функцию в условиях, когда условная «природа» максимизирует наш ущерб. Центральным элементом математического моделирования становится выбор множества неопределенности (Uncertainty Set) для неизвестных параметров. Если мы используем простое коробчатое множество (интервальную неопределенность), мы предполагаем, что каждый параметр может независимо принять абсолютно любое значение между своим историческим минимумом и максимумом. Этот подход, впервые предложенный Алленом Сойстером в 1973 году, дает абсолютно надежные, но чрезмерно консервативные (и астрономически дорогие) решения. Вероятность того, что все независимые параметры одновременно примут свои наихудшие значения в реальной жизни, практически равна нулю, поэтому компания платит гигантскую премию за защиту от невозможного апокалипсиса.

Для решения проблемы сверхконсерватизма Аркадий Немировский и Аарон Бен-Тал разработали теорию эллипсоидальной неопределенности. В этой модели предполагается, что случайные параметры не могут одновременно принимать экстремальные значения, а их совместные отклонения ограничены многомерным эллипсоидом (что хорошо согласуется со статистическими законами нормального распределения и матрицами ковариации). Внедрение эллипсоидального множества неопределенности превращает классическую задачу линейного программирования в задачу конического квадратичного программирования второго порядка (Second-Order Cone Programming, SOCP). Решение этой задачи с помощью алгоритмов внутренней точки требует чуть больше вычислительных ресурсов, но обеспечивает идеальный компромисс: решение гарантированно выживает при 99 процентах реальных кризисов, при этом его финансовая стоимость лишь незначительно превышает стоимость наивного детерминированного оптимума.

Еще одним грандиозным прорывом стала концепция полиэдральной неопределенности и бюджетов неопределенности, предложенная Димитрисом Бертсимасом. В этой модели ЛПР задает специальный параметр (Гамма) — бюджет неопределенности, который устанавливает максимальное количество переменных в каждом ограничении, которым разрешено отклониться до своих наихудших значений одновременно. Гениальность подхода Бертсимаса заключается в том, что его робастный аналог (Robust Counterpart) остается задачей чисто линейного программирования! Это позволяет корпорациям использовать сверхбыстрые коммерческие симплекс-солверы для оптимизации логистических сетей с миллионами переменных, легко регулируя уровень паранойи с помощью единственного параметра Гамма.

Сегодня методы робастной оптимизации являются стандартом де-факто в критически важных отраслях. В управлении энергосистемами диспетчеры используют робастные модели для расчета оптимальных графиков работы генераторов (Unit Commitment), гарантируя, что электросеть не рухнет даже при наихудших сценариях пикового потребления и одновременной остановки ветряных электростанций из-за штиля. В финансовом инжиниринге робастные алгоритмы защищают портфели ценных бумаг от крахов, минимизируя потери при экстремальных рыночных шоках, доказывая, что в мире абсолютной неопределенности правильная геометрия математических ограничений способна спасти бизнес от банкротства.