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

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

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

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

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

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

Заявление

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

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

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

${\ displaystyle {\ text {при условии:}} \ g (x) = 0}$

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

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

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

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

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

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

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

${\ displaystyle {\ text {при условии:}} \ g (x, y) = 0}$

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

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

где ${\ displaystyle \ lambda}$термин может быть либо добавлен, либо вычтен. Если${\ displaystyle f (x_ {0}, y_ {0})}$ это максимум ${\ displaystyle f (x, y)}$ для исходной задачи с ограничениями и ${\ Displaystyle \ набла г (х_ {0}, у_ {0}) \ neq 0}$, то существует ${\ displaystyle \ lambda _ {0}}$ такой, что (${\ displaystyle x_ {0}, y_ {0}, \ lambda _ {0}}$) является стационарной точкой для функции Лагранжа (стационарными точками являются те точки, в которых первые частные производные${\ Displaystyle {\ mathcal {L}}}$равны нулю). Предположение${\ Displaystyle \ набла г \ neq 0}$называется квалификацией ограничений. Однако не все стационарные точки дают решение исходной задачи, так как метод множителей Лагранжа дает только необходимое условие оптимальности в задачах с ограничениями. ^{[9] [10] [11] [12] [13]} Также существуют достаточные условия для минимума или максимума , но если конкретное решение-кандидат удовлетворяет достаточным условиям, гарантируется только то, что это решение является лучшим локально - что есть, лучше любых допустимых близлежащих точек. глобальной Оптимум может быть найден путем сравнения значений исходной целевой функции в точках, удовлетворяющих необходимым и локально достаточным условиям.

Метод множителей Лагранжа основан на интуиции, что в максимуме 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}} (х, у, \ лямбда) = е (х, у) - \ лямбда г (х, у),}$

и решить

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

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

Обратите внимание, что ${\ Displaystyle \ набла _ {\ лямбда} {\ mathcal {L}} (х, у, \ лямбда) = 0}$ подразумевает ${\ displaystyle g (x, y) = 0}$, как частная производная от ${\ Displaystyle {\ mathcal {L}}}$ относительно ${\ displaystyle \ lambda}$ является ${\ Displaystyle -g (х, у)}$, который, очевидно, равен нулю тогда и только тогда, когда ${\ 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 {case}}}$

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

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

что сводится к решению n + 1 уравнения с n + 1 неизвестными.

Ограниченные экстремумы f являются критическими точками лагранжиана${\ 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 \ набла г_ {я} (\ mathbf {х})}$. Таким образом, набор направлений, допускаемых всеми ограничениями, представляет собой пространство направлений, перпендикулярных всем градиентам ограничений. Обозначим это пространство допустимых ходов через${\ displaystyle A}$ и обозначим диапазон градиентов ограничений через ${\ displaystyle S}$. Затем${\ Displaystyle А = S ^ {\ perp}}$, пространство векторов, перпендикулярных каждому элементу ${\ displaystyle S}$.

Мы по-прежнему заинтересованы в поиске точек, где ${\ displaystyle f}$не меняется при ходьбе, поскольку эти точки могут быть (ограниченными) экстремумами. Поэтому мы ищем${\ displaystyle \ mathbf {x}}$ так, чтобы любое допустимое направление движения от ${\ displaystyle \ mathbf {x}}$ перпендикулярно ${\ Displaystyle \ набла е (\ mathbf {х})}$ (иначе мы могли бы увеличить ${\ displaystyle f}$двигаясь в этом допустимом направлении). Другими словами,${\ Displaystyle \ набла е (\ mathbf {х}) \ в А ^ {\ перп} = 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 \ если \ 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 {case}}}$

что сводится к решению ${\ 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 м (м-1) / 2}$ уравнения:

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

куда ${\ Displaystyle \ клин}$обозначает внешний продукт . Стационарные точки${\ displaystyle x}$ являются решениями указанной выше системы уравнений плюс ограничение ${\ displaystyle g (x) = 0.}$ Обратите внимание, что ${\ Displaystyle {\ tfrac {1} {2}} м (м-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 \ тусклый (\ ker (L_ {x})) = п-1}$ и ${\ Displaystyle \ тусклый (\ ker (K_ {x})) = np.}$ ${\ 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} \ клин \ 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 {align} & {\ 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 {выровнены}}}$

потом

${\ 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 е (х, у) = х + у}$ при условии ограничения ${\ 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 {align} {\ mathcal {L}} (x, y, \ lambda) & = f (x, y) + \ lambda \ cdot g (x, y) \\ [4pt] & = x + y + \ lambda (x ^ {2} + y ^ {2} -1). \ end {выравнивается}}}$

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

${\ displaystyle {\ begin {align} \ 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 {выровнено }}}$

и поэтому:

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

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

Первые два уравнения дают

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

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

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

Пример 2

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

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

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

${\ Displaystyle е (х, у) = х ^ {2} у}$

с условием, что ${\ displaystyle x}$- и ${\ displaystyle y}$-координаты лежат на окружности вокруг начала координат с радиусом ${\ displaystyle {\ sqrt {3}}}$. То есть с учетом ограничения

${\ displaystyle g (x, y) = x ^ {2} + y ^ {2} -3 = 0.}$

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

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

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

${\ displaystyle {\ begin {align} {\ mathcal {L}} (x, y, \ lambda) & = f (x, y) + \ lambda \ cdot g (x, y) \\ & = x ^ { 2} y + \ lambda (x ^ {2} + y ^ {2} -3). \ End {выравнивается}}}$

из которого можно рассчитать градиент:

${\ displaystyle {\ begin {align} \ 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 {выровнено}}}$

И поэтому:

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

(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}} (х, у, 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,}$

что дает систему n уравнений,${\ Displaystyle к = 1, \ ldots, п}$, такое, что:

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

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

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

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

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

Сначала мы вычисляем частную производную безусловной задачи по каждой переменной:

${\ displaystyle {\ begin {align} & {\ frac {\ partial {\ mathcal {L}}} {\ partial x}} = 2x + 2x \ lambda \\ [5pt] & {\ frac {\ partial {\ mathcal {L}}} {\ partial \ lambda}} = x ^ {2} -1. \ end {выравнивается}}}$

Если целевая функция трудно дифференцируема, дифференциал по каждой переменной может быть аппроксимирован как

${\ displaystyle {\ begin {align} {\ frac {\ partial {\ mathcal {L}}} {\ partial x}} \ приблизительно {\ frac {{\ mathcal {L}} (x + \ varepsilon, \ lambda) - {\ mathcal {L}} (x, \ lambda)} {\ varepsilon}}, \\ [5pt] {\ frac {\ partial {\ mathcal {L}}} {\ partial \ lambda}} \ приблизительно { \ frac {{\ mathcal {L}} (x, \ lambda + \ varepsilon) - {\ mathcal {L}} (x, \ lambda)} {\ varepsilon}}, \ end {align}}}$

куда ${\ displaystyle \ varepsilon}$ это небольшое значение.

Затем мы вычисляем величину градиента, которая представляет собой квадратный корень из суммы квадратов частных производных:

${\ displaystyle {\ begin {align} h (x, \ lambda) & = {\ sqrt {(2x + 2x \ lambda) ^ {2} + (x ^ {2} -1) ^ {2}}} \ \ [4pt] & \ приблизительно {\ 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 {align}}}$

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

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

Приложения

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

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

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

Метод множителей Лагранжа имеет несколько обобщений. В нелинейном программировании существует несколько правил умножения, например, правило мультипликатора Каратеодори – Джона и правило выпуклого множителя для ограничений неравенства. ^[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.

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

Экспозиция

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

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

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