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

Метод множителей Лагранжа, применяемый для решения задач математического программирования (в частности, линейного программирования) — метод нахождения условного экстремума функции $f(x)$ , где $x\in \mathbb {R} ^{n}$ , относительно $m$ ограничений $\varphi _{i}(x)=0$ , где $i$ меняется от единицы до $m$ .

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

Составим функцию Лагранжа в виде линейной комбинации функции $f$ и функций $\varphi _{i}$ , взятых с коэффициентами, называемыми множителями Лагранжа — $\lambda _{i}$ :

L(x,\;\lambda )=f(x)+\sum _{i=1}^{m}\lambda _{i}\varphi _{i}(x),

где

\lambda =(\lambda _{1},\;\ldots ,\;\lambda _{m})

.

Составим систему из $n+m$ уравнений, приравняв к нулю частные производные функции Лагранжа $L(x,\;\lambda )$ по $x_{j}$ и $\lambda _{i}$ .
Если полученная система имеет решение относительно параметров $x'_{j}$ и $\lambda '_{i}$ , тогда точка $x'$ может быть условным экстремумом, то есть решением исходной задачи. Заметим, что это условие носит необходимый, но не достаточный характер.

Обоснование

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

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

Линии уровня

\scriptstyle {f(x,\;y)}

и кривая

\scriptstyle {S}

.

Пусть требуется найти экстремум функции $f(x,\;y)$ при условии, заданном уравнением $\psi (x,\;y)=0$ .

Будем считать, что

1) функция

f

непрерывно дифференцируема,

2) функция

\psi

непрерывно дифференцируема, с частными производными, не равными нулю одновременно, то есть уравнение

\psi (x,\;y)=0

задаёт гладкую кривую

S

из обыкновенных точек на плоскости

(x,\;y)

.

3) кривая

S

не проходит через точки, в которых градиент

f

обращается в

0

.

Нарисуем на плоскости $(x,\;y)$ линии уровня функции $f$ (то есть кривые $f(x,\;y)=\mathrm {const}$ ). Из геометрических соображений следует, что точкой (возможно — точками) условного экстремума функции $f$ может быть только точка касания кривой $S$ и некоторой линии уровня, то есть точкой, в которой касательная к $S$ и касательная к этой линии уровня — совпадают. Действительно, если в некоторой точке $(x_{0},\;y_{0})$ кривая $S$ пересекает линию уровня $f(x_{0},\;y_{0})=C_{0}$ трансверсально (то есть под некоторым ненулевым углом), то при движении по кривой $S$ из точки $(x_{0},\;y_{0})$ можно попасть как на линии уровня, соответствующие значению, большему $C_{0}$ , так и на линии уровня, соответствующие значению, меньшему $C_{0}$ . Следовательно, такая точка не может быть точкой экстремума.

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

\nabla f{\Big |}_{(x_{0},\;y_{0})}=\lambda \cdot \nabla \psi {\Big |}_{(x_{0},\;y_{0})},\qquad \qquad (1)

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

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

L(x,\;y,\;\lambda )=f(x,\;y)-\lambda \cdot \psi (x,\;y).

Необходимым условием её экстремума является равенство нулю градиента $\nabla L(x_{0},\;y_{0},\;\lambda _{0})=0$ . В соответствии с правилами дифференцирования оно записывается в виде

\left\{{\begin{array}{llcc}{\dfrac {\partial f}{\partial x}}{\Big |}_{(x_{0},\;y_{0})}&-\lambda _{0}\cdot {\dfrac {\partial \psi }{\partial x}}{\Big |}_{(x_{0},\;y_{0})}&=&0,\\{\dfrac {\partial f}{\partial y}}{\Big |}_{(x_{0},\;y_{0})}&-\lambda _{0}\cdot {\dfrac {\partial \psi }{\partial y}}{\Big |}_{(x_{0},\;y_{0})}&=&0,\\&-\psi (x_{0},\;y_{0})&=&0.\end{array}}\right.

В полученной системе первые два уравнения эквивалентны необходимому условию локального экстремума (1), а третье — уравнению $\psi (x,\;y)=0$ . Из неё можно найти $(x_{0},\;y_{0},\;\lambda _{0})$ . При этом $\lambda _{0}\neq 0$ , поскольку в противном случае градиент функции $f$ обращается в нуль в точке $(x_{0},\;y_{0})\in S$ , что противоречит предположениям.

Замечание. Найденные таким способом точки $(x_{0},\;y_{0})$ могут и не являться точками условного экстремума $f$ — записанное дифференциальное условие носит необходимый, но не достаточный характер.

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

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

Применение

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

См. также

Литература

Акулич И.Л. Глава 3. Задачи нелинейного программирования // Математическое программирование в примерах и задачах. — М.: Высшая школа, 1986. — 319 с. — ISBN 5-06-002663-9..
Зорич В. А. Математический анализ. Часть 1. — изд. 2-е, испр. и доп. — М.: ФАЗИС, 1997.
Протасов В. Ю. Максимумы и минимумы в геометрии. — М.: МЦНМО. — 56 с. — (Библиотека «Математическое просвещение», выпуск 31).

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.