Двухуровневое программирование (Bilevel Programming): оптимизация иерархических систем

В архитектуре двухуровневой модели выделяют Верхний уровень (Лидер) и Нижний уровень (Последователь). Эта структура является математическим обобщением динамической игры Штакельберга. Лидер выбирает вектор переменных x, стремясь максимизировать свою целевую функцию F(x, y). Но переменная y (реакция последователя) не подвластна лидеру. Последователь наблюдает выбор x и находит свой вектор y, решая свою собственную внутреннюю задачу максимизации функции f(x, y). Главная сложность для Лидера заключается в том, что его область допустимых решений не задана явными алгебраическими уравнениями: она формируется множеством рациональных ответов (оптимумов) подзадачи Последователя для каждого возможного значения x.

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

Главным аналитическим методом решения двухуровневых задач является замена задачи нижнего уровня на ее условия оптимальности Каруша-Куна-Таккера (KKT). Поскольку Последователь решает стандартную задачу оптимизации, его оптимальный ответ y обязан удовлетворять системе уравнений и неравенств ККТ. Математики берут эти условия ККТ и просто вставляют их как дополнительные ограничения в задачу Лидера. В результате вложенная структура (задача в задаче) разрушается, и модель превращается в одноуровневую математическую программу с ограничениями взаимодополняемости (Mathematical Program with Equilibrium Constraints, MPEC). Ключевым препятствием в MPEC остается условие дополняющей нежесткости (произведение двух переменных равно нулю), которое нарушает стандартные квалификации ограничений и требует применения методов штрафных функций или релаксации Схольтеса.

Практическая ценность двухуровневого программирования перекрывает любые вычислительные трудности. Этот аппарат применяется при проектировании тарифов в электроэнергетике: регулятор (Лидер) задает цены на выбросы углекислого газа, а независимые электростанции (Последователи) оптимизируют выработку энергии. В транспортной инженерии (Network Design Problem) мэрия города решает, какие новые дороги построить в рамках фиксированного бюджета, понимая, что водители впоследствии перераспределятся по сети согласно эгоистичному равновесию Вардропа. Эти модели доказывают, что эффективное государственное управление невозможно без жесткого математического прогнозирования рациональных реакций децентрализованного рынка.