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

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

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

${\ Displaystyle {\ mathcal {L}} (х, \ лямбда) = е (х) - \ лямбда г (х)}$

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

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

Заявление [ править ]

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

Пусть - целевая функция, - функция ограничений, обе принадлежащие (то есть, имеющие непрерывные первые производные). Позвольте быть оптимальным решением следующей задачи оптимизации такое, что ранг :${\ Displaystyle е \ двоеточие \ mathbb {R} ^ {n} \ rightarrow \ mathbb {R}}$${\displaystyle g\colon \mathbb {R} ^{n}\rightarrow \mathbb {R} ^{c}}$${\displaystyle C^{1}}$${\displaystyle x^{*}}$${\displaystyle Dg(x^{*})=c<n}$

${\displaystyle {\text{maximize}}\ f(x)}$

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

(Здесь обозначает матрицу частных производных,. )${\displaystyle Dg(x^{*})}$${\displaystyle [{\frac {\partial g_{j}}{\partial x_{k}}}]}$

Тогда существуют уникальные множители Лагранжа такие, что .${\displaystyle \lambda ^{*}\in \mathbb {R} ^{c}}$${\displaystyle Df(x^{*})=\lambda ^{*T}Dg(x^{*})}$

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

Одиночное ограничение [ править ]

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

${\displaystyle {\text{maximize}}\ f(x,y)}$

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

(Иногда аддитивная константа отображается отдельно, а не включается в нее , и в этом случае ограничение записывается , как на рисунке 1.) Мы предполагаем, что обе и имеют непрерывные первые частные производные . Мы вводим новую переменную ( ), называемую множителем Лагранжа (или неопределенным множителем Лагранжа ), и изучаем функцию Лагранжа ( или выражение Лагранжа или Лагранжа ), определяемую формулой${\displaystyle g}$${\displaystyle g(x,y)=c}$${\displaystyle f}$${\displaystyle g}$${\displaystyle \lambda }$

${\displaystyle {\mathcal {L}}(x,y,\lambda )=f(x,y)-\lambda g(x,y),}$

где термин может быть либо добавлен, либо вычтен. Если является максимумом для исходной задачи с ограничениями и , то существует такая, что ( ) является стационарной точкой для функции Лагранжа (стационарными точками являются те точки, в которых первые частные производные равны нулю). Предположение называется квалификацией ограничений. Однако не все стационарные точки дают решение исходной задачи, так как метод множителей Лагранжа дает только необходимое условие оптимальности в задачах с ограничениями. ^{[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 ( х , у ) = г для различных значений г , а контур г задается г ( х , у ) = гр .

Предположим, мы идем по контурной линии с 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 )=f(x,y)-\lambda g(x,y),}$

и решить

${\displaystyle \nabla _{x,y,\lambda }{\mathcal {L}}(x,y,\lambda )=0.}$

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

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

Подвести итоги

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

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

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

Множественные ограничения [ править ]

Метод множителей Лагранжа может быть расширен для решения задач с множественными ограничениями, используя аналогичный аргумент. Рассмотрим параболоид с двумя линейными ограничениями, пересекающимися в одной точке. Как единственно возможное решение, эта точка, очевидно, является ограниченным экстремумом. Тем не менее, множество уровня из явно не параллельны либо ограничений в точке пересечения (см рисунок 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 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} }$

Позвольте и быть внешними производными . Стационарность для ограничения при означает. Эквивалентно, ядро содержит Другими словами, и являются пропорциональными векторами. Для этого необходимо и достаточно, чтобы выполнялась следующая система уравнений:${\displaystyle df}$${\displaystyle dg}$${\displaystyle f|_{N}}$${\displaystyle x\in N}$${\displaystyle d(f|_{N})_{x}=0.}$${\displaystyle \ker(df_{x})}$${\displaystyle T_{x}N=\ker(dg_{x}).}$${\displaystyle df_{x}}$${\displaystyle dg_{x}}$${\displaystyle m(m-1)/2}$

${\displaystyle df_{x}\wedge dg_{x}=0\in \Lambda ^{2}(T_{x}^{*}M)}$

где обозначает внешний продукт . Стационарные точки являются решениями вышеупомянутой системы уравнений плюс ограничение. Обратите внимание, что уравнения не являются независимыми, поскольку левая часть уравнения принадлежит подмногообразию, состоящему из разложимых элементов .${\displaystyle \wedge }$${\displaystyle x}$${\displaystyle g(x)=0.}$${\displaystyle {\tfrac {1}{2}}m(m-1)}$${\displaystyle \Lambda ^{2}(T_{x}^{*}M)}$

В этой формулировке нет необходимости явно находить множитель Лагранжа, число такое, что${\displaystyle \lambda }$${\displaystyle df_{x}=\lambda \,dg_{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}$является стационарной точкой тогда и только тогда, когда содержит . Для удобства пусть и где обозначает касательное отображение или якобиан . Подпространство имеет размерность меньше, чем размер , а именно, и принадлежит тогда и только тогда, когда принадлежит изображению Вычислительно говоря, условие состоит в том, что принадлежит пространству строк матрицы или эквивалентно пространство столбцов матрицы (транспонированной). Если обозначает внешнее произведение столбцов матрицы стационарного условия для at, становится${\displaystyle f|_{N}}$${\displaystyle \ker(df_{x})}$${\displaystyle \ker(dG_{x})}$${\displaystyle L_{x}=df_{x}}$${\displaystyle K_{x}=dG_{x},}$${\displaystyle dG}$${\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_{x}^{*}M}$${\displaystyle K_{x}^{*}:\mathbb {R} ^{p*}\to T_{x}^{*}M.}$${\displaystyle L_{x}}$${\displaystyle K_{x},}$${\displaystyle K_{x}^{*}}$${\displaystyle \omega _{x}\in \Lambda ^{p}(T_{x}^{*}M)}$${\displaystyle K_{x}^{*},}$${\displaystyle f|_{N}}$${\displaystyle x}$

${\displaystyle L_{x}\wedge \omega _{x}=0\in \Lambda ^{p+1}\left(T_{x}^{*}M\right)}$

Опять же, в этой формулировке нет необходимости явно находить множители Лагранжа, числа такие, что ${\displaystyle \lambda _{1},\ldots ,\lambda _{p}}$

${\displaystyle df_{x}=\sum _{i=1}^{p}\lambda _{i}d(g_{i})_{x}.}$

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

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

${\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 {\frac {{\text{d}}f(x_{1}^{*}(c_{1},c_{2},\dots ),x_{2}^{*}(c_{1},c_{2},\dots ),\dots )}{{\text{d}}c_{k}}}=\lambda _{k}^{*}.}$

Например, в экономике оптимальная прибыль для игрока рассчитывается с учетом ограниченного пространства действий, где множитель Лагранжа - это изменение оптимального значения целевой функции (прибыли) из-за ослабления данного ограничения (например, через изменение дохода); в таком контексте λ _k * - это предельные издержки ограничения, называемые теневой ценой . ^[15]

Достаточные условия [ править ]

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

Примеры [ править ]

Пример 1 [ править ]

Пример 1а [ править ]

Предположим, мы хотим максимизировать с учетом ограничений . Допустимое множество представляет собой единичный круг, и множество уровней по й диагональным линиям (с наклоном -1), так что мы можем видеть в графическом виде, что максимум происходит при , и что минимальные происходит .${\displaystyle f(x,y)=x+y}$${\displaystyle x^{2}+y^{2}=1}$${\displaystyle \left({\tfrac {\sqrt {2}}{2}},{\tfrac {\sqrt {2}}{2}}\right)}$${\displaystyle \left(-{\tfrac {\sqrt {2}}{2}},-{\tfrac {\sqrt {2}}{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}}}$

Теперь мы можем рассчитать градиент:

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

Пример 1b [ править ]

Теперь модифицируем целевую функцию из примера 1a, чтобы минимизировать, а не снова по окружности . Теперь наборы уровней по- прежнему являются линиями с наклоном -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}$

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

Пример 2 [ править ]

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

Предположим, мы хотим найти максимальные значения

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

Пример 3: Энтропия [ править ]

Предположим, мы хотим найти дискретное распределение вероятностей в точках с максимальной информационной энтропией . Это то же самое, что сказать, что мы хотим найти наименее структурированное распределение вероятностей в точках . Другими словами, мы хотим максимизировать уравнение энтропии Шеннона :${\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_{k}^{*}}=0.}$

Проводя дифференцирование этих n уравнений, получаем

${\displaystyle -\left({\frac {1}{\ln 2}}+\log _{2}p_{k}^{*}\right)+\lambda =0.}$

Это показывает, что все равны (потому что они зависят только от λ ). Используя ограничение${\displaystyle p_{k}^{*}}$

${\displaystyle \sum _{j}p_{j}=1,}$

мы нашли

${\displaystyle p_{k}^{*}={\frac {1}{n}}.}$

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

Пример 4: Численная оптимизация [ править ]

Критические точки лагранжианов находятся в седловых точках , а не в локальных максимумах (или минимумах). ^{[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]

См. Также [ править ]

Ссылки [ править ]

Дальнейшее чтение [ править ]

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

Внешние ссылки [ править ]

В разделе " Методы оптимизации исчисления Викибука" есть страница на тему: Множители Лагранжа.

Экспозиция

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

Для дополнительных текстовых и интерактивных апплетов

• Простое объяснение на примере правительства, использующего налоги в качестве множителя Лагранжа
• Множители Лагранжа без объяснения стойких рубцов с акцентом на интуицию Дэна Кляйна
• Геометрическое представление метода множителей Лагранжа. Обеспечивает убедительное понимание в двух измерениях, что в минимальной точке направление наискорейшего спуска должно быть перпендикулярно касательной к кривой ограничения в этой точке. [Требуется InternetExplorer / Firefox / Safari] Демонстрация Mathematica от Шаши Сатьянараяны
• Апплет
• Видео-лекция MIT OpenCourseware о множителях Лагранжа из курса многомерного исчисления
• Слайды, сопровождающие текст по нелинейной оптимизации Бертсекаса , с подробностями о множителях Лагранжа (лекции 11 и 12)
• Геометрическая идея множителей Лагранжа
• Пример MATLAB использования множителей Лагранжа в оптимизации