Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 84
Текст из файла (страница 84)
Для определения Р, возможно использование какого-либо простого локального метода минимизации; для этих целей можно также использовать и сам описанный метод последовательного перебора с грубым значением е >О. Возможно сочетание описанного метода с каким-либо локальным методом, когда время от времени последовательный перебор прерывается и для уточнения значения Р» из последней найденной точки производится спуск с помощью выбранного локального метода. Недостатком описанного метода является требование знания константы / из условия (3).
Если величина / неизвестна, то можно попытаться взять некоторое начальное значение / = А< и примепять метод с / = /„ 2/„ 4/< и т. д. до тех пор, пока полученное приближение значения /з не будет отличаться от предыдущего приближения не более чем на е. Для уточнения постоянной / можно также использовать результаты проведенных вычислений значений функции на предыдущих итерациях. 4. Для класса ()(7) можно предложить и другой вариант метода покрытий (231), одномерный вариант которого также был рассмотрен в $1.7, и. 4. Предположим для простоты, что в (2) Ь, — а, =... = ܄— а„= «, т. е. «/ — куб с ребрами, параллельными осям координат.
Найдем наименьшее целое число т из условий д/2"+' ~ з/(А "<'и) (т > О) . Через точки с„= (с<«ь ..., С<» ), где с«<=а<+<(Ь< — а,)/2" (<=О, 1, ..., 2", О(/<(т), проведем всевозможные прямые, параллельные осям координат, и разобьем куб </ на систему кубов, которые будем называть кубами /<-го уровня. Тем самым, исходный куб будет иметь нулевой уровень; кубы й+1-го уровня получаются из кубов /<-го уровня делением их ребер пополам и проведением через середины ребер прямых, параллельных осям координат. Далее, пользуясь той же схемой, которая описана в $1.7 (слово «отрезок» теперь нужно заменить словом «куб»), можно организовать перебор кубов различных уровней, последовательно вычислять значение функции /(и) в центрах и< зтих кубов и определять величину Р, = ш<п ./(и<), причем неравенство (1.7.5) здесь следует г«<«в заменить на Р, ( /(и,) — )<и /Ь, + е, где Ь, — длина ребра рассматриваемого на з-м шаге куба с центром в точке и,.
В результате для любой функции Х(и)<в <, (А'), произведя не более 2"" вычислений ее значений, получим решение задачи (1) — (4). В общем случае, когда множество (2) не является кубом, для построения покрытия множества «/ можно воспользоваться параллелепипедами или комбинациями кубов и параллелепипе- 356 методы минимизАции Функции многих пеРеменных 1гл, ь дов. В [231] рассмотрены варианты метода покрытий для более сложяых множеств, задаваемых неравенствами 31(и)<0 (1 ° =1, ..., т). Метод последовательного перебора для других классов функций описан в [139]; об оптимальных последовательных методах на различных классах функций см.
в [21, 106, 228, 282, 298]. 4 13. Метод модифицированных функций Лагранжа 1. Рассмотрим задачу У(и)- ш1; иа У=(ишЕ": иж У„ б1(и)(0, 1=1, ..., т, 31(и)=0, 1 т+1, ..., з), (1) где У(и), д,(и), ..., д.(и) — эаданные функции на множестве Уо. ПУсть Уо ) — оо,Уо ~ 8. Выше (см. теоРемы 4.9.2, 4.9.4, 4.9.5) при определенных условиях выпуклости и регулярности задачи (1) было установлено, что для любой точки по~По найдутся 1* ° 1 множители Лагранжа Л* = (Л„..., Л,): ЛэоиЛо (ЛоиЕ'; Л,>0, Л„>0) такие, что точка (и„, Л*) образует седловую точку функции Лагранжа Ци, Л) = Х(и)+ ~ Лоро(и), иеЕУо Л~Ло (2) 1 т.
е. Ь(ио, Л)(Ь(ио, Ло) = Хо(Ь(и, Л*), иееУо1 ЛЕИЛо. (3) Была также доказана справедливость обратного утверждения: если (ио, Ло) ее Уо Х Ло является седловой точкой функции (2), то иое= Уо (теорема 4.9 1). Основываясь на этих фактах, можно предложить различные методы решения задачи (1), сводящиеся к поиску седловой точки функции Лагранжа. Например, эдесь естественным обраэом напрашивается итерационный процесс, представляющий собой метод проекции градиента по каждой иэ переменных и и Л (спуск по переменной и и подъем — по Л): и„+, — — Рп (и„— аоХ„(иь ЛА)), (4) Ль+г — Рл (Ло+ а„йь(иь Ло)) = Рл,(ЛЕ+ аду(иь)), (5) я = О, 1, ..., где Е„(и, Л) = (Ь„1 (и, Л), ..., Е„о(и, Л)), Ьь (и, Л) = (Еь, (и, Л), „., Ер„,(и, Л)) = (дг(и), ..., бо(и)) = д(и); длину шага а„в (4), (5) можно выбирать иэ тех же соображений, как это делалось выше в т 2. Заметим, что проекция любой точки ЛонЕ' на множество Л, вычисляется просто по З мл мктод»додиеициговлнных функция ллгглнжл З57 формулам Рл«(Л) = (рю "., )д«)«где рд=Л;=шах(ЛьО), »=1,,„,т, р;=Лд, д=-т+1,...,э.
Вместо (4) возможно использование других итерационных процессов, таких, как метод Ньютона и др. В тех случаях, когда задача минимизации функции Ь(и, Л) по переменной и«и У, при каждом фиксированном Л ди А, решается достаточно просто, можно предложить следующий итерационный метод: Х (и»+„Л) = дп1 Ь (и, Л»), Ль+д —— Р„(Ль + аьд (иь«.д)), «ни й О, 1, Однако, как оказалось, сходимость перечисленных методов удается доказать лишь при довольно жестких ограничениях на данные задачи (1).
Приведем простейший пример выпуклой задачи, когда метод (4), (5) не сходится к седловой точке функции Лагранжа. Пример 1. Пусть Х(и)~дО, У=(иыК'. д(и)~и=О). Тот да Х« —— О, дХ« =(0).Функция Лагранжа Х(и, Л)= Х(и)+ Лд(и) Л(и) на дХ,ХЛ,=Е'ХЕ' имеет седловую точку (О, 0), так как Х(0, Л)=0 Л =О=Х(0, 0)=Х(и, 0)=0 и. Процесс (4), (5) здесь имеет вид ид+,=и,-а,Л„, Л«„,=Л,+а„и„, й=О, 1, ... Поскольку иь+д+ Лд+,=(иь + Л~ь) (1 + а[) ) и~» + Ль (д«=0, 1, .. ), то ясно, что при любых (и„Л,) Ф 0 и любом выборе длины шага а„ ) 0 этот процесс расходится. Анализ перечисленных методов показывает, что причина их расходимости заключается в том, что функция Лагранжа (2) по переменной Л не очень хорошо «устроена» и допускает, в частности, случаи, когда в (4.9.38) имеют место строгие включения (см.
пример 4.9.7). Чтобы преодолеть возникающие здесь трудности, можно попытаться видоизменить функцию Лагранжа, строить так называемые модифицированные функции Лагранжа, которые имеют то же множество седловых точек, что и функция (2), и которые обладают лучшими свойствами, чем функция (2). Такие функции, оказывается, существуют и могут быть использованы для поиска седловой точки функции (2) и для решения задачи (1). Следуя [29], мы рассмотрим один из воз можных здесь подходов.
2. Будем рассматривать задачу Х(и)- ш1, и«вдХ=(и«вК": идя дХ, К(и)<0), (6) где Х(и), к(и)=(д,(и), ... д (и)) — заданные функции иэ Сд(У,). Как и в гл. 3, векторное неравенство д (дд, ..., у )> -0 [д~ 0) здесь и ниже означает, что ад~О [я<< 0) при всех 353 МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ КЛ. З 1 1, ..., т, а неравенство а>Ь для а, ЬМЕ" эквивалентно неравенству а — Ь > О. Наряду с классической функцией Лагранжа задачи (6) А (и, Л)=Х(и)+<у(и), Л>, ишь,, ЛюЛ,=(Л~вЕ": Л>0) (7) еще рассмотрим следующую модифицированную функцию Лагранжа: М(™, Л) = Х (и) + ч ~ [(Л + Аэ (и))+)' — 99=А ~ Л ~ (8) переменных и ю У„Л шЛ„где А — произвольная фиксированная положительная константа; в (8) принято обозначение а+ = Р (а) = (а~+, ..., а,+„), а~+= шах(аб О), 3=1,...,т, - проенция точки а се Е" на положительный октант Е+ = (аен Е: а) О).
Нетрудно видеть, что функция ф(г) (шах (г; О))* =(г+)' одной переменной непрерывно дифференцируема на всей число« вой оси Е', причем ф'(г) 2шах(г; О) =2г+. Отсюда следует, что при у(и), я(и)жС'(У,) функция (8) не- прерывно дифференцируя по и и Л, причем — = М„(и, Л) = Г (и) + (д' (и)) (Л + Ая(и))~, — = Ма(и, Л) = — [(Л+ Ад(и))+ — Л|, и~УФ Лен Е, (10) где я'(и) — матрица порядка тХп, у которой в 1-й строке, дг,. (и) у-м столбце д,„; (и) = — *,.
(1 = 1, ..., т, 1 = 1, ..., и), а матрии~ ца (д'(и) )г получена транспонированием я'(и). далее, пользуясь теоремами 4.2.7, 4.2.8 и следствиями из них, нетрудно показать, что если У,— выпуклое множество и функции г(и), я (и) выпуклы на с7„то функция М(и, Л) выпукла по переменной и на множестве У, при любом фиксированном ЛыЕ". Отметим также, хотя это ниже явно не будет использовано, что М(и, Л) является вогнутой по переменной Л на множестве Л, при любом фиксированном ив (7, — в этом проще всего убедиться, доказав неравенство (М,(и, Л) — М,(и, д), Л вЂ” р) ( 0 для всех Л, и ~Л, и затем обратившись к теореме 4.2.4.
Перейдем к описанию метода решения задачи (6), использующего функцию М(и, Л). В качестве начального приближения возьмем любые точки и, ~ (7е Л, ~ Л,. Пусть й-е приближение митод модиюициговлнных юункции лагранжа 359 6 »з! и„»и У»» Хз»и Л, уже известно. Составим функцию Фь(и) = — (и — кл(з+ с»М(и, Ль), иенУо» (11) где а — некоторое положительное число, являющееся параметром метода. Предположим, что существует точка пз, удовлетворяющая условиям иь е= »г»го, Фь (ил) = гп1 Фь (и). и, (а+ — Ь+»»<(а — Ь) 'т»а, Ь»и Ее». Далее, система соотношений Г(0, »»)О, Х»л»=0, »=1, ..., т, (15) (16) эквивалентна равенству »» = (Х+Ал)+ (17) прв любых постоянных А ) О.
В самом деле, если выполкяются сооткошекля (16), то либо д» = О, Х» ) О, либо )»» = О, д»»-0. В каждом вз этях случаев, очевидно, равенство (17) верно. Таким образом, вз (16) следует (17). Докажем обраткое. Пусть имеет место равенство (17). Распишем это равенство в координатной форме Х» = (Х»+Аж)+ = шзх(2»+Аж; 0), ! = 1, ..., т. (17') Отсюда ясно, что Х» ) 0 прк всех ! = 1, ..., т, т.
е. Х» ) О. Если»»» = О, то Л»Г» =0 и, кроме того, пз (17') получим 0 = (О+Айч)+ = 7»»+Ах», В качестве следующего (к+1)-го приближения возьмем точку и„+» такую, что иь+! ен Ую Фь(иле!) <(п1Ф (и) + бь('2, (13) !я (пз+!) е (и») ) бм где бз) О, 11ш ба = О. В частности, если точка п„иа (12) извел» стна, то можно принять и»+, = и„; в общем случае для опреде- ления пзе, из условий (13) нужно решать задачу (12) с по- мощью какого-либо сходящегося метода минимизации. Дальнейшее изложение не зависит от того, каким методом решается задача (12), поэтому здесь мы можем ограничиться предположением, что имеется какой-либо достаточно эффективный метод решения задачи (12), позволяющий ва конечное число итераций найти точку и„+о которая удовлетворяет условиям (13).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
