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

Метод решения задач ограниченной оптимизации

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

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

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

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

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

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

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

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

Решение, соответствующее исходной ограниченной оптимизации, всегда является седловой точкой функции Лагранжа, ^{[4] [5]} , которую можно выделить среди стационарных точек из определенности ограниченной матрицы Гессе . ^[6]

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

Заявление

Следующее утверждение известно как теорема о множителях Лагранжа. ^[7]

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

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

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

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

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

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

Для случая только одного ограничения и только двух переменных выбора (как показано на рисунке 1) рассмотрим задачу оптимизации (иногда аддитивная константа отображается отдельно, а не включается в , в этом случае ограничение записывается как на рисунке 1.) Мы предполагаем, что и имеют непрерывные первые частные производные . Мы вводим новую переменную ( ), называемую множителем Лагранжа (или неопределенным множителем Лагранжа ) и изучаем функцию Лагранжа (или лагранжево или лагранжево выражение ), определяемую как , где член может быть либо добавлен, либо вычтен. Если является максимумом для исходной задачи с ограничениями и тогда существует такое, что ( ) является стационарной точкой для функции Лагранжа (стационарные точки — это те точки, где первые частные производные равны нулю). Это предположение называется квалификацией ограничения. Однако не все стационарные точки дают решение исходной задачи, поскольку метод множителей Лагранжа дает только необходимое условие оптимальности в задачах с ограничениями. ^{[9] [10] [11] [12] [13]} Достаточные условия для минимума или максимума также существуют , но если конкретное решение-кандидат удовлетворяет достаточным условиям, то гарантируется только то, что это решение является лучшим локально – то есть оно лучше любых допустимых близлежащих точек. Глобальный оптимум может быть найден путем сравнения значений исходной целевой функции в точках, удовлетворяющих необходимым и локально достаточным условиям. $${\displaystyle {\begin{aligned}{\underset {x,y}{\text{maximize}}}\quad &f(x,y)\\{\text{subject to}}\quad &g(x,y)=0.\end{aligned}}}$$ ${\displaystyle g}$ ${\displaystyle g(x,y)=c,}$ ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle \lambda }$ $${\displaystyle {\mathcal {L}}(x,y,\lambda )=f(x,y)+\lambda \cdot g(x,y),}$$ ${\displaystyle \lambda }$ ${\displaystyle f(x_{0},y_{0})}$ ${\displaystyle f(x,y)}$ ${\displaystyle \nabla g(x_{0},y_{0})\neq 0,}$ ${\displaystyle \lambda _{0}}$ ${\displaystyle x_{0},y_{0},\lambda _{0}}$ ${\displaystyle {\mathcal {L}}}$ ${\displaystyle \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 и для некоторых $${\displaystyle \nabla _{x,y}f=\lambda \,\nabla _{x,y}g,}$$ ${\displaystyle \lambda }$

где — соответствующие градиенты. Константа необходима, поскольку, хотя два вектора градиента параллельны, величины векторов градиента, как правило, не равны. Эта константа называется множителем Лагранжа. (В некоторых соглашениях перед ней стоит знак минус). $${\displaystyle \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)}$$ ${\displaystyle \lambda }$ ${\displaystyle \lambda }$

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

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

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

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

Подводя итог $${\displaystyle \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 + 1 уравнений с n + 1 неизвестными. ${\displaystyle n}$ $${\displaystyle \nabla _{x_{1},\dots ,x_{n},\lambda }{\mathcal {L}}(x_{1},\dots ,x_{n},\lambda )=0}$$

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

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

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

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

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

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

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

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

Мы все еще заинтересованы в поиске точек, где не меняется по мере нашего движения, поскольку эти точки могут быть (ограниченными) экстремумами. Поэтому мы ищем такие, чтобы любое допустимое направление движения от было перпендикулярно (иначе мы могли бы увеличивать , двигаясь вдоль этого допустимого направления). Другими словами, Таким образом, существуют скаляры, такие, что ${\displaystyle f}$ ${\displaystyle \mathbf {x} }$ ${\displaystyle \mathbf {x} }$ ${\displaystyle \nabla f(\mathbf {x} )}$ ${\displaystyle f}$ ${\displaystyle \nabla f(\mathbf {x} )\in A^{\perp }=S\,.}$ ${\displaystyle \lambda _{1},\lambda _{2},\ \dots ,\lambda _{M}}$ $${\displaystyle \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~.}$$

Эти скаляры — множители Лагранжа. Теперь у нас их есть, по одному на каждое ограничение. ${\displaystyle M}$

Как и прежде, вводим вспомогательную функцию и решаем, что равносильно решению уравнений с неизвестными. $${\displaystyle {\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)}\ }$$ $${\displaystyle \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}}}$$ ${\displaystyle n+M}$ ${\displaystyle \ n+M\ }$

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

Современная формулировка через дифференцируемые многообразия

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

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

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

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

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

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

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

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

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

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

Часто множители Лагранжа имеют интерпретацию как некую величину интереса. Например, параметризуя контурную линию ограничения, то есть, если выражение Лагранжа то $${\displaystyle {\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}}}$$ $${\displaystyle \ {\frac {\partial {\mathcal {L}}}{\partial c_{k}}}=\lambda _{k}~.}$$

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

Более того, по теореме об огибающей оптимальное значение множителя Лагранжа имеет интерпретацию как предельное влияние соответствующей константы ограничения на оптимальное достижимое значение исходной целевой функции: Если обозначить значения в оптимуме звездочкой ( ), то можно показать, что ${\displaystyle \star }$ $${\displaystyle {\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}~.}$$

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

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

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

Примеры

Пример 1

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

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

Для метода множителей Лагранжа ограничением является, следовательно, функция Лагранжа, — это функция, которая эквивалентна , когда равна 0 . $${\displaystyle g(x,y)=x^{2}+y^{2}-1=0\ ,}$$ $${\displaystyle {\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}}}$$ ${\displaystyle \ f(x,y)\ }$ ${\displaystyle \ g(x,y)\ }$

Теперь мы можем вычислить градиент: и, следовательно: $${\displaystyle {\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}}}$$ $${\displaystyle \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}}}$$

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

Первые два уравнения дают Подставляя в последнее уравнение, имеем: итак , что означает, что стационарные точки являются $${\displaystyle x=y=-{\frac {1}{2\lambda }},\qquad \lambda \neq 0~.}$$ $${\displaystyle {\frac {1}{4\lambda ^{2}}}+{\frac {1}{4\lambda ^{2}}}-1=0\ ,}$$ $${\displaystyle \lambda =\pm {\frac {1}{\sqrt {2\ }}}\ ,}$$ ${\displaystyle {\mathcal {L}}}$ $${\displaystyle \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 в этих точках дает $${\displaystyle 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\ }}~.}$$

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

Пример 2

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

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

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

Пример 3

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

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

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

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

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

Применение обычного метода множителей Лагранжа дает, из которого можно вычислить градиент: И, следовательно: (iii) — это просто исходное ограничение. (i) подразумевает или Если то по (iii) и, следовательно, из (ii). Если подстановка этого в (ii) дает Подстановка этого в (iii) и решение для дает Таким образом, существует шесть критических точек $${\displaystyle {\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}}}$$ $${\displaystyle {\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}}}$$ $${\displaystyle \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}}}$$ ${\displaystyle \ x=0\ }$ ${\displaystyle \ \lambda =-y~.}$ ${\displaystyle x=0}$ ${\displaystyle \ y=\pm {\sqrt {3\ }}\ }$ ${\displaystyle \ \lambda =0\ }$ ${\displaystyle \ \lambda =-y\ ,}$ ${\displaystyle \ x^{2}=2y^{2}~.}$ ${\displaystyle \ y\ }$ ${\displaystyle \ y=\pm 1~.}$ ${\displaystyle \ {\mathcal {L}}\ :}$ $${\displaystyle ({\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)~.}$$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Если целевая функция не является легко дифференцируемой, дифференциал по каждой переменной можно аппроксимировать как , где — малое значение. $${\displaystyle {\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}}}$$ ${\displaystyle \varepsilon }$

Далее мы вычисляем величину градиента, которая представляет собой квадратный корень из суммы квадратов частных производных: $${\displaystyle {\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 , как и в Однако, в отличие от критических точек в , критические точки в h возникают в локальных минимумах, поэтому для их поиска можно использовать методы численной оптимизации. ${\displaystyle {\mathcal {L}}~.}$ ${\displaystyle {\mathcal {L}}\,,}$

Приложения

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

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

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

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

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

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

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

Метод множителей Лагранжа применяется к ограниченным марковским процессам принятия решений. ^[20] Он естественным образом производит градиентные прямо-двойственные алгоритмы в безопасном обучении с подкреплением. ^[21]

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

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

Смотрите также

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

Ссылки

1. Хоффманн, Лоуренс Д.; Брэдли, Джеральд Л. (2004). Исчисление для бизнеса, экономики, социальных и естественных наук (8-е изд.). С. 575–588. ISBN 0-07-242432-X.
2. Бивис, Брайан; Доббс, Ян М. (1990). "Статическая оптимизация". Оптимизация и теория устойчивости для экономического анализа . Нью-Йорк: Cambridge University Press. стр. 40. ISBN 0-521-33605-8.
3. Проттер, Мюррей Х .; Моррей, Чарльз Б. младший (1985). Промежуточный исчисление (2-е изд.). Нью-Йорк, Нью-Йорк: Springer. стр. 267. ISBN 0-387-96058-9.
4. Уолш, GR (1975). "Свойство седловой точки функции Лагранжа". Методы оптимизации . Нью-Йорк, Нью-Йорк: John Wiley & Sons. стр. 39–44. ISBN 0-471-91922-5.
5. Калман, Дэн (2009). «Выравнивание с помощью Лагранжа: альтернативный взгляд на ограниченную оптимизацию». Mathematics Magazine . 82 (3): 186–196. doi :10.1080/0025570X.2009.11953617. JSTOR  27765899. S2CID  121070192.
6. Silberberg, Eugene; Suen, Wing (2001). Структура экономики: математический анализ (третье изд.). Бостон: Irwin McGraw-Hill. стр. 134–141. ISBN 0-07-234352-4.
7. де ла Фуэнте , Энджел (2000). Математические методы и модели для экономистов . Кембридж: Издательство Кембриджского университета. стр. 285. doi :10.1017/CBO9780511810756. ISBN 978-0-521-58512-5.
8. Луенбергер, Дэвид Г. (1969). Оптимизация методами векторного пространства . Нью-Йорк: John Wiley & Sons. С. 188–189.
9. Берцекас, Димитрий П. (1999). Нелинейное программирование (второе изд.). Кембридж, Массачусетс: Athena Scientific. ISBN 1-886529-00-0.
10. Вапнярский, И.Б. (2001) [1994], "Множители Лагранжа", Энциклопедия математики , EMS Press.
11. Ласдон, Леон С. (2002) [1970]. Теория оптимизации для больших систем (переиздание). Минеола, Нью-Йорк, Нью-Йорк: Довер. ISBN 0-486-41999-1. МР  1888251.
12. Хириар-Уррути, Жан-Батист; Лемарешаль, Клод (1993). «Глава XII: Абстрактная двойственность для практиков». Алгоритмы выпуклого анализа и минимизации . Grundlehren der Mathematischen Wissenschaften [Основные принципы математических наук]. Том. 306. Берлин, Германия: Springer-Verlag. стр. 136–193 (и библиографические комментарии, стр. 334–335). ISBN 3-540-56852-2. MR  1295240. Том II: Расширенная теория и методы пучков.
13. Лемарешаль, Клод (15–19 мая 2000 г.). «Лагранжева релаксация». В Юнгере, Майкл; Наддеф, Денис (ред.). Вычислительная комбинаторная оптимизация: статьи весенней школы, проходившей в замке Дагштуль . Весенняя школа прошла в замке Дагштуль, 15–19 мая 2000 г. Конспекты лекций по информатике. Том. 2241. Берлин, Германия: Springer-Verlag (опубликовано в 2001 г.). стр. 112–156. дои : 10.1007/3-540-45586-8_4. ISBN 3-540-42877-1. MR  1900016. S2CID  9048698.
14. Лафонтен, Жак (2015). Введение в дифференциальные многообразия. Springer. стр. 70. ISBN 978-3-319-20735-3.
15. Диксит, Авинаш К. (1990). «Теневые цены». Оптимизация в экономической теории (2-е изд.). Нью-Йорк: Oxford University Press. С. 40–54. ISBN 0-19-877210-6.
16. Чианг, Альфа С. (1984). Фундаментальные методы математической экономики (третье изд.). McGraw-Hill. стр. 386. ISBN 0-07-010813-7.
17. Хит, Майкл Т. (2005). Научные вычисления: вводный обзор. McGraw-Hill. стр. 203. ISBN 978-0-07-124489-3.
18. Pourciau, Bruce H. (1980). «Современные правила множителей». American Mathematical Monthly . 87 (6): 433–452. doi :10.2307/2320250. JSTOR  2320250.
19. Гаутам, Мукеш; Бхусал, Нараян; Бенидрис, Мохаммед (2020). Подход на основе чувствительности к адаптивному отключению нагрузки при пониженной частоте . Техасская конференция по энергетике и электротехнике IEEE 2020 г. (TPEC). Институт инженеров-электронщиков и электротехников . стр. 1–5. doi :10.1109/TPEC48276.2020.9042569.
20. Альтман, Эйтан (2021). Ограниченные марковские процессы принятия решений . Routledge .
21. Дин, Дуншэн; Чжан, Кайцин; Йованович, Михайло; Басар, Тамер (2020). Прямо-двойственный метод градиента естественной политики для ограниченных марковских процессов принятия решений . Достижения в области нейронных систем обработки информации.

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

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

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

Экспозиция

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

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

• Резник. "Простое объяснение на примере правительств, использующих налоги в качестве множителей Лагранжа". umiacs.umd.edu . Университет Мэриленда .
• Кляйн, Дэн. «Множители Лагранжа без постоянного рубцевания] Объяснение с упором на интуицию» (PDF) . nlp.cs.berkeley.edu . Калифорнийский университет в Беркли .
• Сатьянараяна, Шаши. "Геометрическое представление метода множителей Лагранжа". wolfram.com ( демонстрация Mathematica ). Wolfram Research . Требуется Internet Explorer / Firefox / Safari.— Дает убедительное представление в двух измерениях о том, что в точке минимизации направление наискорейшего спуска должно быть перпендикулярно касательной кривой ограничений в этой точке.
• «Множители Лагранжа – две переменные». MIT Open Courseware (ocw.mit.edu) (Applet). Массачусетский технологический институт .
• "Множители Лагранжа". MIT Open Courseware (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 г.