Робастная оптимизация: модели неопределенности и алгоритмы гарантированного поиска

Исторически первый подход к робастной линейной оптимизации был предложен Сойстером в 1973 году. Он использовал прямоугольные (Box) множества неопределенности. Решение Сойстера гарантировало абсолютную надежность: каждое ограничение удовлетворялось при любых колебаниях параметров в заданных интервалах. Однако этот подход оказался "ультра-консервативным". В реальных системах вероятность того, что все независимые параметры одновременно примут наихудшие значения, астрономически мала. Из-за этого решения Сойстера приводили к огромным финансовым издержкам, жертвуя прибылью ради избыточной перестраховки.

Настоящая революция произошла на рубеже веков благодаря трудам Бен-Тала, Немировского и Берцимаса. Они предложили использовать эллипсоидальные и полиэдральные множества неопределенности. Эллипсоидальная неопределенность (базирующаяся на нормах) позволяет задавать "бюджет неопределенности" — параметр, который математически контролирует степень консерватизма. Мы предполагаем, что параметры могут отклоняться, но суммарное отклонение (в метрике эллипсоида) ограничено. Это позволяет находить решения, которые обеспечивают 99% надежности при издержках, лишь незначительно превышающих издержки детерминированной задачи.

Математическое изящество современной робастной оптимизации заключается в ее вычислительной податливости (Tractability). Оказывается, что если исходная задача является задачей линейного программирования (LP), а неопределенность задана эллипсоидом, то "робастный эквивалент" этой задачи строго преобразуется в задачу конического программирования второго порядка (SOCP). Если неопределенность полиэдральная, робастный эквивалент остается задачей линейного программирования, хотя и большей размерности. Это означает, что для получения абсолютно защищенных планов не требуются стохастические симуляции Монте-Карло — достаточно один раз запустить стандартный конический решатель.

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

Список литературы:
1. Ben-Tal A., El Ghaoui L., Nemirovski A. Robust Optimization. — Princeton University Press, 2009.
2. Bertsimas D., Sim M. The Price of Robustness. — Operations Research, 2004.
3. Немировский А.С. Линейные матричные неравенства в теории управления. — М.: ФАЗИС, 1998.