Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 21
Текст из файла (страница 21)
е. <Уи(о)Ь, Ь>)0 для всех ЬтиО, то о — точка локального минимума функции 1(и); если (1" (о)Ь, Ь> отрицательно определена, т. е. (Уи (о)Ь, Ь> ~ 0 при всех ЬФ О, то ив точка локального максимума; если ясе квадратичная форма <1'(о)Ь, Ы знакопеременпа, т. е. может принимать как положительные, так и отрицательные значения, то в точке о функция 1(и) не имеет локального минимума или максимума. кллссичкскни мктод 81 з Напомним, что квадратичная форма (Аи, и) = ~~ апи'и> будет положительно определенной тогда и только тогда, когда все угловые миноры матрицы А, т.
е. определители [пд ... ам[ м " м положительны; форма <Аи, и> отрицательно определена тогда и только тогда, когда (-1)'Л~)0 (1=1, ..., и), т. е. знаки угловых миноров Ло ..., Л чередуются, причем Ь,(0. Таким образом, для проверки знакоопределенности квадратичной формы (У" (и)Ь, Ь> достаточно вычислить угловые миноры матрицы l" (г) и исследовать их знаки. В том случае, когда в стационарной точке квадратичная форма (Х"(г)Ь„ Ь> не меняет знака при всех Ь~н Е", но может равняться нулю при некоторых Ь Ф О, то для выяснения поведения функции в окрестности точки и монгно привлечь старшие производные и связанные с ними формы более высокого порядка: где суммирование проводится по всем целым г„..., г„таким, что 0<г~<т (1=1, ..., и, г,+...+г„=т>3). Однако на практике исследование характера стационарных точек с помощью форм й У(о) (т ~ 3) почти не применяется из-за его громоздкости.
В тех случаях, когда указанным выше путем удается выявить все точки локального минимума [максимума[ функции У(и), то для определения глобального минимума [максимума) этой функции на всем пространстве Е" нужно перебрать все точки локального минимума [максимума) и из них выбрать точку с наименьшим [наибольшим] значением функции, если такая точка существует. Пример 1. Пусть в пространстве Е" даны и точек и; = = (ич °, и";) (1=1, ..., т) и требуется найти точку и ~иЕ", сумма квадратов расстояний от которой до этих данных точек минимальна. Иначе говоря, требуется минимизировать функцию Х(и) = ~ [и — и; [з на Е".
а=1 Поскольку У'(и) = 2 ~ (и — и;),то система (5) здесь выгля~=1 дит так: ти — ~~ и; = О. Отсюда получаем стационарную точку 82 ПРСДВАРИТГЛЬНЫЗ СВКДГНПЯ [гл. 2 из = — г и;— = и„подозрительную па экстремум. Матрица вто1=1 рых производных равна У" (и)— = 2гаЕ прп всех и~Е, где Е— единичная матрица размера пХп, т.
е. матрица, у которой элементы аз=1, ао=0 при 1Ф~' (1, 1=1, ..., и). Отсюда ясно, что <У" (и) Ь, Ь> = 2пз!Ь!') 0 при всех Ьчь О. Это значит, что в точке и„= и, достигается локальный минимум. Однако здесь можно сказать больше: в точке ие = и„функция У(и) достигает своего глобального минимума на Е". В самом деле, рассматриваемая функция такова, что Иш У(и) = оо. Тогда по теореме 1.3 мно~ю жество Уе точек минимума У(и) на Е" непусто.
Кроме того, во всех точках из~Уз должно соблюдаться равенство э" (из) =О. Как выяснилось, последнее равенство выполняется только в точке и = иэ. следозателы1о, 7Ув = (из), Ув = У(из) = ~', (иэ — и1!'. 1=1 3. Задачу поиска экстремума функции на всем пространстве Е", которую мы только что рассмотрели, принято называть задачей на безусловный зкстремум.
В этом названии отражен тот факт, что на переменные и = (и', ..., и") никакие дополнительные условия н ограничения не накладываются. Наряду с задачами на безусловный экстремум имеется немало задач, в которых переменные пе могут быть совершенно произвольнымп п должны удовлетворять некоторым дополнительным условиям, выража1ощим, например, условие неотрицательности тех или иных переменных, условия ограниченности используемых ресурсов, условия нормировки, ограничение на параметры конструкции системы п т. п.
Иначе говоря, переменные и=(и', ..., и ) должны принадлежать некоторому заданному мноясеству У из Е", причем УМЕ". Тогда чтобы подчеркнуть, что экстремум функции ищется при условии и1н УМЕ", часто говорят о задаче на условный экстремум. В классическом математическом анализе традиционно рассматривается следующая задача на условный экстремум: найти экстремумы функции з(и) при условии, что переменные и =(и', ..., и") удовлетворяют ограничениям [10, 160, 165, 233] (6) д,(и) О, ..., у,(и)=0; при этом предполагается, что функции У(и), у;(и) определены и имеют непрерывные частные производные первого порядка на всем пространстве Е".
Ограничения (6) принято называть ограничениями типа равенств. Таким обрааом, здесь мы имеем дело с задачей поиска экстремума функции У(и) па множестве У=(и: и~Е", д;(и)=0, 1=1, ..., з). кллссичкскип мктод з 2~ В тех случаях, когда систему (6) удается преобразовать к эквивалентному виду и,=а,(и'+', ..., и"), ..., и„=а„(и"+', ..., и"), (7) » Ы (и, Л) = Л»Х(и) + ~ Лду, (и) »=.л (6) переменных (и', ..., и", Л», Л„..., Л,)=(и, Л)~Е"+'»». Т е о р е м а 1. Пусть е — точка локального лсинимума или максиллума функуии У(и) на множестве л»», задаваемом ограничениями (6), функ»сии Х(и), д,(лл), ..., д,(и) непрерывно диффере~щируемы в окрестности точки ив.
Тогда необходимо существш»от числа (Лг, Лд, ..., Л,) =- Ли =~ О, называемые множителями Лагранжа, такие, что » д2'(и, Л))» ду (и„) '~~ » д г (и») диЛ и=-и» диЛ . диЛ (9) т Доказательство. Поскольку не все числа Л», ..., Л» равны пулю, то условие (9) означает, что векторы У'(ие), » дл (ил), ..., ь.. (лле) линейно зависимы. Допустим противное: пусть зтн векторы линейно независимы. Тогда г+ 1 ( и. В случае в+1(п возьмем какие-либо векторы е,то ..., е„, так, что- Р бы спстема Г(ие), д,(ие), ..., д»(ие)» е,+„..., е„, образовала базис в Е". Введем функции /(и, 1) =У,(и, Е), (л(и,й),...,~ -,(и,С)): у,(и,г)=Х(и) — д ( )+ С, )л(и 1) = ул( ) (л=1, ...,г); (л(ид= = л',ел, и — и„) (1= в+ 1,..., и — 1) переменных (и, 1)~Е"+» и рассмотрим систему уравнений /,(и, 1)= О, )»(и, 1)= О, ..., )„»(и, 1)= 0 выразив из (6) первые р переменных через остальные, рассматриваемую задачу на условный экстремум можно свести к задаче на безусловный экстремум функции лр(ит+», ..., и") = = 3(а,(и"+', ..., и"), ..., аг(и'+», ..., и"), и»+', ..., и") переменных (ив+»,..., и")~ Е" ', которую можно исследовать, например, по описаннои в п.
2 схеме. Однако зтот подход имеет ограниченное применение нз-за того, что явное выражение вида (7) одной группы переменных через остальные переменные удается получить лишь в редких случаях. Более общий подход к исследованию задачи поиска экстремума дифференцнруемой фупллции г(и) при ограничениях (6) дает метод множителей Лагранвла. Зтот метод заключается в следующем. Вводится функция Лагранжа 84 пгедвагительные сведения ~гл. 2 относительно и неизвестных и=(и', ..., и").
Для ее исследования воспользуемся теоремой о неявных функциях [10, 160, 165, 233). Заметим, что ~(ие, 0) = О. Далее, функции (;(и, 2) непрерывно дифференцируемы в окрестности точки (ие, 0) ~ Е~~, причем (еи (ию 0) = У' (иг), 1';„(иг,О) = у~(иг) (1 =1, ...,г); (ю(июО) =е; (2 = 2+1,...,и— — 1). Это значит, что в точке (ие,О) якобиан системы функций 1,(и, 2) (1=0, 1, ..., и — 1), представляющий собой определитель квадратной матрицы со строками У' (ие), д, (иг), .
° ,д,(и ),е,+„..., е„„образующими базис в Е", отличен от нуля. Тогда по теореме о неявных функциях система Ди, г)=0 имеет решение при каждом 2 (Ы ( 2,), где 2, — достаточно малое положительное число, или, точнее, существует вектор-функция и и(2)=(и'(2), ..., и" (г)), которая определена и дифференцируема при всех 2 (~2! ( 2,) и такая, что и(0) = ие, У (и(2)) = Х(ие) — 2, л2 (и(г)) = О, 1 = 1,..., г; (еи и (г) — и,) = О, 1 = г + 1, ..., и — 1. Это значит, что и(Ю)ы У, !Н ~2п и(2)-эие при 2- О.
Отсюда же имеем .7(и(г))=У(и ) — 2<7(и„) ~У(и ) + 2 = 7(и( — 2)) ч2ел(0, Г,), что противоречит тому, что иг — точка локального экстремума. Из теоремы 1 следует, что подозрительными па экстремум могут быть лишь те точки и, для которых существуют множители Л=(Л„Ло ..., Л,) такие, что точка (и, Л)ыЕ"+'+' удовлетворяет системе п+ г уравнений ди2 ди' и, кроме того, пзвестно, что Л =(Л„Л„..., Л,)чьО.
Нетрудно видеть, что если (Р, Л) — решение системы (10), то (и, аЛ) при любом а чьО таклге является решением этой системы, т. е. мноягители (Л„Ло ..., Л,) из (10) определяются с точностью постоянного множители. Поэтому множители Л моя~но подчинить какому-либо дополнительному условию нормировки, например, в Л,)О, 1ЛГ2= ~ Л',=1. (11) $=-о Если система (10) имеет решения (и, Л) такие, что Л,чьО, то задачу минимизации У(и) при условиях (6) называют регулярной (невырожденной) в точке и. В регулярной задаче условие нормировки (11) можно заменить более простым условием Л, = 1. Нетрудно видеть, что для регулярности задачи в точ- кллссическгги ыетод 85 Р ке о достаточно, чтобы векторы уг(о),...,у,(о) были линейно независимы, т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
