Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 22
Текст из файла (страница 22)
е. чтобы равенство агд,(о) + ... + а,у,(о) = 0 было возможно только при а, =... = а, = О. Условия (10) с условием нормировки (11) (или Лг = 1) представляют собой систему и+ в+ 1 уравнений с и+ в+ 1 неизвестными (и, Л)=(и', ..., и", Л„Л„..., Л,). Решив ее, мы найдем точки о ~ П, подозрительные на экстремум, и соответствуюгцие пм множители Лагранжа Л =Л, =(Л„Ло ..., Л.)ФО.
Для выясненпя того, будет ли в этих точках в действительности реализовываться локальный минимум илн максимум, нужно провести дополнительные исследования с привлечением вторых производных функции Лагранжа по переменной и. Теорема 2. Пусть: 1) функг(ии г(и), д,(и), ..., д,(и) дважды дифференуируемы в точке о ж П = (и я Е": д, (и) = О, ... д,(и) = 0); 2) точка (о, Л,) удовлетворяет условиям (10), (11); 3) квадратичная форма <.х .(о, Л,))г, тг>>0 [<0) (12) ири всех )г, для которых (.Т'(о),й)(0 [)О[, (у;(о),н) = О, г = 1, ...,в; 64=0.
(13) Тогда в точке о функция г'(и) на П илгеет строгий локальный минимум [максимум). Д о к а з а т е л ь с т в о. Допустим противное: точка о удовлетворяет условиям теоремы, но не является точкой строгого локального минимума г(и) на гг'. Тогда найдется такая последовательность (и„), что у,(ид) = О, ..., д,(и,) =О, ад Ф о, гг = 1, 2, ...; (предполагаем, что о не является изолированной точкой множества П; всякая изолированная точка множества П может считаться точкой строгого локального минимума или максимума и оез выполнения условий (10) — (13)). Точку и, можно записать в виде ид — о ид — г ид = о + [ ид — о [ = о + (дед, ед = [и — о[ ' [ид — и[' гд = [ ид — о[, (гд) -~ О.
Поскольку [е„[ =1, то, выбирая при необходимости подпоследовательность„можем считать, что (е„) - е„[е,[ = 1. С учетом (14) и дифференцируемости функций Х(и), уг(и) в точке о имеем 0~1(ид) — Х(о) = (Г(о), ед) гд+ о((д), 0 = д (ид) — у (о) = (у1 (о), ед) гд + о (гд) ПРЕДВАРИТЕЛЬНЫЕ СВЕДЕНИЯ [гл. 2 для всех 1 = 1, ..., г, й = 1, 2, ... Разделив зтп соотношения на 1,> 0 и устремив й — ~ ", получим <Х'(и), е,> ( О, (й (В), е,) = = 0 (1 = 1,..., 2), так что е, удовлетворяет условиям (13).
Далее, из того, что иа, и я У, Л, > О, и из (14) имеем Я (ид, Л,) = Л,Х (из) + ~. Л[д[ (из) = ЛВХ (ид) ( ЛзХ (В) = Л,Х (г) + 1=1 + ~ Л[д[(и) — — 2'([[, Л,). Отсюда с учетом условия (10) и дваж1=1 ды дифференцируемостп функции 2'(и, Л„) в точке и получаем О ) 2' (им Л ) — 2' (и Я а) =, [~, (3'и ~ (и, Л, ) ею еи) + о ( [и) л = 1, 2, ... Разделив зто неравенство на [~з ) О и устремив й - оа, будем иметь <Ыии (п~ Лс) ее ео> ~ 0 что протиВоречит услоВиям (12), (13) .
Аналогично исследуется случай, когда и — точка строгого локального максимума. Пример 2. Пусть требуется на в-мерной единичной сфере 77 = (и ~н Е": [и[' = <и, и> = 1) найтп точку, сумма квадратов расстояний от которой до ш данных точек и„..., и„[ИЕ" была бы мингмальной, т.
е. нун[но минимизировать функцию Х(и) =- = ~ ~ и — и[ '[1 прп условии <и, и> = 1. 1=1 Для решения етой задачи составим функцию Лагранжа Ы(и, Л)= Л,Х(и)+ Л(<и, и> — 1). Спстема (10) примет впд 2'„(и, Л)=Л1 2л[(и — и,)+2Ли= О, <и, и> =1, (15) где из = — ~~ и[ (см. пример 1). Очевидно, прн Л, =0 система 1=-1 (15) не пмеет решенпя с (Л„Л)~0, позтому мол[ем прнгять Л, = 1, Тогда нз (15) при и,Ф 0 получим две точки В[ = и.,/~и,! н [ч = — и,/[и,!, подозрительные на минимум, и соответствующие пм множители Лагранжа Л, = лт([и,! — 1) н = т( — !и,! — 1). Ыатрпцы вторых производных функции Лагранжа в найденных точках (ип Л~) п (гм Л,) равны соответственно 2~и,!тЕ и — 2!и,!тЕ, где Š— единичная матрица.
Отсюда ясно, что в точке и, достигается локальный в[пнимум, а в точке В, — локальный максимум функции Х(и) при условии ~и~ =1. Поскольку У вЂ” компактное множество, Х(и) непрерывна на У, то согласно теореме 1.1 на [Х функция Х(и) достигает своего глобального минимума н максимума. Но точки глобального зкстремума, конечно же, удовлетворяют системе (15). Как выяснилось, прп поФО система (15) имеет всего два решения и, н п,.
Следовательно, В, = и,/~и,~ — точка глобального мнни- кллсспчвскшг метод 87 ем мума, о, = — и,l!и,~ — точка глобального максимума прп и,Ф О. Таким образом, искомая точка есть ие = ие,~(и,( прп и ~ О. Рассмотрим случай и, = О. Тогда решением системы (15) нвляется точка (о, Л„Л), где Л, = 1, Л = — т, а и — произволь- ная точка, для которой !о! =1. Это значит, что нз необходимых условий экстремума (15) при и0 = 0 не удалось извлечь никакой полезной информации — все точки единичной сферы как были, так п остались подозрительными на экстремум.
Тем не менее адесь нетрудно разобраться в происходящем. А именно, при и, =0 для всех и ~ У имеем У(и) = ~,' (~ иà — 2 (и, иО+~ и;!г) = г=г вв Ъ т т = гп — 2( и, ~,', и) + ~~о~ ( и.„)г = т — ~~ (и;)г .= сов1. Таким обг=г г —.--1 1=1 разом, прн и, = 0 рассматрпваемая задача становится тривиаль- ной: У(и) = сонет на гУ, т. е. можно сказать, что во всех точках и — (У фупкцпя достигает глобального минимума (нлп макси- мума). Пример 3.
Пусть требуется найти точки экстремума функ- ции У(и)=х на множестве РУ=(и=(х, у)жЕ1, х' — у'=О). Применим метод множителей Лагранжа. Здесь функция Лагранн'а такая: Ы(и, Л)=Л,х+Л(х' — у'-). Система (10), (11) имеет впд У о + ЗЛх = О, 2Лу = О, тз — у' = О, Лез + Лг =- 1, Ло ~ )О. Нетрудно видеть, что она совместна лишь прп Л, = 0 и выделяет единственную точку о = (О, 0) = О, подозрительную на экстре- мум. Таким образом, рассматриваемая задача нерегулярна в точ- ке о= О. Она просто решается, если из равенства х' — у' = 0 выразпть х = у"' и заметить, что У(и) = у"' ( — < у < ). Ясно, что о=(0, 0) — точка глобального мпнпмуг1а функции У(и) па гУ.
4. Метод множителей Лагранжа может быть применен для поиска экстремумов функции и в тех случаягэ когда на пере- мепныо и=(и', ..., и") наряду с ограничениями (6) тапа ра- венств накладываются еще ограничения Ь,(и)<0, ..., Ь (и)<0, называемые ограничениями тина неравенств. Будем предполагать, что функции У(и), д,(и), Ь;(и) (1= = 1, ..., з, 1 = 1, ..., т) определепы н дпфференцпруемы во всех точках и ~Е". Оказывается, если ввести новые вспомогательные переменные и =(иг', ..., ю"), связанные с походными переменпымп и =(и', ..., и') соотношениями (ю') ' + Ь, (и) = О, ..., (ю") '+ Ь„(и) = О, (17) то задача поиска экстремумов функции У(и) при ограничениях (6), (16) сводится к равносильной задаче поиска экстремумов ПРЕДВАРИТЕЛЬНЫЕ СВВДВНИЯ ~гл.
3 той же функции в пространстве переменных й=(и', ..., и", и1', ..., в'")=(и, и1) при ограничениях типа равенств (6), (17). Равносильность этих двух задач понимается в следующем смысле: если и„— точка локального минимума [максимума) функции У(и) при ограничениях (6), (16), то и„=(и,и ), где 1г =(и'„,...,В1,), и1', =-( — й;(из))'~' (7=1,...,т) будет точкой локального минимума [максимума) функции Х(и) при ограничениях (6), (17), и наоборот, если и,= (иэ, ю„) — точка локального минимума [максимума[ функции 1(и) при ограничениях (6), (17), топе — точка локальпого мипимума [максимума] У(и) при ограничениях (6), (16).
Таким образом, для поиска экстремумов функции У(и) при ограничениях (6), (17) можно ввести функцию Лаграняза в Р$ .й (и, и, Х, 11) = Л,Х(и) + ~З~ >1у1(и) + ~, р ((и11) + йз(и)) 1 1=1 и в соответствии с изложенным в п. 3 написать необходимые условия экстремума в виде системы (10), найти точки, подозрительные па экстремум, выявить среди них точки локального миннмума нлп максимума, а затем, исключив переменные ю', ..., и1", получить точки экстремума функции У(и) при ограничениях (6), (16).
П р и м е р 4. Пусть требуется в и-мерном единичном шаре У = (и: и1ВЕ", 1и1'= (и, и> ~1) найти точку, сумма квадратов расстояний от которой до и данных точек и1, ..., и„шЕ" была бы мпннмальной, т. е. требуется минимизировать функцию У(и) = ~~ 1и — и111 при ограничениях <и, и> (1. 1=1 Из примера 1 следует, что глобальный минимум функции У(и) на всем пространстве Е" достигается в точке и~ = и, = т 1 чгт — ~ иоПоэтому если 1и,1~ 1, то эта точка и, будет решени1=1 ем рассматриваемой задачи.
Остается рассмотреть случай [и,1) 1. Введем новую переменную и1 соотношением и11 + (и, и> — 1 = 0 (18) и рассмотрим задачу минимизации функции Х(и) в простран- стве переменных й = (и, и1) =(и', ..., и, и1)1н Е"+' при ограни- чениях (18). Составим функцию Лаграпн1а 2'(и, >) = Хз ~ [и— ' 1=1 — и111+ Л(1оз + 1и[1 — 1). Система (10) будет иметь вид 2' = 2»,т(и — и,)+ 2).и = О, 2' = 2Хи1 = О, и1'+ 1и1* — 1 = О, кльссическни метод 89 где Л =(Л„Л)Ф О.
Напоминаем, что !и0! > 1. Очевидно, при Л,= = 0 эта система не имеет решения. Поэтому можем принять Л, = 1 и переписать систему в виде (и+Л)и = ти„Лю = О, 2а'+ (и!' = 1, (и,! > 1. (19) Заметим, что здесь случай Л = 0 невозможен, так как тогда и= и, и !иР =!и,!'= 1 — 2а' ~ 1, что противоречит условию (и,! > 1. Коли же ЛФ О, то из (19) получаем два решения э, = =(и/1и,1, 0), Л,=т(1и,! — 1)>0 и Р,=( — и/!и01, 0), Л,= = — л2(!и,!+1)(0.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
