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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Метод множителей Лагранжа, метод нахождения условного экстремума функции ~f(x), где x\in\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. Мы будем считать, что все функции непрерывно дифференцируемы, и данное уравнение задает гладкую кривую S на плоскости (x,\;y). Тогда задача сводится к нахождению экстремума функции f на кривой S. Будем также считать, что S не проходит через точки, в которых градиент f обращается в 0.

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

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

\nabla f\Big|_{(x_0,\;y_0)}=\lambda\nabla\psi\Big|_{(x_0,\;y_0)},\qquad\qquad(1)

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

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

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

Необходимым условием ее экстремума является равенство нулю градиента \nabla L(x_0,\;y_0,\;\lambda_0)=0. В соответствии с правилами дифференцирования, оно записывается в виде

\left\{\begin{matrix}
\dfrac{\partial f(x_0,\;y_0)}{\partial x}-\lambda_0\dfrac{\partial\psi(x_0,\;y_0)}{\partial x} & = & 0,\\
\dfrac{\partial f(x_0,\;y_0)}{\partial y}-\lambda_0\dfrac{\partial\psi(x_0,\;y_0)}{\partial y} & = & 0,\\
-\psi(x_0,\;y_0) & = & 0.
\end{matrix}\right.

Мы получили систему, первые два уравнения которой эквивалентны необходимому условию локального экстремума (1), а третье — уравнению \psi(x,\;y)=0. Из нее можно найти (x_0,\;y_0,\;\lambda_0). При этом \lambda_0\ne 0, поскольку в противном случае градиент функции f обращается в нуль в точке (x_0,\;y_0)\in S, что противоречит нашим предположениям. Следует заметить, что найденные таким образом точки (x_0,\;y_0) могут и не являться искомыми точками условного экстремума — рассмотренное условие носит необходимый, но не достаточный характер. Нахождение условного экстремума с помощью вспомогательной функции L и составляет основу метода множителей Лагранжа, примененного здесь для простейшего случая двух переменных. Оказывается, вышеприведенные рассуждения обобщаются на случай произвольного числа переменных и уравнений, задающих условия.

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

Применение[править | править исходный текст]

См. также[править | править исходный текст]

Литература[править | править исходный текст]

  • Зорич В. А. Математический анализ. Часть 1. — изд. 2-е, испр. и доп. — М.: ФАЗИС, 1997.
  • Акулич И.Л. Глава 3. Задачи нелинейного программирования // Математическое программирование в примерах и задачах. — М.: Высшая школа, 1986. — 319 с. — ISBN 5-06-002663-9.