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

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

Метод множителей Лагранжа, метод нахождения условного экстремума функции ~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.



Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Полезное


Смотреть что такое "Метод множителей Лагранжа" в других словарях:

  • Лагранжа метод множителей —         метод решения задач на Условный экстремум; Л. м. м. заключается в сведении этих задач к задачам на безусловный экстремум вспомогательной функции т. н. функции Лагранжа.          Для задачи об экстремуме функции f (х1, x2,..., xn) при… …   Большая советская энциклопедия

  • Лагранжа множители — Метод множителей Лагранжа, метод нахождения условного экстремума функции f(x), где , относительно m ограничений , i меняется от единицы до m. Содержание 1 Описание метода …   Википедия

  • Лагранжа функция — Метод множителей Лагранжа, метод нахождения условного экстремума функции f(x), где , относительно m ограничений , i меняется от единицы до m. Содержание 1 Описание метода …   Википедия

  • Метод Лагранжа — (дифференциальные уравнения) метод решения дифференциальных уравнений. Метод Лагранжа приведения квадратичной формы к каноническому виду Метод множителей Лагранжа …   Википедия

  • МЕТОД ОПТИМИЗАЦИИ — метод построения алгоритмов нахождения максимумов функции и точек, в которых они достигаются, при наличии ограничений или без них. Обычно рассматривается случай, когда функция задана в одномерном или многомерном пространстве; однако М.о. обобщены …   Большой экономический словарь

  • Множители Лагранжа — Метод множителей Лагранжа, метод нахождения условного экстремума функции f(x), где , относительно m ограничений , i меняется от единицы до m. Содержание 1 Описание метода …   Википедия

  • Множитель Лагранжа — Метод множителей Лагранжа, метод нахождения условного экстремума функции f(x), где , относительно m ограничений , i меняется от единицы до m. Содержание 1 Описание метода …   Википедия

  • Функция Лагранжа — Метод множителей Лагранжа, метод нахождения условного экстремума функции f(x), где , относительно m ограничений , i меняется от единицы до m. Содержание 1 Описание метода …   Википедия

  • Метод функционала плотности — Теория функционала плотности (англ. density functional theory, DFT)  метод расчёта электронной структуры систем многих частиц в квантовой физике и квантовой химии. В частности, применяется для расчёта электронной структуры молекул и… …   Википедия

  • Список объектов, названных в честь Лагранжа — Существует несколько математических и физических объектов, носящих имя французского математика XVIII века Луи Жозефа Лагранжа: Теоремы Теорема Лагранжа в математическом анализе  см. формула конечных приращений Теорема Лагранжа (теория групп) …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»