Задача. Минимизировать функцию $f:{\mathbb{R}}^n\to \mathbb{R}$ при равенствах-ограничениях $g_i(x)=0,i=1,\dots ,m$. Обозначим вектор ограничений $g=(g_1,\dots ,g_m{)}^T$.
1) Метод множителей Лагранжа — формулировка
- Лагранжиан
$$L(x,\lambda )=f(x)-\sum _{i=1}^m{\lambda }_i{g}_i(x),$$ где $\lambda =({\lambda }_1,\dots ,{\lambda }_m)$ — множители Лагранжа.
- Необходимые условия стационарности (первые производные):
$${\nabla }_{x}L(x^{\ast },{\lambda }^{\ast })=\nabla f(x^{\ast })-\sum _{i=1}^m{\lambda }_i^{\ast }\nabla g_i(x^{\ast })=0,g(x^{\ast })=0.$$ Иными словами градиент $f$ в точке экстремума лежит в линейной оболочке градиентов ограничений.
2) Критерии применимости (условия корректности вывода множителей)
- Стандартное условие (LICQ): матрица Якоби $Dg(x^{\ast })=[\nabla g_1(x^{\ast }),\dots ,\nabla g_m(x^{\ast }){]}^T$ имеет ранг $m$. Тогда при достаточно гладких $f,g_i$ любая точка локального экстремума удовлетворяет уравнениям Лагранжа (существуют ${\lambda }^{\ast }$), и ${\lambda }^{\ast }$ уникальны.
- Если LICQ не выполняется, стандартная теорема о существовании множителей не гарантирует $\lambda$. Могут существовать множители, но они не уникальны и/или дополнительные квалификационные условия (MFCQ, CRCQ и т.д.) нужны для теоретического обеспечения.
3) Вторые производные — достаточное и необходимое условия
- Обозначим матрицу Гессиана Лагранжиана по $x$:
$$H={\nabla }_{xx}^{2}L(x^{\ast },{\lambda }^{\ast })={\nabla }^{2}f(x^{\ast })-\sum _{i=1}^m{\lambda }_i^{\ast }{\nabla }^2{g}_i(x^{\ast }).$$ - Ещё определим касательное подпространство к многообразию ограничений:
$$T=\{v\in {\mathbb{R}}^n:Dg(x^{\ast })v=0\}(\text{то есть}\nabla g_i(x^{\ast }{)}^{T}v=0,\forall i).$$ - Необходимое условие: для любого $v\in T$ выполняется
$$v^{T}Hv\ge 0.$$ - Достаточное условие строгого локального минимума: для любого ненулевого $v\in T$ $$v^{T}Hv>0.$$ - Альтернативно используют бордерную (bordered) матрицу, но практичнее проверять положительную определённость квадратичной формы $v^{T}Hv$ на $T$.
4) Анализ вырождения ограничений (ранг $Dg(x^{\ast })<m$)
Классификация и приёмы:
- Случай 1 — некоторые ограничения избыточны (линейно зависимые градиенты), но множество допустимых точек локально всё ещё гладкое многообразие кодимензии $r=\mathrm{rank}Dg(x^{\ast })$. Действия: исключить зависимые ограничения (найти независимый набор), применить метод Лагранжа к независимому набору. Множители при этом не уникальны в исходной постановке.
- Случай 2 — ранга нет (не удаётся получить локальную параметризацию через неявную функцию): множество допустимых точек может иметь сингулярность (узел, самопересечение, кут). Тогда:
- не действует обычная неявная функция; нельзя гарантировать существование $\lambda$;
- применяют параметризацию вручную (если возможно) и сводят задачу к неограниченному минимуму по параметрам;
- если градиенты исчезают, нужно исследовать старшие по порядку члены разложения Тейлора вдоль возможных направлений: найти наименьший порядок $k$ с ненулевыми производными и сравнить соответствующие однородные формы (анализ высших порядков).
- Общие методы при вырождении: удалить избыточные ограничения; перейти к параметрическому описанию допустимого множества; использовать метод штрафов/аугментированные Лагранжианы для численной аппроксимации; применять общие условные оптимизационные критерии (KKT) с соответствующими квалификационными условиями.
5) Практическая последовательность решения
- Записать $L$, решить систему ${\nabla }_{x}L=0,g=0$. Проверить ранг $Dg$ в найденных точках.
- Если $\mathrm{rank}Dg=m$, применить вторые условия на $T$ (проверить $v^{T}Hv$ на $T$).
- Если ранг меньше — попытаться устранить зависимость ограничений или параметризовать множество ограничений; если это невозможно, исследовать старшие порядки в направлении касательной (анализ по Тейлору).
Кратко: метод множителей Лагранжа даёт необходимые условия при гладкости; для гарантии существования и уникальности множителей нужна независимость градиентов (LICQ). Для достаточности минимума проверяют положительную определённость Гессиана Лагранжиана на касательном подпространстве. Вырождение градиентов требует устранения избыточности, параметризации или анализа высших порядков.