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

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

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

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

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

${\displaystyle {\mathcal {L}}(x,\lambda )\equiv f(x)+\langle \lambda ,g(x)\rangle }$

для функций ; называется множителем Лагранжа. ${\displaystyle f(x),g(x)}$ ${\displaystyle \lambda }$

В простом случае это упрощается до

${\displaystyle {\mathcal {L}}(x,\lambda )\equiv f(x)+\lambda \cdot g(x)}$

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

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

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

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

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

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

Заявление

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

Пусть – целевая функция, – функция ограничений, обе из которых принадлежат (т. е. имеют непрерывные первые производные). Пусть – оптимальное решение следующей задачи оптимизации такое, что для матрицы частных производных , : ${\displaystyle \ f\colon \mathbb {R} ^{n}\rightarrow \mathbb {R} \ }$ ${\displaystyle \ g\colon \mathbb {R} ^{n}\rightarrow \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 {\text{maximize}}\ f(x)}$

${\displaystyle {\text{subject to:}}\ g(x)=0}$

Тогда существует уникальный множитель Лагранжа, такой что (Обратите внимание, что это несколько традиционная вещь, которая явно рассматривается как вектор-столбец, чтобы гарантировать совпадение размеров. Но мы могли бы с тем же успехом сделать его просто вектором-строкой, не принимая транспонирование) . ${\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), рассмотрим задачу оптимизации

$${\displaystyle {\begin{aligned}{\underset {x,y}{\text{maximize}}}\quad &f(x,y)\\{\text{subject to}}\quad &g(x,y)=0.\end{aligned}}}$$

(Иногда аддитивная константа отображается отдельно, а не включается в , и в этом случае ограничение записывается , как показано на рисунке 1.) Мы предполагаем, что оба и имеют непрерывные первые частные производные . Мы вводим новую переменную ( ), называемую множителем Лагранжа (или неопределенным множителем Лагранжа ), и изучаем функцию Лагранжа (или лагранжиан или выражение Лагранжа ), определяемую формулой ${\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),}$

где термин может быть добавлен или вычтен. If является максимумом для исходной задачи с ограничениями, и тогда существует такое, что ( ) является стационарной точкой для функции Лагранжа (стационарные точки - это те точки, где первые частные производные равны нулю). Это предположение называется квалификацией ограничений. Однако не все стационарные точки дают решение исходной задачи, поскольку метод множителей Лагранжа дает лишь необходимое условие оптимальности в задачах с ограничениями. ^{[9] [10] [11] [12] [13]} Также существуют достаточные условия для минимума или максимума , но если конкретное решение-кандидат удовлетворяет достаточным условиям, гарантируется только то, что это решение является лучшим локально - что то есть это лучше, чем любые допустимые близлежащие точки. Глобальный оптимум можно найти путем сравнения значений исходной целевой функции в точках, удовлетворяющих необходимым и локально достаточным условиям . ${\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}}}$

Метод легко обобщается на функции от переменных. ${\displaystyle n}$

${\displaystyle \nabla _{x_{1},\dots ,x_{n},\lambda }{\mathcal {L}}(x_{1},\dots ,x_{n},\lambda )=0}$

что представляет собой решение n + 1 уравнений с n + 1 неизвестными.

Ограниченные экстремумы 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},\ ...,\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_{\star x}M)}$

где обозначает внешний продукт . Стационарные точки являются решениями приведенной выше системы уравнений плюс ограничение. Обратите внимание, что уравнения не являются независимыми, поскольку левая часть уравнения принадлежит подмногообразию, состоящему из разложимых элементов . ${\displaystyle \ \wedge \ }$ ${\displaystyle \ x\ }$ ${\displaystyle \ g(x)=0~.}$ ${\displaystyle \ {\tfrac {1}{2}}m(m-1)\ }$ ${\displaystyle \ \Lambda ^{2}(T_{\star x}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\ }$является стационарной точкой тогда и только тогда, когда содержит . Для удобства пусть и где обозначает касательное отображение или якобиан. Подпространство имеет размерность меньшую, чем размерность , а именно, и принадлежит тогда и только тогда, когда принадлежит образу. Говоря вычислительным языком, условие состоит в том, что принадлежит пространству строк матрицы или, что эквивалентно, пространству столбцов матрицы (транспонирования). If обозначает внешнее произведение столбцов матрицы стационарного условия для at становится ${\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 \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_{\star x}M}$ ${\displaystyle \ K_{\star x}:\mathbb {R} _{\star }^{p}\to T_{\star x}M~.}$ ${\displaystyle L_{x}}$ ${\displaystyle \ K_{x}\ ,}$ ${\displaystyle K_{\star x}}$ ${\displaystyle \ \omega _{x}\in \Lambda ^{p}(T_{\star x}M)\ }$ ${\displaystyle \ K_{\star x}\ ,}$ ${\displaystyle \ f|_{N}\ }$ ${\displaystyle \ x\ }$

${\displaystyle L_{x}\wedge \omega _{x}=0\in \Lambda ^{p+1}\left(T_{\star x}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 , можно интерпретировать как множитель Лагранжа, определяющий изменение действия (переход потенциала в кинетическую энергию) после изменения ограниченной траектории частицы. В теории управления это формулируется вместо этого как уравнения стоимости .

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

Для метода множителей Лагранжа ограничение имеет вид

${\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}}}$

— это функция, которая эквивалентна функции, когда установлено значение 0 . ${\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)\ }$

Применение обычного метода множителей Лагранжа дает

${\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}}}$

(iii) является исходным ограничением. (i) подразумевает или Если то из (iii) и, следовательно, из (ii). Подстановка этого в (ii) дает результат. Подстановка этого в (iii) и решение дает. Таким образом, существует шесть критических точек ${\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~.}$

Мы используем множители Лагранжа, чтобы найти точку максимальной энтропии для всех дискретных распределений вероятностей. Мы требуем, чтобы: ${\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\ ,}$

что дает систему из n уравнений, такую ​​что: ${\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-Х.
2. Бивис, Брайан; Доббс, Ян М. (1990). «Статическая оптимизация». Теория оптимизации и устойчивости для экономического анализа . Нью-Йорк: Издательство Кембриджского университета. п. 40. ISBN 0-521-33605-8.
3. Проттер, Мюррей Х .; Морри, Чарльз Б. младший (1985). Промежуточное исчисление (2-е изд.). Нью-Йорк, штат Нью-Йорк: Спрингер. п. 267. ИСБН 0-387-96058-9.
4. Уолш, Греция (1975). «Свойство перевала функции Лагранжа». Методы оптимизации . Нью-Йорк, штат Нью-Йорк: Джон Уайли и сыновья. стр. 39–44. ISBN 0-471-91922-5.
5. Кальман, Дэн (2009). «Выравнивание с помощью Лагранжа: альтернативный взгляд на оптимизацию с ограничениями». Журнал «Математика» . 82 (3): 186–196. дои : 10.1080/0025570X.2009.11953617. JSTOR  27765899. S2CID  121070192.
6. Зильберберг, Юджин; Суен, Винг (2001). Структура экономики: математический анализ (Третье изд.). Бостон: Ирвин МакГроу-Хилл. стр. 134–141. ISBN 0-07-234352-4.
7. де ла Фуэнте , Анхель (2000). Математические методы и модели для экономистов . Кембридж: Издательство Кембриджского университета. п. 285. дои : 10.1017/CBO9780511810756. ISBN 978-0-521-58512-5.
8. Люенбергер, Дэвид Г. (1969). Оптимизация методами векторного пространства . Нью-Йорк: Джон Уайли и сыновья. стр. 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). Введение в дифференциальные многообразия. Спрингер. п. 70. ИСБН 978-3-319-20735-3.
15. Диксит, Авинаш К. (1990). «Теневые цены». Оптимизация в экономической теории (2-е изд.). Нью-Йорк: Издательство Оксфордского университета. стр. 40–54. ISBN 0-19-877210-6.
16. Чан, Альфа К. (1984). Фундаментальные методы математической экономики (Третье изд.). МакГроу-Хилл. п. 386. ИСБН 0-07-010813-7.
17. Хит, Майкл Т. (2005). Научные вычисления: вводный обзор. МакГроу-Хилл. п. 203. ИСБН 978-0-07-124489-3.
18. Пурсио, Брюс Х. (1980). «Современные правила мультипликатора». Американский математический ежемесячник . 87 (6): 433–452. дои : 10.2307/2320250. JSTOR  2320250.
19. Гаутам, Мукеш; Бхусал, Нараян; Бенидрис, Мохаммед (2020). Подход, основанный на чувствительности, к адаптивному отключению нагрузки при пониженной частоте . Техасская конференция по энергетике и энергетике IEEE 2020 (TPEC). Институт инженеров электроники и электротехники . стр. 1–5. дои : 10.1109/TPEC48276.2020.9042569.
20. Альтман, Эйтан (2021). Марковские процессы принятия решений с ограничениями . Рутледж .
21. Дин, Дуншэн; Чжан, Кайцин; Йованович, Михайло; Басар, Тамер (2020). Первично-двойственный метод градиента естественной политики для марковских процессов принятия решений с ограничениями . Достижения в области нейронных систем обработки информации.

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

• Бивис, Брайан; Доббс, Ян М. (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 г.