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

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

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

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

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

Большим преимуществом этого метода является то, что он позволяет решать оптимизацию без явного параметризация с точки зрения ограничений. В результате метод множителей Лагранжа широко используется для решения сложных задач оптимизации с ограничениями. Далее метод множителей Лагранжа обобщается Условия Каруша – Куна – Таккера., который также может учитывать ограничения-неравенства вида ${\displaystyle h(\mathbf {x} )\leq 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^{*}}$ оптимальное решение следующей задачи оптимизации, такое что rank ${\displaystyle Dg(x^{*})=c<n}$:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Для проверки первой возможности (касаемся контурной линии ж), обратите внимание, что, поскольку градиент функции перпендикулярна контурным линиям, касательные к контурным линиям ж и г параллельны тогда и только тогда, когда градиенты ж и г параллельны. Таким образом, мы хотим очков (Икс, у) где г(Икс, у) = 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 }$ предшествует знак минус).

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

Обратите внимание, что это означает решение трех уравнений с тремя неизвестными. Это метод множителей Лагранжа. Обратите внимание, что ${\displaystyle \nabla _{\lambda }{\mathcal {L}}(x,y,\lambda )=0}$ подразумевает ${\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}$

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

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

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

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

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

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

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

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

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

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

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

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

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

Позволять ${\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}$ стационарная точка ${\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

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

Пример 1а

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

Оценка целевой функции ж в этих точках дает

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

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

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

С другой стороны, минимумы возникают на уровне, установленном для ж = 0 (поскольку по построению ж не может принимать отрицательные значения), при ${\displaystyle ({\sqrt {2}}/2,-{\sqrt {2}}/2)}$ и ${\displaystyle (-{\sqrt {2}}/2,{\sqrt {2}}/2)}$, где кривые уровня ж не касаются ограничения. Условие, что ${\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) подразумевает ${\displaystyle x=0}$ или ${\displaystyle \lambda =-y}$. Если ${\displaystyle x=0}$ тогда ${\displaystyle y=\pm {\sqrt {3}}}$ согласно (iii) и, следовательно, ${\displaystyle \lambda =0}$ из (ii). Если ${\displaystyle \lambda =-y}$, подставляя это в (ii), получаем ${\displaystyle x^{2}=2y^{2}}$. Теперь подставляя это в (iii) и решая для ${\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).}$

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

Пример 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}.}$

Для того, чтобы это было вероятностным распределением, сумма вероятностей ${\displaystyle p_{i}}$ в каждой точке ${\displaystyle x_{i}}$ должно быть равно 1, поэтому наше ограничение:

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

что дает систему п уравнения ${\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.}$

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

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

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

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

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

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

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

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

Используя множители Лагранжа, эту задачу можно преобразовать в задачу безусловной оптимизации:

${\displaystyle {\mathcal {L}}(x,\lambda )=x^{2}+\lambda (x^{2}-1).}$

Две критические точки возникают в седловых точках, где Икс = 1 и Икс = −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}}}$

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

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

Приложения

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

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

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

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

Системы питания

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

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

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

использованная литература

1. Hoffmann, Laurence D .; Брэдли, Джеральд Л. (2004). Расчет для бизнеса, экономики, социальных наук и наук о жизни (8-е изд.). С. 575–588. ISBN  0-07-242432-X.
2. Бивис, Брайан; Доббс, Ян М. (1990). «Статическая оптимизация». Теория оптимизации и устойчивости для экономического анализа. Нью-Йорк: Издательство Кембриджского университета. п. 40. ISBN  0-521-33605-8.
3. Проттер, Мюррей Х.; Морри, Чарльз Б., мл. (1985). Промежуточный исчисление (2-е изд.). Нью-Йорк: Спрингер. п. 267. ISBN  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  9780521585125.
8. Люенбергер, Дэвид Г. (1969). Оптимизация методами векторного пространства. Нью-Йорк: Джон Вили и сыновья. С. 188–189.
9. Бертсекас, Дмитрий П. (1999). Нелинейное программирование (Второе изд.). Кембридж, Массачусетс: Athena Scientific. ISBN  1-886529-00-0.
10. Вапнярский, И. (2001) [1994], «Множители Лагранжа», Энциклопедия математики, EMS Press.
11. Ласдон, Леон С. (2002). Теория оптимизации для больших систем (Перепечатка изд. Macmillan 1970 г.). Минеола, Нью-Йорк: Дувр. ISBN  0-486-41999-1. Г-Н  1888251.
12. Хириар-Уррути, Жан-Батист; Лемарешаль, Клод (1993). «XII Абстрактная двойственность для практиков». Алгоритмы выпуклого анализа и минимизации, Том II: Расширенная теория и методы связки. Grundlehren der Mathematischen Wissenschaften [Основные принципы математических наук]. 306. Берлин: Springer-Verlag. С. 136–193 (и библиографические комментарии к стр. 334–335). ISBN  3-540-56852-2. Г-Н  1295240.
13. Лемарешаль, Клод (2001). «Лагранжева релаксация». В Юнгере, Михаэль; Наддеф, Денис (ред.). Вычислительная комбинаторная оптимизация: доклады весенней школы, прошедшей в Шлос-Дагштуле, 15–19 мая 2000 г.. Конспект лекций по информатике. 2241. Берлин: Springer-Verlag. С. 112–156. Дои:10.1007/3-540-45586-8_4. ISBN  3-540-42877-1. Г-Н  1900016.
14. Лафонтен, Жак (2015). Введение в дифференциальные многообразия.. Springer. п. 70. ISBN  9783319207353.
15. Диксит, Авинаш К. (1990). "Теневые цены". Оптимизация в экономической теории (2-е изд.). Нью-Йорк: Издательство Оксфордского университета. С. 40–54. ISBN  0-19-877210-6.
16. Чан, Альфа К. (1984). Фундаментальные методы математической экономики (Третье изд.). Макгроу-Хилл. п.386. ISBN  0-07-010813-7.
17. Хит, Майкл Т. (2005). Научные вычисления: вводный обзор. Макгроу-Хилл. п. 203. ISBN  978-0-07-124489-3.
18. Pourciau, Брюс Х. (1980). «Современные правила мультипликатора». Американский математический ежемесячный журнал. 87 (6): 433–452. Дои:10.2307/2320250. JSTOR  2320250.
19. Гаутам, Мукеш; Бхусал, Нараян; Бенидрис, Мохаммед (2020). «Основанный на чувствительности подход к адаптивному снижению пониженной нагрузки». 2020 IEEE Texas Power and Energy Conference (TPEC). IEEE. С. 1–5. Дои:10.1109 / TPEC48276.2020.9042569.

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

• Бивис, Брайан; Доббс, Ян М. (1990). «Статическая оптимизация». Теория оптимизации и устойчивости для экономического анализа. Нью-Йорк: Издательство Кембриджского университета. С. 32–72. ISBN  0-521-33605-8.
• Бертсекас, Дмитрий П. (1982). Ограниченная оптимизация и методы множителя Лагранжа. Нью-Йорк: Academic Press. ISBN  0-12-093480-9.
• Beveridge, Gordon S.G .; Шехтер, Роберт С. (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.
• Hestenes, Магнус Р. (1966). «Минимумы функций при ограничениях на равенство». Вариационное исчисление и теория оптимального управления. Нью-Йорк: Вили. С. 29–34.
• Wylie, C. Ray; Барретт, Луи С. (1995). «Экстремумы интегралов при ограничении». Высшая инженерная математика (Шестое изд.). Нью-Йорк: Макгроу-Хилл. С. 1096–1103. ISBN  0-07-072206-4.

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

Экспозиция

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

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

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