Функция Лагранжа

ЛАГРАНЖА ФУНКЦИЯ

Перевод

ЛАГРАНЖА ФУНКЦИЯ

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

при условиях 

Функция F(x,l), определенная выражением 

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

Соотношения (5) полученной системы  представляют условия связи (2). Точка   доставляет обычный (безусловный) экстремум Л. ф.   по х.

Для большинства практич. задач значение   в (3), (4) можно принять равным единице. Однако имеются примеры (см. [1]), в к-рых правило множителей при   не выполняется, а выполняется при   Для определения условий, позволяющих отличить случаи   рассматриваются (см. [2]) матрицы G и G_f.

Пусть r(G) - ранг матрицы G, рассматриваемой в оптимальной точке х*. Тогда если   если же  то для выполнения правила множителей необходимо положить   Кроме того, если   (наиболее распространенный случай в практич. задачах), то   определены однозначно, а если   определяются не единственным образом. В зависимости от рассмотренных случаев   полагается равным 0 или 1. Тогда система (4), (5) превращается в систему m+n уравнений с m+n неизвестными   Множителям Лагранжа   можно дать интерпретацию, имеющую определенный физич. смысл (см. Лагранжа множители).

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

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

при условиях 

Для вывода необходимых условий  оптимальности в задаче (6) - (8) вводится Л. ф.

Для определенности рассматривается  случай максимума f(x). Пусть   доставляет максимум f(x).при ограничениях (7), (8) и пусть в точке х* выполнено требование регулярности ограничений (см. [2]); пусть J - множество индексов jиз j=1, ..., п, для к-рых   - множество индексов j, для к-рых   и I - множество индексов i из i=1,. . ., m₂, для к-рых ограничения (7) в точке х*выполняются как строгие неравенства. Тогда существует такой вектор 

Сформулированные необходимые  условия обобщают условия (4), (5). Эти  условия можно интерпретировать, используя понятие седловой точки  функции F(x,l). В седловой точке (x*,l*) функция F(x,l) удовлетворяет неравенствам 

Точка   в к-рой выполняются условия (10) - (12), удовлетворяет необходимым условиям существования седловой точки Л. ф.F(x,l) на множестве   и l, удовлетворяющем ограничениям (10). В том случае, когда f(х) - вогнутая при   функция, a g_i(x) - выпуклая, если   и вогнутая, если   сформулированные необходимые условия оказываются и достаточными, т. е. найденная из необходимых условий точка (x*,l*) является седловой точкой Л. ф. F(x,l) при   и l, удовлетворяющем ограничениям (10), и f(x*).является абсолютным максимумом f(x).при ограничениях (7), (8).

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

при ограничениях 

Ограничения (7) при i=1, ..., т ₂ сводятся к (14) простым переобозначением. Условия типа равенства   заменяются неравенствами   и также приводятся к виду (14). Пусть Л. ф. записана в виде 

и пусть I - множество индексов tиз I=1, ..., т, для к-рых ограничения (14) выполняются как строгие неравенства. Тогда если   - оптимальное решение задачи (13) - (15), то при выполнении требования регулярности   ограничений существует такой вектор 

что 

(см. [2], [3]). Условия (17) - (19) с  учетом положительных  и нулевых значений   иногда записывают следующим образом:

Если  ограничения (7) или (14) линейны, то упоминаемое  выше условие регулярности ограничений всегда выполнено. Поэтому  для линейных ограничений  единственным предположением при выводе необходимых  условий является дифференцируемость функции f(x).

Если  в задаче (13) - (15) функции f(x). и g_i(x), i=1,. . ., т, вогнутые, то точка (x*, l*) удовлетворяющая необходимым условиям (17) - (19), является седловой точкой Л. ф. (16) и х* доставляет абсолютный максимум. То что Л. ф. имеет в этом случае седловую точку, может быть доказано и без предположений о дифференцируемоеЩ функций f(x). и g_i(x).

Аналог  Л. ф. применяется  и в-вариационном исчислении при рассмотрении задач на условный экстремум функционалов. Здесь также необходимые  условия оптимальности  в задаче на условный экстремум оказывается  удобным записывать как необходимые  условия для нек-рого составного функционала (аналога  Л. ф.), построенного с помощью множителей Лагранжа. Пусть, напр., поставлена Болъца задача:найти минимум функционала 

при наличии  дифференциальных ограничений  типа равенств 

и граничных  условий 

Необходимые условия в этой условноэкстремальной задаче получаются как  необходимые условия  безусловного экстремума функционала (см. [4])

составленного с помощью множителей Лагранжа 

Эти необходимые  условия, представляющие собой замкнутую  систему соотношений  для определения  оптимального решения x*(t) и соответствующих  множителей Лагранжа   в конкретных постановках записываются в виде Эйлера уравнения, Вейерштрасса условия и трансверсальности условия.

Лит.:[1] Смирнов В. И., Курс высшей математики, 23 изд., т. 1, М., 1974; [2] X е д л и Д ж., Нелинейное и динамическое программирование, пер. с англ., М., 1967; [3] К u h n H. W., Т u с k e r A. W., в кн.: Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability, Berk.- Los Ang., 1951, p. 481-92; [4] Б л и с с Г. А., Лекции цо вариационному исчислению, пер. с англ., М., 1950. И. Б. Вапнярский.

 

Математическая  энциклопедия. —  М.: Советская энциклопедия. И. М. Виноградов. 1977—1985.

222222222222222222222222222222

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

где действие — функционал 

 обозначает множество параметров системы.

Уравнения движения, полученные посредством функциональной производной, идентичны обычнымуравнениям Эйлера-Лагранжа. Динамические системы, чьи уравнения движения могут быть получены посредством принципа наименьшего действия для удобно выбранной функции Лагранжа, известны каклагранжевые динамические системы. Примеров лагранжевых динамических систем много, начиная с классической версии Стандартной Модели в физике элементарных частиц и заканчивая уравнениями Ньютона в классической механике. Также к ним относятся чисто математические проблемы, такие какуравнения геодезических и проблема Плато.

333333333333333333333333333

Функция Лагранжа

Перевод

Функция Лагранжа

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

Содержание 1 Описание метода 2 Обоснование 2.1 Двумерный случай 3 Применение 4 См. также 5 Ссылки

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

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

где  .

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

Обоснование

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

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

Линии уровня   и кривая  .

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

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

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

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

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

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

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

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

Применение

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

См. также

• Линейное программирование
• Условия Каруша — Куна — Таккера

Ссылки

• Зорич В. А. Математический анализ. Часть 1. — изд. 2-е, испр. и доп. — М.: ФАЗИС, 1997.

9999999999999999999999999999999

 

Содержание

Введение

1. Построение модели

2. Задача Лагранжа. Безусловный и условный экстремумы