Новости    Библиотека    Энциклопедия    Биографии    Карта сайта    Ссылки    О проекте




предыдущая главасодержаниеследующая глава

Рассказ двенадцатый. Экстремумы функций многих переменных. Принцип Лагранжа

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

Ж. Лагранж

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

Пусть f0,f1, ..., fm - функции n переменных х = (х1 ,..., хn).

Рассмотрим задачу с ограничениями типа равенств и неравенств

(з) f0(х) → min (max), f (х) = 0, fi (x) = 0, i = 1, ..., m',
fi(x) ≤ 0, i = m' + 1, ..., m.

Отметим, впрочем, что в основном у нас будут встречаться задачи с одними лишь равенствами.

Примеры.

1) f0 (х) = (х1 - a1)2 + (х2 - а2)2 + (x1 - b1)2 + (х2 - b2)2 + (x1 - c1)2 + (х2 - с2)2 → min, х = (x1, x2).
2) f0(х) = х1...хn → max, (х) = х12 + ... + х2n - 1 = 0.

Напомним, что (з2) - это при n = 2 формализация планиметрической, а при n = 3 - классической задачи Кеплера о параллелепипеде максимального объема, вписанном в шар.

4) формализует такую задачу: найти на плоскости точку, сумма квадратов расстояний от которой до трех данных точек была бы минимальной (сравните ее с задачей Штейнера).

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

Обозначим совокупность допустимых точек в задаче (з) через С. Иначе говоря, С состоит из трех точек х, для которых

f(x) = 0, i = 1, ..., m', fi(х) = 0, i = m' +1, ..., m.

Множество С называется ограниченным, если существует константа А > 0 такая, что |хi| ≤ A, i = 1, ..., n для любой точки х = (х1..., хn) из С. Например, множество х21 + ... + х2n = 1 ограничено, в частности ограничена окружность х12 + х22 = 1, а множество х1 = х22 (парабола) не является ограниченным множеством.

Теорема Вейерштрасса.Пусть в задаче (з) функции f0,...., fm непрерывны, а совокупность С допустимых точек в (з) ограничена. Тогда решение обеих задач

min) f0 (х) → min, fi(х) = 0, i = 1, ..., m',
fi(x)≤ 0, i = m' + 1, ..., m

и

max) f0 (х) → max, f (х) = 0, i = 1, ..., m',
f (х) ≤ 0, i = m' + 1, ..., m

существует.

Укажем, как и в предыдущем рассказе, на такое

Следствие.Пусть функция f0(х)(х = (х1 ,..., хn)) непрерывна для любого х. Тогда если

lim f0 (х) = ∞ при х21 + ... + х2n → ∞,

то решение задачи без ограничений

f0(х) → min

существует.

Повторим определение локального экстремума в задаче (з).

Определение 1.Говорят, что точка х̂ = (х̂1, ..., х̂n) доставляет локальный минимум (максимум) в задаче (з), если можно указать такое ε > 0, что для всех допустимых точек х = (х1, ..., хn), удовлетворяющих неравенству

|xi - x̂i| < ε, i = 1,..,n

выполнено неравенство f0 (х) ≥ f0 (х̂) (f0(х) ≤ f0 (х̂)).

Если (з) задача без ограничений и х̂ доставляет ей локальный экстремум, мы говорим еще, что х̂ доставляет локальный экстремум функции f0.

Для того чтобы можно было сформулировать основное правило решения задач типа (з), необходимо ввести еще одно понятие.

Пусть функция y = f (х) определена для всех х = (х1, ..., хn), для которых выполнены неравенства aj ≤ хj ≤ bj, j = 1, ..., n (совокупность всех таких точек назовем параллелепипедом Π(a1, b1;,...,;an, bn) и пусть для точки х0 = (х01, ..., х0n) выполнены строгие неравенства

aj < xj < bj, j = 1, ..., n.

Рассмотрим следующую функцию одного переменного:

gj(x) = f(x01,....,x0,j-1, x0,j, x0,j+1,....,x0n).

Что мы сделали? Мы закрепили все координаты у х0, кроме j-й, а к j-й координате прибавили число х. Предположим теперь, что функция gj дифференцируема в нуле.

Определение 2.Производная в нуле функции gj называется j-й частной производной функции f в точке х0 и обозначается df(x0)/dxj.

Теперь сформулируем две теоремы, которые позволят нам затем описать правило решения задач типа (з).

Сначала рассмотрим задачу (з) без ограничений.

Теорема Ферма.Пусть в точке х̂ существуют все частные производные функции f0. Если точка х̂ доставляет локальный экстремум (минимум или максимум) этой функции, то

(1)

Точки, для которых все частные производные равны нулю, называются стационарными. Соотношения (1) являются, разумеется (как и в случае n = 1), необходимыми условиями.

Приведем пример приложения этой теоремы. Решим задачу (з1). Решение задачи существует в силу следствия теоремы Вейерштрасса. Обозначим его (х̂, у̂). Имеем


Ответ. (х̂, у̂) есть центр масс треугольника (а1, а2), (b1, b2), (c1, c2).

Теперь рассмотрим общую задачу (з), в которой, правда, неравенства отсутствуют. Составим такую сумму:


где х = (x1, ..., xm), λ = (λ0, λ1,....,λm)

Эту функцию называют функцией Лагранжа. Числа λ0, λ1,....,λm называются множителями Лагранжа.

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

(2)

дополненные уравнениями связи

(3)

надо решить относительно х1 ,..., хn, λ0, λ1,....,λm и среди этих решений выбрать нужное.

Это правило основывается на следующей теореме.

Теорема (правило множителей Лагранжа).Пусть функции f0, ...,fm определены в некотором параллелепипеде Π(a1, b1; а2, b2; ...; an, bn), содержащем внутри себя точку х̂ = (х̂1 ..., x̂n) (aii < bi, i = 1, ..., n). Пусть далее все функции fi, i = 0, 1, ..., m, и все частные производные əfi/əxj, i = 0, 1, ..., m; j = 1, ..., n непрерывны в этом параллелепипеде. Тогда если допустимая точка х̂ доставляет локальный экстремум (минимум или максимум) в задаче (з) (где неравенства отсутствуют: m' = m), то найдутся числа λ0, λ1,....,λm, не равные одновременно нулю и такие, что


Сделаем теперь несколько замечаний. Отметим, во-первых, что в (2) и (3) имеется n + m уравнений с n + m + 1 неизвестным. Но надо иметь в виду, что множители Лагранжа можно умножать на любую константу, отличную от нуля.

Таким образом, всегда можно домножить так, чтобы один из множителей Лагранжа равнялся единице. Тогда в (2) - (3) число уравнений фактически равно числу неизвестных.

Далее. Уравнения (2) наиболее содержательны, если λ0 ≠ 0. Ведь если λ0 = 0, то уравнения (2) отражают лишь вырожденность ограничений и не связаны с функцией, экстремум которой ищется. Но вообще-то заранее считать, что λ0 отлично от нуля (как это делает Лагранж - см. эпиграф), нельзя. Приведем пример, показывающий, что правило множителей Лагранжа при дополнительном допущении λ0 ≠ 0 может стать неверным.

Пример. Рассмотрим задачу (см. рис. 48):

х1 → min, х22 - х31 ≠ 0.
Рис. 48
Рис. 48

Из рисунка видно, что единственным решением задачи является точка х̂ = (0, 0). Попробуем теперь составить функцию Лагранжа с λ0 = 1 и применить алгоритм Лагранжа:


откуда


Уравнение связи имеет вид х22 - x31 = 0. Написанные уравнения, как легко видеть, не совместны.

Правило множителей Лагранжа позволяет дать следующий рецепт поиска решений задачи (з) с равенствами. Разобьем его на те же 4 этапа.

1 этап - формализация задачи. Требуется привести (разумеется, если это возможно) задачу к виду (з) с m' = m.

2 этап - применение принципа Лагранжа, т. е. составление системы уравнений


3 этап состоит в нахождении всех стационарных точек. При этом бывает полезно сначала выяснить вопрос о том, может ли λ0 равняться нулю или нет.

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

Этот рецепт решения мы коротко называем принципом Лагранжа.

Из сформулированных теорем следует, что если (в задаче без неравенств) совокупность допустимых точек ограничена и все функции f0,...,fm непрерывны и непрерывны все частные производные əfi/əxj, i = 0,...., m, j = 1, ..., n, то описанное правило приведет к решению задачи.

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

2. Здесь так же, как и в предыдущем рассказе, уделим место некоторым объяснениям.

Теорему Ферма в многомерном случае нет нужды специально объяснять, ибо она тривиально выводится из одномерного случая. Действительно, пусть функция f01,..., хn) имеет локальный экстремум в точке (х̂1 ,..., х̂n). То есть функция gj(x) (по типу той, которая была определена в п. 1)

gj(x) = f0(x̂1 ,..., x̂j-1, x̂j + x, x̂j+1,.....,x̂n)

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

g'j(0) = 0.

Но по самому определению j-й частной производной как раз и получается, что


Сопоставляя эти два равенства и произвольность j, приходим к теореме Ферма:


Теперь нам предстоит разобраться в правиле множителей Лагранжа. Начнем наши объяснения с простейшей ситуации, когда, во-первых, n = 2, m = 1, а во-вторых, когда ограничение задается линейным соотношением. Иначе говоря, будем рассматривать следующую задачу:

f0 (x1, х2) → max, f11, х2) = а1х1 + а2х2 - b = 0.

График y = f0(x1, х2) можно мыслить себе (вспомните, что говорилось в десятом рассказе) как ландшафт горной местности. Соотношение f11, х2) = a1x1 + а2х2 - b = 0 задает на плоскости прямую. Можно представить себе, что в горной местности прокладывают линию электропередачи по траектории, которая на карте имеет вид прямой. Спрашивается, где будет самая высокая точка трассы?

Вспомним, как горы изображают на картах. Там наносят линии одинаковой высоты, линии уровня. Задумаемся над тем, как должны быть расположены друг относительно друга трасса электропередачи и линия уровня нашей горы в точке наивысшего подъема.

Ясно, что трасса в этой точке не может пересекать линию уровня. Если трасса пересекает ее, то она проходит из области меньших значений высоты в область ее больших значений, и значит, в точке пересечения максимума высоты быть не может. Вывод: в точке максимума высоты трасса должна касаться линии уровня.

Теперь посмотрим на функцию f11, х2) = a1x1 + а2х2 - b. Ее частные производные


Вектор (а1, а2) перпендикулярен трассе и вообще любой линии уровня функции f11, х2). Это ясно из геометрического смысла уравнения а1x1 + а2х2 = b. Однако оказывается, что этот факт верен всегда. А именно, если f(х1, х2) - любая непрерывная функция, у которой ее частные производные также непрерывны, то вектор


перпендикулярен касательной к линии уровня f(х) = f(х̄).

Но ведь трасса тоже касательна к линии уровня в точке максимума высоты. Из всего сказанного и вытекает, что оба вектора


перпендикулярны трассе и, следовательно, пропорциональны, т. е.


или


где


В этой частной ситуации мы пришли к правилу множителей Лагранжа.

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

f0(x1, х2) = с0, f1(x1, х2) = c1.

Допустим, что в некоторой части плоскости через каждую точку проходит одна и лишь одна кривая каждого из семейств. Предположим, что в х̂ = (х̂1, х̂2) задача имеет решение. Тогда все точки кривой l0, задаваемой уравнением

f01, х2) = с̂0 = :f0(х̂1, х̂2),

обязаны лежать "по одну сторону" от кривой l1 задаваемой уравнением

f1(x1, х2) = ĉ1 = :f1(x̂1 х̂2),

т. е. эти кривые должны не пересекаться, а касаться. Мы объяснили, что если в точке х̂ на кривой l1 функция f0 имеет экстремальное значение, то кривая f0 касается кривой l1.

Еще раз напомним о том, что вектор (df0 (х̂)/dx1, df0 (х̂)/dx2) перпендикулярен кривой l0, а вектор (df0(x̂)/dx1, df0(x̂)/dx2) перпендикулярен кривой l1. Если эти кривые касаются, то данные векторы должны быть пропорциональны.

Пропорциональность этих векторов и утверждается в правиле множителей Лагранжа (с λ0 = 1).

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

В начале рассказа была поставлена общая задача, когда имеются и равенства, и неравенства. А дальше речь шла уже об одних лишь равенствах. Как видоизменяется принцип Лагранжа в общем случае? Вернемся к задаче (з), которая была поставлена вначале, и допустим, что все функции f0(х), ...,fm(x) удовлетворяют условиям сформулированной выше теоремы о правиле множителей Лагранжа. Тогда, если допустимая точка х̂ доставляет локальный минимум в задаче (з), то найдутся числа λ0, 1,...,λm не равные одновременно нулю и такие, что


кроме того, удовлетворяются условия не отрицательности множителей Лагранжа при функционале и неравенствах λ0 ≥ 0, λm'+1 ≥ 0,..., λm ≥ 0 и выполняются следующие условия (так называемые условия дополняющей не жесткости):

λjfj (х̂) = 0, j = m' + 1, ..., m.

Условия дополняющей не жесткости означают, что множитель Лагранжа λj может быть отличен от нуля только на "активном" ограничении, когда в точке экстремума ограничение типа неравенства на самом деле является равенством: fj (х̂) = 0, j = m' + 1, ..., m.

Что же изменилось? Во-первых, здесь "экстремум" заменился на "минимум". При неравенствах небезразлично, какой тип экстремума рассматривается. В случае задачи на максимум или при наличии ограничений вида fj > 0 для применения только что сформулированного результата необходимо сначала преобразовать задачу к виду (з), заменив, если это нужно, некоторые из fj, j = 0, m' + 1, ..., m на - fj. Во-вторых, добавилось условие не отрицательности, в-третьих - условие дополняющей не жесткости.

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

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

Пришлось специально заняться изучением выпуклых функций и выпуклых экстремальных задач. И мы уделим этому некоторое внимание.

3. Выпуклые функции и выпуклые задачи. О выпуклых функциях одного переменного мы мельком уже сказали. Выпуклые функции нескольких переменных определяются совершенно аналогично. Функция f(х) = f(х1 ,..., хn) называется выпуклой, если для любых точек х и х' и любого α, 0 ≤ α ≤ 1, имеет место неравенство Иенсена

f(αх + (1 - α)х') ≤ αf(х) + (1 - α)f(х').

Примерами выпуклых функций являются прежде всего линейные и аффинные функции. Отметим также "функцию расстояния" от точки до нуля


Функцию y = f (х) называют строго выпуклой, если в неравенстве Иенсена при х ≠ х' и 0 < α < 1 имеет место строгое неравенство

f(αх + (1 - α) х') < αf(x) + (1 - α)f(х')

Функции y = х2, y = √(h2 + х2) и x21 + х 22 строго выпуклы, а функция y = |х| или функция расстояния - не строго выпуклы. Нетрудно понять, что если функция y = f (х) строго выпукла и достигает в точке х̂ своего минимума, то этот минимум единствен.

Уже было сказано, что не всякая функция является дифференцируемой, и дважды обсуждался пример: y = |х|. Эта функция выпукла и не дифференцируема в нуле. Функция расстояния также дифференцируема всюду, кроме нуля, где она не является дифференцируемой. Однако если выпуклая функция дифференцируема и в некоторой точке ее производная равна нулю, то в этой точке функция достигает своего абсолютного экстремума. И даже более того: график любой выпуклой функции лежит "выше" любой своей касательной плоскости.

Отмеченное обстоятельство очень важно: для выпуклых дифференцируемых функций теорема Ферма является достаточным условием экстремума! Вот одна из причин того, что теория выпуклых экстремальных задач имеет такой завершенный характер.

предыдущая главасодержаниеследующая глава




ИНТЕРЕСНО:

Многомерный математический мир… в вашей голове

В школах Великобритании введут китайские учебники математики

Найдено самое длинное простое число Мерсенна, состоящее из 22 миллионов цифр

Как математик помог биологам совершить важное открытие

Математические модели помогут хирургам

Почему в математике чаще преуспевают юноши

Физики-практики откровенно не любят математику

В индийской рукописи нашли первое в истории упоминание ноля

Вавилонская глиняная табличка оказалась древнейшей «тригонометрической таблицей» в мире

Ученые рассказали о важной роли игр с пальцами в обучении детей математике
Пользовательского поиска

© Злыгостев Алексей Сергеевич, статьи, подборка материалов, оформление, разработка ПО 2001-2017
При копировании материалов проекта обязательно ставить ссылку на страницу источник:
http://mathemlib.ru/ 'MathemLib.ru: Математическая библиотека'
Рейтинг@Mail.ru