Ф.П. Васильев - Методы оптимизации (1125241), страница 19
Текст из файла (страница 19)
Тогда по теореме о неявных функциях система (5) имеет решение при каждом г, ~ г ~ < г„, где г, — достаточно малое положительное число, или, точнее, существует непрерывно дифференцируемая векторфункция х = х(г) = (х'(т),... ..., х"(Ф)), такая, что при всех $, ~г! < 1 х(0) =х„, 7(х(г)) =7(х,) — Й д,,(х(г)) =О, з = 1,..., г, (е,, х(г) — х,) =О, з =в+1,..., и — 1. Это значит, что х(2) е Х, 0 < г < т,. Однако 7'(х(г)) = 7(х,) — г < 7" (х,) ЧЗ Е е (О, гг), что противоречит тому, что х„— точка локального минимума. Тем самым доказано, что векторы 7"'(х,), д,'(х,),..., д,'(х,) линейно зависимы, т. е. существует набор Л* фО, что х.„(х„Л ) =О.
Тогда для набора ( Л ) ф ~0 также С„(х„, — Л ) =О. Поэтому можем считать, что Л; > О. Теорема 1 доказана. П Условие (4), в котором используются лишь первые производные функций 7"(х), д,.(х), з = 1,..., г, принято называть необходимым условием первого порядка. Разумеется, в (4) неравенство Л; > 0 вполне можно было бы заменить на Л" < 0 — это принципиального значения не имеет. Однако, следуя традициям, восходящим к Вейерштрассу, в литературе по экстремальным задачам для определенности обычно берут Л,* > О, относя это неравенство к характеристике точки локального минимума.
Из теоремы 1 следует, что'подозрительными на локальный минимум, могут быть лишь те точки х Е Е", для которых существуют множители Лагранжа Л = (Л,..., Л,) такие,, что пара (х, Л) является решением системы Л~У~(х)+ 2 Л,д,'(х)=0, д,.(х) =О, з =1,..., г, Л фО, Л,>0, (6) Пусть в — какая-либо фиксированная точка локального минимума функции 7" (х) на многкестве (1). Множество всех Л, для которых пара (х = в, Л) является решением системы (6), будем называть множителями Лагранжа, соответствующими точке в, и обозначать через Л = Л(в). Нетрудно видеть, что если (в, Л) — решение системы (6), то (в, аЛ) при любом а > 0 также является решением этой системы. Отсюда следует, что множество А(в) является конусом, будем его называть конусом Лагранжа точки о.
3 а м е ч а н и е 1. Поскольку всякая точка х* Е Х локального максимума функции 7'(х) является точкой локального минимума функции ( — 7'(х)), то, применяя теорему 1 к функции ( — 7(х)), получим, что для точки х' необходимо существуют множители Лагранжа Л* = (Л',, Л„') такие, что х"..(х', Л ) =О, Л ~0, Л' < О. Отсюда следует, что подозрительными на локальный максимум функции 7'(х) на множестве (1) могут быть лишь те точки х е Е", для которых существуют множители Л = (Л„*,..., Л,*) такие, что пара (х, Л) является решением системы Лг7"'(х)+ 2; Лтд,.'(х) =О, д,.(х) =О, а =1,..., г, Л фО, Лг < О. (7) г=! Множество всех Л, для которых пара (х = и, Л) является решением системы (7), также является конусом, который мы будем обозначать через Л (в) и называть конусом Лагранжа точки и локального максимума, Отличие этого конуса от конуса, соответствующего точке локального минимума в том, что здесь у всех точек ЛЕ Л (в) координата Л„< О.
Такое соглашение о знаке Л,, несмотря на всю свою условность, ниже позволит нам единообразно формулировать необходимые и достаточные условия экстремума второго порядка, как-то упорядочит процедуру исследования точек экстремума. Из теоремы 1 и замечания 1 следует, что в точке в экстремума функции Г'(х) на множестве (1) конус Лагранжа не может быть пустым — если этот конус пуст, то такая точка в заведомо не может быть точкой экстремума. Из того, что множество множителей Лагранжа является конусом, условие Л ф 0 в (6), (7) можно заменить каким-либо условием нормировки, взяв, в например, )Л)' = 2; Л,'. = 1. Вместо отдельного исследования систем (6), (7) г=в можно рассмотреть одну систему х.
(х, Л) = Л„~'(х) + ~,' Л д '(х) = О, д,.(х) = О, а = 1,..., г, г=! (л„л„..., л,) Фо, последовательно полагая в ней Л„ = 1, Л„ = -1 и Лг = О, ~ Л, = 1. 2 ~=1 Система (8) с учетом условий нормировки представляет собой систему и+ г+ 1 уравнений с и+ в+ 1 неизвестными (х, Л) = (х',..., х", Лю Л„... ..., Л,). Решив ее, мы найдем точки х=о множества (1), подозЕительные на экстремум, и соответствующие им множители Лагранжа Л = Л(в). Для вы- яснения того, будет ли в этих точках в действительности реализовываться локальный минимум или максимум, нужно провести дополнительное изуче- ние свойств функции 7(х) в окрестности точки в с учетом ограничений (1).
Здесь могут быть привлечены геометрические, физические и т. п, сооора- жения. При выполнении. условий теорем Вейерштрасса из $1 можно быть уверенным, что хотя бы одна из найденных точек в окажется точкой гло- бального минимума или максимума. Для выяснения характера экстремума точек в могут быть привлечены вторые производные функции Лагранжа по переменной х — об этом речь пойдет в Э 5. 62 Гл.
2. КЛАССИЧЕСКАЯ ТЕОРИЯ ЭКСТРЕМУМА 5 3. ЗАДАЧИ НА УСЛОВНЫЙ ЭКСТРЕМУМ Изложенная схема поиска экстремума функции на множестве (1) составляет суть правила (метода) множителей Лагранжа. Для иллюстрации этого правила рассмотрим несколько примеров. Пример 1. Пусть требуется на и-мерной единичной сфере Х = = (х е Е": ~х~' = (х, х) = 1) найти точку, сумма квадратов расстояний от которой до р данных точек х„..., х была бы минимальной. Иначе говоря, в нужно минимизировать функцию г"(х) = 2 ~х — х,.~' при условии д(х) = !=! = (х, х) — 1 =0. Как и в примере 2.2, здесь удобнее пользоваться следуюпшм р Р пРедставлением фУнкции Г(х) = Р(х~' — 2Р(х, хо) + 2 (х,)', где хо = — 2; х,.
!=! != ! Составим фУнкцию ЛагРанжа этой задачи: С(х, Л) = ЛоУ(х)+ Л ((х, х) — 1). Система (8) имеет вид С,(х, Л) =2РЛ,(х — х )+2Лх=О, (х, х) =1, (Л„, Л) фО, (9) При Л„= 0 эта система, очевидно, не имеет решения. Поэтому здесь можем принять Л = 1 или Л, = — 1.
При х ~0 из системы (9) получаем две точки: в! = — и о = — —, подозрительные на экстремум. Соответствую!дне этим !о! ' !оР точкам множители Лагранжа нетрудно выписать явно. Однако они нам ниже явно не понадобятся, важен лишь факт их существования. Поскольку Х компактное множество, функция г"(х) непрерывна на Х, то согласно теоремам 1.1, 1.4 эта функция достигает на Х своего глобального минимума и максимума. Но точки глобального экстремума, конечно же, удовлетворяют системе (9).
Но система (9) при х ф 0 имеет всего два решения в! и оы Следовательно, одна из этих точек является точкой глобального минимума, другая — точкой глобального максимума. Вычислив и сравнив значения У(о!),1'(о,), нетрудно убедиться, что о! = — — точка глобального минимума со значением г"(в!) =г"„= р — 2~ ~; х! + ч~; х~, в, = — -8!! — точка глобального максимУма со значением У(оо) = Г"' = Р+ 2~ 2 х!~ + 2; х!. По!=! ' !=! скольку при х ф 0 у функции 1'(х) других точек экстремума на Х нет, то у(о!) < у(х) Ух Е Х, хаев!, и у(х) < у(и,) !гх Е Х, х фым т.
е. экстремумы строгие. Рассмотрим случай х = О. Тогда системе (9) удовлетворяют все точки в, для которых ~о~ =1. Это значит, что из необходимых условий экстремума (9) при х =0 нам не удалось извлечь никакой полезной информации — все точки единичной сферы как были, так и остались подозрительными на экстремум. Однако нетрудно убедиться, что при х, = 0 Т" (х) = р+ 2,' хз = сопз1 !=! Ух е Х, и рассматриваемая задача стала тривиальной: можно сказать, что все точки х е Х являются точкой абсолютного минимума (или максимума). П р и м е р 2.
Определим точки экстремума функции У(и) = х на множестве Х = (и = (х, д) е Е'! д(х) = х' — д' = О). Функция Лагранжа здесь равна й(и, Л) = Л х+ Л(х' — у'). Система (8) запишется в виде: Ло+ЗЛх~=О, — 2ЛУ=О, хз — уз=О, (Ло,Л)фО Из этой системы находим единственную точку в = (О, 0), подозрительную на экстремум. Ей соответствует конус Лагранжа А(в) = (Л = (Ло = О, Л): ЧЛ ф О). Нетрудно видеть, что точка в = 0 в этой задаче является точкой глобального минимума.
В самом деле, из равенства хо — у' = 0 следует, что Яи) = х = (у')ив > 0= г"(0) = г", !Уи 6 Х. Здесь т"" = +ос. 2. Изложим правило множителей Лагранжа для задачи поиска точек экстремума функции г(х) на множестве, имеющем более общий вид; Х=(х ЕЕ": д(х)(О,...,д„(х) (О,д,„„(х)=0,...,д(х) =О), (10) где предполагается, что функции у(х), д,(х),..., д,(х) определены на всем пространстве Е'. Ограничения д,(х) = О, з = т + 1,..., в, как и в (1), будем называть ограничениями типа равенств, а ограничения д,.(х) < О, о = 1,..., гп — ограничениями типа неравенств. В (10) не исключаются возможности, когда отсутствуют ограничения типа равенств (з = тп) или типа равенств (гп = 0); при з = гп = 0 множество Х = Е" получаем задачу на безусловный экстремум из $2.
Для исследования задачи поиска экстремума функции г(х) на множестве (10) введем функцию Лагранжа Л ~0, Л*>0, Л!*>О,, Л* >О, л,,(х„, Л )=О, Л;д,(х,)=0, 4=1,..., гп. Отметим, что теорему 2 в литературе иногда называют теоремой Каруша — Джона 1234; 586). Доказательство этой теоремы требует развития некоторого математического аппарата, и оно будет ниже проведено дву. мя способами для несколько более обших множеств, чем (10) (см.
$4.8, 5 6.16). Из теоремы 2 следует, что точками локального минимума функции Г"(х) на множестве (10) могут быть лишь те точки х Е Е", для которых существуют множители Лагранжа Л = (Л„,..., Л,), такие, что пара (х, Л) является решением системы Лог'(х)+ 2, Лзд,.'(х)=0, Л,д(х)=0, д(х)(0, о=1,...,т, в= ! д(х)=0, Е=гп+1,...,з, Л~О, Л„)0, Л,)0, ..., Л,„)0. (11) Пусть в — какая-либо фиксированная точка локального минимума функции у(х) на множестве (10).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
