Множитель Лагранжа

«Функция Лагранжа» перенаправляется сюда. Не путать с лагранжианом (физика) .

В математической оптимизации метод множителей Лагранжа представляет собой стратегию поиска локальных максимумов и минимумов функции, подчиняющейся ограничениям уравнения (т. е. при условии, что одно или несколько уравнений должны точно удовлетворяться выбранными значениями переменных ). ). Он назван в честь математика Жозефа-Луи Лагранжа .

Резюме и обоснование

Основная идея состоит в том, чтобы преобразовать задачу с ограничениями в такую ​​форму, в которой все еще можно было бы применить тест производной задачи без ограничений. Связь между градиентом функции и градиентами ограничений вполне естественно приводит к переформулировке исходной задачи, известной как функция Лагранжа или лагранжиан. В общем случае лагранжиан определяется как $${\mathcal {L}}(x,\lambda )\equiv f(x)+\langle \lambda ,g(x)\rangle$$ для функций $f,g$; $\lambda$ называется множителем Лагранжа.

В простых случаях, когда внутренний продукт определяется как скалярное произведение , лагранжиан равен $${\mathcal {L}}(x,\lambda )\equiv f(x)+\lambda \cdot g(x)$$

Метод можно резюмировать следующим образом: чтобы найти максимум или минимум функции $f$ подчиняется ограничению равенства $g(x)=0$, найдите стационарные точки ${\mathcal {L}}$ рассматривать как функцию $x$ и множитель Лагранжа $\lambda ~$. Это означает, что все частные производные должны быть равны нулю, включая частную производную по $\lambda ~$.

${\frac {\partial {\mathcal {L}}}{\partial x}}=0$   и   ${\frac {\ \partial {\mathcal {L}}\ }{\partial \lambda }}=0\ ;$

или эквивалентно

${\frac {\partial f(x)}{\partial x}}+\lambda \cdot {\frac {\partial g(x)}{\partial x}}=0$   и  $g(x)=0~.$

Решение, соответствующее исходной оптимизации с ограничениями, всегда является седловой точкой функции Лагранжа: которые можно выделить среди стационарных точек по определенности окаймленной матрицы Гессе .

Большим преимуществом этого метода является то, что он позволяет решать оптимизацию без явной параметризации ограничений. В результате метод множителей Лагранжа широко используется для решения сложных задач оптимизации с ограничениями. Далее метод множителей Лагранжа обобщается условиями Каруша–Куна–Таккера , которые также могут учитывать ограничения-неравенства вида $h(\mathbf {x} )\leq c$ для заданной константы $c$.

Заявление

Следующее утверждение известно как теорема о множителе Лагранжа.

Позволять $f:\mathbb {R} ^{n}\to \mathbb {R}$ быть целевой функцией, $g:\mathbb {R} ^{n}\to \mathbb {R} ^{c}$ быть функцией ограничений, обе принадлежащие $C^{1}$ (то есть иметь непрерывные первые производные). Позволять $x_{\star }$ — оптимальное решение следующей задачи оптимизации такое, что для матрицы частных производных ${\Bigl [}\operatorname {D} g(x_{\star }){\Bigr ]}_{j,k}={\frac {\ \partial g_{j}\ }{\partial x_{k}}}$, $\operatorname {rank} (\operatorname {D} g(x_{\star }))=c\leq n$:

$${\begin{aligned}&{\text{maximize }}f(x)\\&{\text{subject to: }}g(x)=0\end{aligned}}$$

Тогда существует единственный множитель Лагранжа $\lambda _{\star }\in \mathbb {R} ^{c}$ такой, что $\operatorname {D} f(x_{\star })=\lambda _{\star }^{\mathsf {T}}\operatorname {D} g(x_{\star })~.$ (Обратите внимание, что это несколько традиционная вещь, когда $\lambda _{\star }$ явно рассматривается как вектор-столбец, чтобы гарантировать совпадение размеров. Но с таким же успехом мы могли бы сделать это просто вектором-строкой, не прибегая к транспонированию).

Теорема о множителе Лагранжа утверждает, что в любом локальном максимуме (или минимуме) функции, оцениваемой при ограничениях равенства, если применяется квалификация ограничения (поясняется ниже), то градиент функции (в этой точке) может быть выражен как линейная комбинация градиентов ограничений (в этой точке), при этом множители Лагранжа действуют как коэффициенты . Это эквивалентно утверждению, что любое направление, перпендикулярное всем градиентам ограничений, также перпендикулярно градиенту функции. Или еще сказать, что по направлению производная функции равна 0 во всех возможных направлениях.

Единое ограничение

Рисунок 1: Красная кривая показывает ограничение g ( x , y ) = c . Синие кривые — это контуры f ( x , y ) . Точка, в которой красное ограничение по касательной касается синего контура, является максимумом f ( x , y ) вдоль ограничения, поскольку d ₁ > d ₂ .

Для случая только одного ограничения и только двух переменных выбора (как показано на рисунке 1), рассмотрим задачу оптимизации $${\begin{aligned}{\underset {x,y}{\text{maximize}}}\quad &f(x,y)\\{\text{subject to}}\quad &g(x,y)=0.\end{aligned}}$$ (Иногда аддитивная константа отображается отдельно, а не включается в $g$, и в этом случае ограничение записывается $g(x,y)=c,$ как на рисунке 1.) Мы предполагаем, что оба $f$ и $g$ имеют непрерывные первые частные производные . Вводим новую переменную ( $\lambda$), называемый множителем Лагранжа (или неопределенным множителем Лагранжа ), и изучите функцию Лагранжа (или лагранжиан или выражение Лагранжа ), определяемую формулой $${\mathcal {L}}(x,y,\lambda )=f(x,y)+\lambda \cdot g(x,y),$$ где $\lambda$ термин может быть добавлен или вычтен. Если $f(x_{0},y_{0})$ это максимум $f(x,y)$ для исходной задачи с ограничениями и $\nabla g(x_{0},y_{0})\neq 0,$ тогда существует $\lambda _{0}$ такой, что ( $x_{0},y_{0},\lambda _{0}$) является стационарной точкой для функции Лагранжа (стационарные точки — это те точки, в которых первые частные производные ${\mathcal {L}}$ равны нулю). Предположение $\nabla g\neq 0$ называется квалификацией ограничений. Однако не все стационарные точки дают решение исходной задачи, поскольку метод множителей Лагранжа дает лишь необходимое условие оптимальности в задачах с ограничениями. Достаточные условия для минимума или максимума также существуют , но если конкретное решение-кандидат удовлетворяет достаточным условиям, гарантируется только то, что это решение является лучшим локально , то есть оно лучше, чем любые допустимые близлежащие точки. Глобальный . оптимум можно найти путем сравнения значений исходной целевой функции в точках, удовлетворяющих необходимым и локально достаточным условиям

Метод множителей Лагранжа основан на интуитивном понимании того, что в максимуме f ( x , y ) не может увеличиваться в направлении любой такой соседней точки, которая также имеет g = 0 . Если бы это было так, мы могли бы идти по g = 0 , чтобы подняться выше, а это означало бы, что отправная точка на самом деле не была максимальной. С этой точки зрения, это точный аналог проверки того, равна ли производная неограниченной функции 0 , то есть мы проверяем, что производная по направлению равна 0 в любом соответствующем (жизнеспособном) направлении.

Мы можем визуализировать контуры f , заданные как f ( x , y ) = d для различных значений d , и контур g , заданный g ( x , y ) = c .

Предположим, мы идем по контурной линии с g = c . Нас интересует поиск точек, в которых f почти не меняется при ходьбе, поскольку эти точки могут быть максимумами.

Это может произойти двумя способами:

1. Мы могли бы прикоснуться к контурной линии f , поскольку по определению f не меняется, когда мы идем по ее контурным линиям. Это означало бы, что касательные к контурным линиям f и g здесь параллельны.
2. Мы достигли «ровной» части f , что означает, что f не меняется ни в каком направлении.

Чтобы проверить первую возможность (мы касаемся контурной линии f ), обратите внимание, что, поскольку градиент функции перпендикулярен контурным линиям, касательные к контурным линиям f и g параллельны тогда и только тогда, когда градиенты f и g параллельны. Таким образом, нам нужны точки ( x , y ) , где g ( x , y ) = c и $$\nabla _{x,y}f=\lambda \,\nabla _{x,y}g,$$ для некоторых $\lambda$

где $$\nabla _{x,y}f=\left({\frac {\partial f}{\partial x}},{\frac {\partial f}{\partial y}}\right),\qquad \nabla _{x,y}g=\left({\frac {\partial g}{\partial x}},{\frac {\partial g}{\partial y}}\right)$$ являются соответствующими градиентами. Константа $\lambda$ требуется, поскольку, хотя два вектора градиента параллельны, величины векторов градиента обычно не равны. Эта константа называется множителем Лагранжа. (В некоторых конвенциях $\lambda$ предшествует знак минус).

Обратите внимание, что этот метод также решает вторую возможность, что f является уровнем: если f является уровнем, то его градиент равен нулю, и установка $\lambda =0$ является решением независимо от $\nabla _{x,y}g$.

Чтобы объединить эти условия в одно уравнение, введем вспомогательную функцию $${\mathcal {L}}(x,y,\lambda )\equiv f(x,y)+\lambda \cdot g(x,y)\,,$$ и решить $$\nabla _{x,y,\lambda }{\mathcal {L}}(x,y,\lambda )=0~.$$

Обратите внимание, что это равносильно решению трех уравнений с тремя неизвестными. Это метод множителей Лагранжа.

Обратите внимание, что $\ \nabla _{\lambda }{\mathcal {L}}(x,y,\lambda )=0\$ подразумевает $\ g(x,y)=0\ ,$ как частная производная ${\mathcal {L}}$ относительно $\lambda$ является $\ g(x,y)~.$

Подводя итог $$\nabla _{x,y,\lambda }{\mathcal {L}}(x,y,\lambda )=0\iff {\begin{cases}\nabla _{x,y}f(x,y)=-\lambda \,\nabla _{x,y}g(x,y)\\g(x,y)=0\end{cases}}$$

Метод легко обобщается на функции $n$ переменные $$\nabla _{x_{1},\dots ,x_{n},\lambda }{\mathcal {L}}(x_{1},\dots ,x_{n},\lambda )=0$$ что представляет собой решение n + 1 уравнений с n + 1 неизвестными.

Ограниченные экстремумы f являются критическими точками лагранжиана ${\mathcal {L}}$, но они не обязательно являются локальными экстремумами ${\mathcal {L}}$ (см. § Пример 2 ниже).

Можно переформулировать лагранжиан как гамильтониан , и в этом случае решения являются локальными минимумами гамильтониана. Это сделано в теории оптимального управления , в форме принципа минимума Понтрягина .

Трудности для численной оптимизации создает и тот факт, что решения метода множителей Лагранжа не обязательно являются экстремумами лагранжиана. Эту проблему можно решить, минимизировав величину градиента лагранжиана, поскольку эти минимумы совпадают с нулями величины, как показано в Примере 5: Численная оптимизация .

Множественные ограничения

Рисунок 2: Параболоид, ограниченный двумя пересекающимися линиями.

Рисунок 3: Контурная карта рисунка 2.

Метод множителей Лагранжа можно расширить для решения задач с несколькими ограничениями, используя аналогичный аргумент. Рассмотрим параболоид , на который наложены два ограничения на линии, пересекающиеся в одной точке. Поскольку это единственное возможное решение, эта точка, очевидно, является ограниченным экстремумом. Однако набора уровень $f$ явно не параллелен ни одному из ограничений в точке пересечения (см. рисунок 3); вместо этого это линейная комбинация градиентов двух ограничений. В случае множественных ограничений именно это мы и ищем в целом: метод Лагранжа ищет точки, не в которых градиент $f$ обязательно кратен градиенту любого отдельного ограничения, но в котором он представляет собой линейную комбинацию градиентов всех ограничений.

Конкретно, предположим, что у нас есть $M$ ограничений и движемся по множеству точек, удовлетворяющих $g_{i}(\mathbf {x} )=0,i=1,\dots ,M\,.$ Каждая точка $\mathbf {x}$ на контуре заданной ограничительной функции $g_{i}$ имеет пространство допустимых направлений: пространство векторов, перпендикулярных $\nabla g_{i}(\mathbf {x} )\,.$ Таким образом, набор направлений, разрешенных всеми ограничениями, представляет собой пространство направлений, перпендикулярных всем градиентам ограничений. Обозначим это пространство допустимых ходов через $\ A\$ и обозначим диапазон градиентов ограничений через $S\,.$ Затем $A=S^{\perp }\,,$ пространство векторов, перпендикулярных каждому элементу $S\,.$

Нас по-прежнему интересует поиск точек, где $f$ не меняется по мере нашего продвижения, поскольку эти точки могут быть (ограниченными) экстремумами. Поэтому мы ищем $\mathbf {x}$ так, что любое допустимое направление движения в сторону от $\mathbf {x}$ перпендикулярен $\nabla f(\mathbf {x} )$ (иначе мы могли бы увеличить $f$ двигаясь в этом допустимом направлении). Другими словами, $\nabla f(\mathbf {x} )\in A^{\perp }=S\,.$ Таким образом, существуют скаляры $\lambda _{1},\lambda _{2},\ \dots ,\lambda _{M}$ такой, что $$\nabla f(\mathbf {x} )=\sum _{k=1}^{M}\lambda _{k}\,\nabla g_{k}(\mathbf {x} )\quad \iff \quad \nabla f(\mathbf {x} )-\sum _{k=1}^{M}{\lambda _{k}\nabla g_{k}(\mathbf {x} )}=0~.$$

Эти скаляры являются множителями Лагранжа. Теперь у нас есть $M$ из них по одному на каждое ограничение.

Как и раньше, введем вспомогательную функцию $${\mathcal {L}}\left(x_{1},\ldots ,x_{n},\lambda _{1},\ldots ,\lambda _{M}\right)=f\left(x_{1},\ldots ,x_{n}\right)-\sum \limits _{k=1}^{M}{\lambda _{k}g_{k}\left(x_{1},\ldots ,x_{n}\right)}\$$ и решить $$\nabla _{x_{1},\ldots ,x_{n},\lambda _{1},\ldots ,\lambda _{M}}{\mathcal {L}}(x_{1},\ldots ,x_{n},\lambda _{1},\ldots ,\lambda _{M})=0\iff {\begin{cases}\nabla f(\mathbf {x} )-\sum _{k=1}^{M}{\lambda _{k}\,\nabla g_{k}(\mathbf {x} )}=0\\g_{1}(\mathbf {x} )=\cdots =g_{M}(\mathbf {x} )=0\end{cases}}$$ что равносильно решению $n+M$ уравнения в $\ n+M\$ неизвестные.

Допущение квалификации ограничения при наличии нескольких ограничений заключается в том, что градиенты ограничений в соответствующей точке линейно независимы.

Современная формулировка с помощью дифференцируемых многообразий

Задачу поиска локальных максимумов и минимумов с учетом ограничений можно обобщить до поиска локальных максимумов и минимумов на дифференцируемом многообразии. $\ M~.$ В дальнейшем не обязательно, чтобы $M$ быть евклидовым пространством или даже римановым многообразием. Все проявления градиента $\ \nabla \$ (который зависит от выбора римановой метрики) можно заменить внешней производной $\ \operatorname {d} ~.$

Единое ограничение

Позволять $\ M\$ быть гладким многообразием размерности $\ m~.$ Предположим, что мы хотим найти стационарные точки $\ x\$ гладкой функции $\ f:M\to \mathbb {R} \$ при ограничении подмногообразия $\ N\$ определяется $\ g(x)=0\ ,$ где $\ g:M\to \mathbb {R} \$ — гладкая функция, для которой 0 — регулярное значение .

Позволять $\ \operatorname {d} f\$ и $\ \operatorname {d} g\$ быть внешними производными от $\ f\$ и $\ g\$. Стационарность для ограничения $\ f|_{N}\$ в $\ x\in N\$ означает $\ \operatorname {d} (f|_{N})_{x}=0~.$ Аналогично, ядро $\ \ker(\operatorname {d} f_{x})\$ содержит $\ T_{x}N=\ker(\operatorname {d} g_{x})~.$ Другими словами, $\ \operatorname {d} f_{x}\$ и $\ \operatorname {d} g_{x}\$ являются пропорциональными 1-формами. Для этого необходимо и достаточно, чтобы следующая система $\ {\tfrac {1}{2}}m(m-1)\$ уравнения имеют место: $$\operatorname {d} f_{x}\wedge \operatorname {d} g_{x}=0\in \Lambda ^{2}(T_{x}^{\ast }M)$$ где $\ \wedge \$ обозначает внешний продукт . Стационарные точки $\ x\$ являются решениями приведенной выше системы уравнений плюс ограничение $\ g(x)=0~.$ Обратите внимание, что $\ {\tfrac {1}{2}}m(m-1)\$ уравнения не являются независимыми, так как левая часть уравнения принадлежит подмногообразию $\ \Lambda ^{2}(T_{x}^{\ast }M)\$ состоящее из разложимых элементов .

В этой формулировке нет необходимости явно находить множитель Лагранжа, число $\ \lambda \$ такой, что $\ \operatorname {d} f_{x}=\lambda \cdot \operatorname {d} g_{x}~.$

Множественные ограничения

Позволять $\ M\$ и $\ f\$ быть таким же, как в приведенном выше разделе в отношении случая одного ограничения. Вместо функции $g$ описано там, теперь рассмотрим гладкую функцию $\ G:M\to \mathbb {R} ^{p}(p>1)\ ,$ с функциями компонентов $\ g_{i}:M\to \mathbb {R} \ ,$ для чего $0\in \mathbb {R} ^{p}$ это обычное значение . Позволять $N$ быть подмногообразием $\ M\$ определяется $\ G(x)=0~.$

$\ x\$ является стационарной точкой $f|_{N}$ тогда и только тогда, когда $\ \ker(\operatorname {d} f_{x})\$ содержит $\ \ker(\operatorname {d} G_{x})~.$ Для удобства пусть $\ L_{x}=\operatorname {d} f_{x}\$ и $\ K_{x}=\operatorname {d} G_{x}\ ,$ где $\ \operatorname {d} G$ обозначает касательное отображение или якобиан $\ TM\to T\mathbb {R} ^{p}~$ ( $\ T_{x}\mathbb {R} ^{p}$ может быть канонически отождествлен с $\ \mathbb {R} ^{p}$). Подпространство $\ker(K_{x})$ имеет размерность меньшую, чем у $\ker(L_{x})$, а именно $\ \dim(\ker(L_{x}))=n-1\$ и $\ \dim(\ker(K_{x}))=n-p~.$ $\ker(K_{x})$ принадлежит $\ \ker(L_{x})\$ тогда и только тогда, когда $L_{x}\in T_{x}^{\ast }M$ принадлежит образу $\ K_{x}^{\ast }:\mathbb {R} ^{p\ast }\to T_{x}^{\ast }M~.$ С вычислительной точки зрения условие состоит в том, что $L_{x}$ принадлежит пространству строк матрицы $\ K_{x}\ ,$ или, что эквивалентно, пространство столбцов матрицы $K_{x}^{\ast }$ (транспонирование). Если $\ \omega _{x}\in \Lambda ^{p}(T_{x}^{\ast }M)\$ обозначает внешнее произведение столбцов матрицы $\ K_{x}^{\ast }\ ,$ стационарное состояние для $\ f|_{N}\$ в $\ x\$ становится $$L_{x}\wedge \omega _{x}=0\in \Lambda ^{p+1}\left(T_{x}^{\ast }M\right)$$ Еще раз: в этой формулировке нет необходимости явно находить множители Лагранжа, числа $\ \lambda _{1},\ldots ,\lambda _{p}\$ такой, что $$\ \operatorname {d} f_{x}=\sum _{i=1}^{p}\lambda _{i}\operatorname {d} (g_{i})_{x}~.$$

Интерпретация множителей Лагранжа

В этом разделе мы модифицируем уравнения ограничений в форме $g_{i}({\bf {x}})=0$ в форму $\ g_{i}({\bf {x}})=c_{i}\ ,$ где $\ c_{i}\$ — m вещественные константы, которые считаются дополнительными аргументами выражения Лагранжа ${\mathcal {L}}$.

Часто множители Лагранжа интерпретируются как некоторая процентная величина. Например, параметризовав контурную линию ограничения, то есть, если выражение Лагранжа равно $${\begin{aligned}&{\mathcal {L}}(x_{1},x_{2},\ldots ;\lambda _{1},\lambda _{2},\ldots ;c_{1},c_{2},\ldots )\\[4pt]={}&f(x_{1},x_{2},\ldots )+\lambda _{1}(c_{1}-g_{1}(x_{1},x_{2},\ldots ))+\lambda _{2}(c_{2}-g_{2}(x_{1},x_{2},\dots ))+\cdots \end{aligned}}$$ затем $$\ {\frac {\partial {\mathcal {L}}}{\partial c_{k}}}=\lambda _{k}~.$$

Итак, λ _k — скорость изменения оптимизируемой величины в зависимости от параметра ограничения. Например, в лагранжевой механике уравнения движения выводятся путем нахождения стационарных точек действия , интеграла по времени от разницы между кинетической и потенциальной энергией. Таким образом, силу, действующую на частицу вследствие скалярного потенциала F = −∇ V , можно интерпретировать как множитель Лагранжа, определяющий изменение действия (переход потенциала в кинетическую энергию) после изменения ограниченной траектории частицы. В теории управления это формулируется вместо этого как уравнения стоимости .

Более того, согласно теореме о конверте оптимальное значение множителя Лагранжа интерпретируется как предельное влияние соответствующей константы ограничения на оптимально достижимое значение исходной целевой функции: Если мы обозначим оптимальные значения звездочкой ( $\star$), то можно показать, что $${\frac {\ \operatorname {d} f\left(\ x_{1\star }(c_{1},c_{2},\dots ),\ x_{2\star }(c_{1},c_{2},\dots ),\ \dots \ \right)\ }{\operatorname {d} c_{k}}}=\lambda _{\star k}~.$$

Например, в экономике оптимальная прибыль игрока рассчитывается при условии ограниченного пространства действий, где множитель Лагранжа — это изменение оптимального значения целевой функции (прибыли) вследствие ослабления заданного ограничения (например, за счет изменение дохода); в таком контексте $\ \lambda _{\star k}\$ — это предельная стоимость ограничения, называемая теневой ценой .

Достаточные условия

Основная статья: Гессен с границей

Достаточные условия для ограниченного локального максимума или минимума могут быть сформулированы в терминах последовательности главных миноров (определителей выровненных в верхнем левом углу подматриц) граничной матрицы Гессе вторых производных выражения Лагранжа.

Примеры

Пример 1

Иллюстрация задачи оптимизации с ограничениями 1

Предположим, мы хотим максимизировать $\ f(x,y)=x+y\$ с учетом ограничения $\ x^{2}+y^{2}=1~.$ является Допустимым множеством единичный круг, а множествами уровня f являются диагональные линии (с наклоном −1), поэтому мы можем видеть графически, что максимум возникает при $\ \left({\tfrac {1}{\sqrt {2}}},{\tfrac {1}{\sqrt {2}}}\right)\ ,$ и что минимум происходит при $\ \left(-{\tfrac {1}{\sqrt {2}}},-{\tfrac {1}{\sqrt {2}}}\right)~.$

Для метода множителей Лагранжа ограничение имеет вид $$g(x,y)=x^{2}+y^{2}-1=0\ ,$$ следовательно, функция Лагранжа, $${\begin{aligned}{\mathcal {L}}(x,y,\lambda )&=f(x,y)+\lambda \cdot g(x,y)\\[4pt]&=x+y+\lambda (x^{2}+y^{2}-1)\ ,\end{aligned}}$$ это функция, эквивалентная $\ f(x,y)\$ когда $\ g(x,y)\$ установлено на 0 .

Теперь мы можем рассчитать градиент: $${\begin{aligned}\nabla _{x,y,\lambda }{\mathcal {L}}(x,y,\lambda )&=\left({\frac {\partial {\mathcal {L}}}{\partial x}},{\frac {\partial {\mathcal {L}}}{\partial y}},{\frac {\partial {\mathcal {L}}}{\partial \lambda }}\right)\\[4pt]&=\left(1+2\lambda x,1+2\lambda y,x^{2}+y^{2}-1\right)\ \color {gray}{,}\end{aligned}}$$ и поэтому: $$\nabla _{x,y,\lambda }{\mathcal {L}}(x,y,\lambda )=0\quad \Leftrightarrow \quad {\begin{cases}1+2\lambda x=0\\1+2\lambda y=0\\x^{2}+y^{2}-1=0\end{cases}}$$

Обратите внимание, что последнее уравнение является исходным ограничением.

Первые два уравнения дают $$x=y=-{\frac {1}{2\lambda }},\qquad \lambda \neq 0~.$$ Подставив в последнее уравнение, получим: $${\frac {1}{4\lambda ^{2}}}+{\frac {1}{4\lambda ^{2}}}-1=0\ ,$$ так $$\lambda =\pm {\frac {1}{\sqrt {2\ }}}\ ,$$ откуда следует, что стационарные точки ${\mathcal {L}}$ являются $$\left({\tfrac {\sqrt {2\ }}{2}},{\tfrac {\sqrt {2\ }}{2}},-{\tfrac {1}{\sqrt {2\ }}}\right),\qquad \left(-{\tfrac {\sqrt {2\ }}{2}},-{\tfrac {\sqrt {2\ }}{2}},{\tfrac {1}{\sqrt {2\ }}}\right)~.$$

Оценка целевой функции f в этих точках дает $$f\left({\tfrac {\sqrt {2\ }}{2}},{\tfrac {\sqrt {2\ }}{2}}\right)={\sqrt {2\ }}\ ,\qquad f\left(-{\tfrac {\sqrt {2\ }}{2}},-{\tfrac {\sqrt {2\ }}{2}}\right)=-{\sqrt {2\ }}~.$$

Таким образом, ограниченный максимум равен $\ {\sqrt {2\ }}\$ и ограниченный минимум равен $-{\sqrt {2}}$.

Пример 2

Иллюстрация задачи оптимизации 2 с ограничениями

Теперь мы модифицируем целевую функцию примера 1 так, чтобы минимизировать $\ f(x,y)=(x+y)^{2}\$ вместо $\ f(x,y)=x+y\ ,$ снова по кругу $\ g(x,y)=x^{2}+y^{2}-1=0~.$ Теперь наборы уровней $f$ по-прежнему являются линиями наклона −1, а точки на окружности, касающиеся этих наборов уровней, снова становятся $\ ({\sqrt {2}}/2,{\sqrt {2}}/2)\$ и $\ (-{\sqrt {2}}/2,-{\sqrt {2}}/2)~.$ Эти точки касания являются максимумами $\ f~.$

С другой стороны, минимумы происходят на уровне, установленном для $\ f=0\$ (поскольку по своей конструкции $\ f\$ не может принимать отрицательные значения), при $\ ({\sqrt {2}}/2,-{\sqrt {2}}/2)\$ и $\ (-{\sqrt {2}}/2,{\sqrt {2}}/2)\ ,$ где кривые уровня $\ f\$ не касаются ограничения. Условие, которое $\ \nabla _{x,y,\lambda }\left(f(x,y)+\lambda \cdot g(x,y)\right)=0\$ правильно определяет все четыре точки как экстремумы; минимумы характеризуются $\ \lambda =0\$ и максимумы по $\ \lambda =2~.$

Пример 3

Иллюстрация задачи ограниченной оптимизации 3 .

В этом примере рассматриваются более сложные вычисления, но это по-прежнему проблема с одним ограничением.

Предположим, кто-то хочет найти максимальные значения $$f(x,y)=x^{2}y$$ с тем условием, что $\ x\$- и $\ y\$-координаты лежат на окружности вокруг начала координат с радиусом $\ {\sqrt {3\ }}~.$ То есть при условии ограничения $$g(x,y)=x^{2}+y^{2}-3=0~.$$

Поскольку существует только одно ограничение, существует один множитель, скажем $\ \lambda ~.$

Ограничение $\ g(x,y)\$ тождественно равен нулю на окружности радиуса $\ {\sqrt {3\ }}~.$ Любое кратное $\ g(x,y)\$ может быть добавлен в $\ g(x,y)\$ уход $\ g(x,y)\$ неизменным в интересующей области (на круге, где выполняется наше исходное ограничение).

Применение обычного метода множителей Лагранжа дает $${\begin{aligned}{\mathcal {L}}(x,y,\lambda )&=f(x,y)+\lambda \cdot g(x,y)\\&=x^{2}y+\lambda (x^{2}+y^{2}-3)\ ,\end{aligned}}$$ из которого можно вычислить градиент: $${\begin{aligned}\nabla _{x,y,\lambda }{\mathcal {L}}(x,y,\lambda )&=\left({\frac {\partial {\mathcal {L}}}{\partial x}},{\frac {\partial {\mathcal {L}}}{\partial y}},{\frac {\partial {\mathcal {L}}}{\partial \lambda }}\right)\\&=\left(2xy+2\lambda x,x^{2}+2\lambda y,x^{2}+y^{2}-3\right)~.\end{aligned}}$$ И поэтому: $$\nabla _{x,y,\lambda }{\mathcal {L}}(x,y,\lambda )=0\quad \iff \quad {\begin{cases}2xy+2\lambda x=0\\x^{2}+2\lambda y=0\\x^{2}+y^{2}-3=0\end{cases}}\quad \iff \quad {\begin{cases}x(y+\lambda )=0&{\text{(i)}}\\x^{2}=-2\lambda y&{\text{(ii)}}\\x^{2}+y^{2}=3&{\text{(iii)}}\end{cases}}$$ (iii) является исходным ограничением. (i) подразумевает $\ x=0\$ или $\ \lambda =-y~.$ Если $x=0$ затем $\ y=\pm {\sqrt {3\ }}\$ согласно (iii) и, следовательно, $\ \lambda =0\$ из (ii). Если $\ \lambda =-y\ ,$ подстановка этого в (ii) дает $\ x^{2}=2y^{2}~.$ Подставив это в (iii) и решив $\ y\$ дает $\ y=\pm 1~.$ Таким образом, существует шесть критических точек $\ {\mathcal {L}}\ :$ $$({\sqrt {2\ }},1,-1);\quad (-{\sqrt {2\ }},1,-1);\quad ({\sqrt {2\ }},-1,1);\quad (-{\sqrt {2\ }},-1,1);\quad (0,{\sqrt {3\ }},0);\quad (0,-{\sqrt {3\ }},0)~.$$

Оценивая цель в этих точках, можно обнаружить, что $$f(\pm {\sqrt {2\ }},1)=2;\quad f(\pm {\sqrt {2\ }},-1)=-2;\quad f(0,\pm {\sqrt {3\ }})=0~.$$

Следовательно, целевая функция достигает глобального максимума (с учетом ограничений) при $\ (\pm {\sqrt {2\ }},1\ )$ и глобальный минимум в $\ (\pm {\sqrt {2\ }},-1)~.$ Суть $\ (0,{\sqrt {3\ }})\$ представляет собой локальный минимум $\ f\$ и $\ (0,-{\sqrt {3\ }})\$ является локальным максимумом $\ f\ ,$ что можно определить путем рассмотрения Гессе матрицы $\ {\mathcal {L}}(x,y,0)~.$

Обратите внимание, что пока $\ ({\sqrt {2\ }},1,-1)\$ является критической точкой $\ {\mathcal {L}}\ ,$ это не локальный экстремум $\ {\mathcal {L}}~.$ У нас есть $${\mathcal {L}}\left({\sqrt {2\ }}+\varepsilon ,1,-1+\delta \right)=2+\delta \left(\varepsilon ^{2}+\left(2{\sqrt {2\ }}\right)\varepsilon \right)~.$$

Учитывая любую окрестность $\ ({\sqrt {2\ }},1,-1)\ ,$ можно выбрать небольшой позитив $\ \varepsilon \$ и маленький $\ \delta \$ любого знака, чтобы получить $\ {\mathcal {L}}$ значения как больше, так и меньше $\ 2~.$ Это также можно увидеть из матрицы Гессе $\ {\mathcal {L}}\$ оценивается в этой точке (или даже в любой из критических точек), которая представляет собой неопределенную матрицу . Каждая из критических точек $\ {\mathcal {L}}\$ является седловой точкой $\ {\mathcal {L}}~.$

Пример 4 – Энтропия

Предположим, мы хотим найти дискретное распределение вероятностей в точках $\ \{p_{1},p_{2},\ldots ,p_{n}\}\$ с максимальной информационной энтропией . Это то же самое, что сказать, что мы хотим найти наименее структурированное распределение вероятностей в точках $\ \{p_{1},p_{2},\cdots ,p_{n}\}~.$ Другими словами, мы хотим максимизировать уравнение энтропии Шеннона : $$f(p_{1},p_{2},\ldots ,p_{n})=-\sum _{j=1}^{n}p_{j}\log _{2}p_{j}~.$$

Чтобы это было распределение вероятностей, сумма вероятностей $\ p_{i}\$ в каждой точке $\ x_{i}\$ должно равняться 1, поэтому наше ограничение: $$g(p_{1},p_{2},\ldots ,p_{n})=\sum _{j=1}^{n}p_{j}=1~.$$

Мы используем множители Лагранжа, чтобы найти точку максимальной энтропии: $\ {\vec {p}}^{\,*}\ ,$ по всем дискретным распределениям вероятностей $\ {\vec {p}}\$ на $\ \{x_{1},x_{2},\ldots ,x_{n}\}~.$ Мы требуем, чтобы: $$\left.{\frac {\partial }{\partial {\vec {p}}}}(f+\lambda (g-1))\right|_{{\vec {p}}={\vec {p}}^{\,*}}=0\ ,$$ что дает систему из n уравнений, $\ k=1,\ \ldots ,n\ ,$ такой, что: $$\left.{\frac {\partial }{\partial p_{k}}}\left\{-\left(\sum _{j=1}^{n}p_{j}\log _{2}p_{j}\right)+\lambda \left(\sum _{j=1}^{n}p_{j}-1\right)\right\}\right|_{p_{k}=p_{\star k}}=0~.$$

Проведя дифференцирование этих n уравнений, получим $$-\left({\frac {1}{\ln 2}}+\log _{2}p_{\star k}\right)+\lambda =0~.$$

Это показывает, что все $\ p_{\star k}\$ равны (так как зависят только от λ ). Используя ограничение $$\sum _{j}p_{j}=1\ ,$$ мы находим $$p_{\star k}={\frac {1}{n}}~.$$

Следовательно, равномерное распределение — это распределение с наибольшей энтропией среди распределений по n точкам.

Пример 5 – Численная оптимизация

Множители Лагранжа приводят к тому, что критические точки возникают в седловых точках (пример 5 ).

Величину градиента можно использовать для того, чтобы критические точки находились в локальных минимумах (Пример 5 ).

Критические точки лагранжиана возникают в седловых точках , а не в локальных максимумах (или минимумах). К сожалению, многие методы численной оптимизации, такие как восхождение на холм , градиентный спуск , некоторые квазиньютоновские методы и другие, предназначены для поиска локальных максимумов (или минимумов), а не седловых точек. По этой причине необходимо либо изменить формулировку, чтобы гарантировать, что это задача минимизации (например, путем экстремизации квадрата градиента лагранжиана , как показано ниже), либо использовать метод оптимизации, который находит стационарные точки (например, метод Ньютона без экстремума поиск строки ) и не обязательно экстремумов.

В качестве простого примера рассмотрим задачу нахождения значения x , которое минимизирует $\ f(x)=x^{2}\ ,$ ограничено так, что $\ x^{2}=1~.$ (Эта проблема несколько нетипична, поскольку этому ограничению удовлетворяют только два значения, но она полезна для иллюстративных целей, поскольку соответствующую функцию без ограничений можно визуализировать в трех измерениях.)

Используя множители Лагранжа, эту задачу можно преобразовать в задачу неограниченной оптимизации: $${\mathcal {L}}(x,\lambda )=x^{2}+\lambda (x^{2}-1)~.$$

Две критические точки возникают в седловых точках, где x = 1 и x = −1 .

Чтобы решить эту проблему с помощью метода численной оптимизации, мы должны сначала преобразовать эту проблему так, чтобы критические точки находились в локальных минимумах. Это делается путем вычисления величины градиента задачи неограниченной оптимизации.

Сначала мы вычисляем частную производную задачи без ограничений по каждой переменной: $${\begin{aligned}&{\frac {\partial {\mathcal {L}}}{\partial x}}=2x+2x\lambda \\[5pt]&{\frac {\partial {\mathcal {L}}}{\partial \lambda }}=x^{2}-1~.\end{aligned}}$$

Если целевая функция не является легко дифференцируемой, дифференциал по каждой переменной можно аппроксимировать как $${\begin{aligned}{\frac {\ \partial {\mathcal {L}}\ }{\partial x}}\approx {\frac {{\mathcal {L}}(x+\varepsilon ,\lambda )-{\mathcal {L}}(x,\lambda )}{\varepsilon }},\\[5pt]{\frac {\ \partial {\mathcal {L}}\ }{\partial \lambda }}\approx {\frac {{\mathcal {L}}(x,\lambda +\varepsilon )-{\mathcal {L}}(x,\lambda )}{\varepsilon }},\end{aligned}}$$ где $\varepsilon$ это небольшая величина.

Далее мы вычисляем величину градиента, которая представляет собой квадратный корень из суммы квадратов частных производных: $${\begin{aligned}h(x,\lambda )&={\sqrt {(2x+2x\lambda )^{2}+(x^{2}-1)^{2}\ }}\\[4pt]&\approx {\sqrt {\left({\frac {\ {\mathcal {L}}(x+\varepsilon ,\lambda )-{\mathcal {L}}(x,\lambda )\ }{\varepsilon }}\right)^{2}+\left({\frac {\ {\mathcal {L}}(x,\lambda +\varepsilon )-{\mathcal {L}}(x,\lambda )\ }{\varepsilon }}\right)^{2}\ }}~.\end{aligned}}$$

(Поскольку величина всегда неотрицательна, оптимизация по квадрату величины эквивалентна оптимизации по величине. Таким образом, «квадратный корень» можно опустить в этих уравнениях без ожидаемой разницы в результатах оптимизации.)

Критические точки h встречаются в точках x = 1 и x = −1 , как и в ${\mathcal {L}}~.$ В отличие от критических точек ${\mathcal {L}}\,,$ однако критические точки h возникают в локальных минимумах, поэтому для их поиска можно использовать методы численной оптимизации.

Приложения

Теория управления

В теории оптимального управления множители Лагранжа интерпретируются как переменные стоимости , а множители Лагранжа переформулируются как минимизация гамильтониана в принципе минимума Понтрягина .

Нелинейное программирование

Метод множителей Лагранжа имеет несколько обобщений. В нелинейном программировании существует несколько правил множителей, например правило множителей Каратеодори – Джона и правило выпуклых множителей, для ограничений-неравенств.

Энергетические системы

Методы, основанные на множителях Лагранжа, находят применение в энергосистемах , например, при размещении распределенных энергетических ресурсов (DER) и сбросе нагрузки.

Безопасное обучение с подкреплением

Метод множителей Лагранжа применяется к марковским процессам принятия решений с ограничениями . Естественно, он создает основанные на градиенте первичные двойственные алгоритмы в безопасном обучении с подкреплением.

Нормализованные решения

При рассмотрении задач УЧП с ограничениями, т. е. при изучении свойств нормированных решений, важную роль играют множители Лагранжа.

См. также

• Корректировка наблюдений
• Двойственность
• Индекс Гиттинса
• Условия Каруша – Куна – Такера : обобщение метода множителей Лагранжа
• Множители Лагранжа в банаховых пространствах : еще одно обобщение метода множителей Лагранжа
• Тест множителя Лагранжа при оценке максимального правдоподобия
• Лагранжева релаксация

Дальнейшее чтение

• Бивис, Брайан; Доббс, Ян М. (1990). «Статическая оптимизация» . Теория оптимизации и устойчивости для экономического анализа . Нью-Йорк, штат Нью-Йорк: Издательство Кембриджского университета. стр. 32–72. ISBN  0-521-33605-8 .
• Берцекас, Дмитрий П. (1982). Оптимизация с ограничениями и методы множителей Лагранжа . Нью-Йорк, штат Нью-Йорк: Academic Press. ISBN  0-12-093480-9 .
• Беверидж, Гордон С.Г.; Шехтер, Роберт С. (1970). «Множители Лагранжа» . Оптимизация: теория и практика . Нью-Йорк, штат Нью-Йорк: МакГроу-Хилл. стр. 244–259. ISBN  0-07-005128-3 .
• Бингер, Брайан Р.; Хоффман, Элизабет (1998). «Ограниченная оптимизация». Микроэкономика с исчислением (2-е изд.). Чтение: Аддисон-Уэсли. стр. 56–91. ISBN  0-321-01225-9 .
• Картер, Майкл (2001). «Ограничения равенства» . Основы математической экономики . Кембридж, Массачусетс: MIT Press. стр. 516–549. ISBN  0-262-53192-5 .
• Хестенес, Магнус Р. (1966). «Минимумы функций, на которые распространяются ограничения равенства». Вариационное исчисление и теория оптимального управления . Нью-Йорк, штат Нью-Йорк: Уайли. стр. 29–34.
• Уайли, К. Рэй; Барретт, Луи К. (1995). «Экстремумы интегралов при ограничении». Высшая инженерная математика (Шестое изд.). Нью-Йорк, штат Нью-Йорк: МакГроу-Хилл. стр. 1096–1103. ISBN  0-07-072206-4 .

Внешние ссылки

Экспозиция

• Стюард. «Концептуальное введение» . slimy.com . - плюс краткое обсуждение множителей Лагранжа в вариационном исчислении , используемых в физике.
• Карпентер, Кеннет Х. «Множители Лагранжа для квадратичных форм с линейными ограничениями» (PDF) . Канзасский государственный университет .

Дополнительный текст и интерактивные апплеты

• Резник. «Простое объяснение на примере того, как правительства используют налоги в качестве множителей Лагранжа» . umiacs.umd.edu . Университет Мэриленда .
• Кляйн, Дэн. «Множители Лагранжа без постоянных рубцов] Объяснение с акцентом на интуицию» (PDF) . nlp.cs.berkeley.edu . Калифорнийский университет в Беркли .
• Сатьянараяна, Шаши. «Геометрическое представление метода множителей Лагранжа» . wolfram.com ( Mathematica демонстрация ). Вольфрам Исследования . Требуется Internet Explorer/Firefox/Safari. — Обеспечивает убедительное представление в двух измерениях о том, что в точке минимизации направление наибольшего спуска должно быть перпендикулярно касательной кривой ограничения в этой точке.
• «Множители Лагранжа – две переменные» . Открытые курсы MIT (ocw.mit.edu) (Applet). Массачусетский технологический институт .
• «Множители Лагранжа» . Открытые курсы MIT (ocw.mit.edu) (видеолекция). Математика 18-02: Многомерное исчисление. Массачусетский технологический институт . Осень 2007 года.
• Берцекас. «Подробнее о множителях Лагранжа» (PDF) . athenasc.com (слайды/лекции курса). Нелинейное программирование. — Слайды курса, сопровождающие текст по нелинейной оптимизации.
• Вятт, Джон (7 апреля 2004 г.) [19 ноября 2002 г.]. «Множители Легранжа, оптимизация с ограничениями и принцип максимальной энтропии» (PDF) . www-mtl.mit.edu . Elec E & CS / Mech E 6.050 – Информация, энтропия и вычисления. — Геометрическая идея, лежащая в основе множителей Лагранжа.
• «Использование множителей Лагранжа в оптимизации» . matlab.cheme.cmu.edu (пример MATLAB). Питтсбург, Пенсильвания: Университет Карнеги-Меллона. 24 декабря 2011 г.