Математическое программирование с ограничениями взаимодополняемости (MPEC)

Алгебраически ограничение взаимодополняемости записывается как скалярное произведение: x * y = 0, при условии, что x >= 0 и y >= 0. В физике это описывает контактную задачу: если две детали не соприкасаются (зазор x > 0), то сила контактного давления (y) строго равна нулю. Если давление возникло (y > 0), то детали плотно прижаты друг к другу (зазор x = 0). В двухуровневом программировании (Bilevel Programming) условия взаимодополняемости появляются из условий Каруша-Куна-Таккера (KKT) для нижней задачи оптимизации (произведение множителя Лагранжа на активное ограничение). Проблема заключается в том, что функция f(x,y) = x*y является сильно невыпуклой (седлообразной), а область допустимых решений представляет собой объединение гиперплоскостей (осей координат), не имеющее внутренних точек.

Эта патологическая геометрия приводит к фатальным последствиям для вычислительной математики. Задачи MPEC нарушают так называемое Условие регулярности Мангасаряна-Фромовица (MFCQ) во всех допустимых точках! Это означает, что классический метод множителей Лагранжа и теорема ККТ становятся алгебраически недействительными: множители Лагранжа могут вообще не существовать или уходить в бесконечность. Любой стандартный алгоритм нелинейного программирования (NLP), основанный на градиентах (SQP или методы внутренней точки), попытавшись решить MPEC «в лоб», мгновенно потерпит крах, зациклится или выдаст случайный математический мусор из-за сингулярности матриц Якоби.

Для преодоления этого алгебраического тупика исследователи операций разработали методы регуляризации и релаксации (Сглаживания). Самым известным подходом является метод релаксации Схольтеса (Scholtes Relaxation). Жесткое уравнение взаимодополняемости (x * y = 0) заменяется на ослабленное неравенство: (x * y <= t), где t — крошечный положительный параметр сглаживания. Это микроскопическое послабление мгновенно восстанавливает условие регулярности (MFCQ), и область допустимых решений становится слегка выпуклой («раздувается» в уголках). Алгоритм решает серию таких сглаженных задач, итеративно уменьшая параметр t до нуля. Доказано, что последовательность решений этих искусственных задач строго сходится к истинному (C-стационарному) локальному оптимуму оригинальной задачи MPEC.

Другим мощным подходом является переформулировка MPEC в задачу Смешанного целочисленного линейного программирования (MILP) с помощью метода Big-M. Уравнение x * y = 0 заменяется введением новой бинарной переменной z. Система переписывается в виде двух неравенств: x <= M * z и y <= M * (1 - z), где M — искусственное, заведомо огромное число (Большое М). Если z = 0, то x обязан стать нулем (а y может быть любым в пределах М). Если z = 1, то y становится нулем. Этот метод идеально точен, но комбинаторный взрыв бинарных переменных делает его применимым только для небольших систем. Сегодня гибридные солверы (такие как KNITRO) виртуозно балансируют между сглаживанием и целочисленной ветрификацией, позволяя правительствам оптимизировать равновесие на многомиллиардных энергетических и квотных биржах.