Стохастическое программирование: оптимизация с вероятностными ограничениями (Chance-Constrained)

Математическая философия Chance-Constrained Programming заключается в замене жестких алгебраических неравенств на вероятностные утверждения. В классической модели ограничение выглядит как A*x <= B, где параметры строго детерминированы. Если матрица A или вектор B содержат случайные величины, мы не можем требовать выполнения неравенства в 100 процентах случаев (это привело бы к отсутствию допустимых решений). В вероятностной модели неравенство записывается как P(A*x <= B) >= 1 - Альфа, где Альфа — заранее заданный, очень маленький уровень риска. Это означает, что математическая модель обязана найти такое решение x, при котором случайные факторы нарушат ограничение не чаще, чем в Альфа процентах случаев (допустимый уровень отказа).

Главной вычислительной проблемой метода является преобразование этого вероятностного неравенства в детерминированный эквивалент, который мог бы решить компьютер. Если случайными являются только элементы правой части (вектора B), а их закон распределения (например, нормальный) известен, задача сводится к использованию квантилей. Вероятностное ограничение алгебраически трансформируется в жесткое линейное неравенство A*x <= F_inv(1 - Альфа), где F_inv — обратная функция (квантиль) кумулятивного распределения вектора B. В этом частном случае стохастическая задача мгновенно схлопывается в элементарную задачу линейного программирования, решаемую обычным симплекс-методом.

Однако, если случайными являются элементы технологической матрицы A (левой части), ситуация катастрофически усложняется. Умножение случайной величины на искомую переменную x делает дисперсию результата зависимой от самого решения. Детерминированный эквивалент такого ограничения перестает быть линейным; он превращается в нелинейное неравенство второго порядка, включающее квадратные корни из квадратичных форм (описывающих ковариационную матрицу случайных величин). К счастью, полученная область допустимых решений остается выпуклой, что позволяет эффективно решать задачу с помощью методов конического квадратичного программирования (SOCP) и алгоритмов внутренней точки.

В современном финансовом инжиниринге оптимизация с вероятностными ограничениями служит математической основой для управления рисками по стандарту Базель III. Концепция Value-at-Risk (VaR) — это не что иное, как переформулированное вероятностное ограничение, требующее, чтобы убытки портфеля не превысили определенного порога с заданной вероятностью (например, 99 процентов). В энергетике этот же алгоритм управляет загрузкой гидроэлектростанций: диспетчер максимизирует выработку энергии при вероятностном ограничении, гласящем, что риск падения уровня воды в водохранилище ниже критической отметки из-за случайной засухи не должен превышать одного процента в год.