Метод множителей Лагранжа

1. Метод множителей Лагранжа

Метод множителей Лагранжа, метод нахождения условного экстремума функции  , где  , относительно  ограничений  ,  меняется от единицы до  .

Описание  метода

• Составим функцию Лагранжа в виде линейной комбинации функции и функций , взятыми с коэффициентами, называемыми множителями Лагранжа — ,

, где  .

• Составим систему из уравнений, приравняв к нулю частные производные функции Лагранжа  по  и  .
• Если полученная система имеет решение относительно параметров  и  , и градиент функции в точке не равен нулю, тогда точка  может быть условным экстремумом, то есть решением исходной задачи. Заметим, что это условие носит необходимый, но не достаточный характер.

Обоснование

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

Двумерный случай

Линии уровня f(x,y) и кривая S

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

Нарисуем на плоскости  линии уровня функции (то есть кривые ). Из геометрических соображений видно, что экстремумом функции на кривой могут быть только точки, в которых касательные к и соответствующей линии уровня совпадают. Действительно, если кривая пересекает линию уровня в точке трансверсально (то есть под некоторым ненулевым углом), то двигаясь по кривой из точки мы можем попасть как на линии уровня, соответствующие большему значению , так и меньшему. Следовательно, такая точка не может быть точкой экстремума.

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

(1)

где — некоторое число, отличное от нуля, и являющееся множителем Лагранжа.

Рассмотрим теперь функцию Лагранжа , зависящую от и :

Необходимым условием ее экстремума является равенство нулю градиента  . В соответствии с правилами дифференцирования, оно записывается в виде

Мы получили систему, первые два уравнения которой  эквивалентны необходимому условию  локального экстремума (1), а третье — уравнению  . Из нее можно найти . При этом , поскольку в противном случае градиент функции обращается в нуль в точке , что противоречит нашим предположениям. Следует заметить, что найденные таким образом точки могут и не являться искомым условным экстремум — рассмотренное условие носит необходимый, но не достаточный характер. Нахождение условного экстремума с помощью вспомогательной функции и составляет основу метода множителей Лагранжа, примененного здесь для простейшего случая двух переменных. Оказывается, вышеприведенные рассуждения обобщаются на случай произвольного числа переменных и уравнений, задающих условия.

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

Применение

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

 

Рассмотрим общую  задачу оптимизации, содержащую несколько  ограничений в виде равенств:   минимизировать f(x) при ограничениях g_i (x)=0, j=1,...,к.

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

Минимизировать  f(x)= x₁ ^. x₂ +  x₃  при ограничении: g(x)= x₁ +x ₂+ x₃ - 1 = 0.  Исключив переменную x₃ с помощью уравнения g(x)=0, получим оптимизационную задачу с двумя переменными без ограничений: f(x₁ , x₂) = x₁ ^.  x₂ + (1 - x₁ - x₂)  .

Метод исключения переменных применим лишь в тех случаях, когда уравнения, представляющие ограничения, можно разрешить относительно некоторого конкретного набора независимых  переменных. При наличии большого числа ограничений в виде равенств, процесс исключения переменных становится весьма трудоемкой процедурой. Кроме  того, возможны ситуации, когда уравнения  не удается разрешать относительно переменной. В частности, если в приведенном  примере ограничения g(x)=0 задать в виде g(x)= + + , то получить аналитическое выражение какой-либо из переменных через другие не представляется возможным. Таким образом, при решении оптимизационных задач, содержащих сложные ограничения в виде равенств, целесообразно использовать метод множителей Лагранжа. С помощью этого метода находят необходимые условия, позволяющие идентифицировать точки оптимума в задачах оптимизации с ограничением в виде равенств. При этом задача с ограничением в виде равенств, преобразуется в эквивалентную задачу безусловной оптимизации.

Рассмотрим задачу, имеющую несколько ограничений  в виде равенств:    

 минимизировать  f(x) при ограничениях (x)=0, при  j=1,2,....,k.

В соответствии с методом множителей эта задача преобразуется в следующую задачу безусловной оптимизации:

минимизировать  L(x, )=f (x)-

  ,

где  L(x, ) - функция Лагранжа, - множители Лагранжа.

На знак   никаких требований не накладывается.

Приравниваем  частные производные L(x, ) по x к нулю, получаем следующую систему n уравнений с n неизвестными:

 ... ,

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

g₁(x)=0,

g₂(x)=0,

.........

g_k(x)=0.

Решение расширенной  системы, состоящей из n+k неизвестными, определяет стационарную точку функции L.

Пример № 1. Минимизировать    при ограничении .

Соответствующая задача безусловной оптимизации  записывается в следующем виде.

Минимизировать 

Приравняв две  компоненты градиента L к нулю, получим:         

 

            

 

 

Поставив полученные значения  в уравнение , получим,   т.е. . Следовательно,    
 
 

2. Условный экстремум 

Пусть - открытое множество и на G заданы функции . Обозначим такую, что

- уравнение связи.

Определение.

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

Метод множителей Лагранжа для решения задачи условного экстремума

Теорема

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

Следствие

Если  - точка условного экстремума функции относительно уравнений связи, то такие, что в точке или в координатном виде .

Достаточное условие условного  экстремума

Пусть является стационарной точкой функции Лагранжа при . Если - отрицательно (положительно) определена квадратическая форма переменных при условии , то является точкой max (min для положительно определенной) условного экстремума. Если она за этих условий не является знакоопределенной, тогда экстремума нет.