Ф.П. Васильев - Методы решения экстремальных задач (1981) (1158203), страница 17
Текст из файла (страница 17)
е. (е„од) ы )!Р» и о»=рп(о. Так как г=(0, 0) а=К», то ясно, что п»«0. Имеются две возможности: 1) од « — ед. Тогда направление е» Ф 0 является возможным направлением убывания функнии р'(и) в точке и» на множестве (.Р. Полагаем и»„= и»+а»ем 0 < ссд «р»; еды — — ед, (33) где Р»=зпр(сс: ид+(едеп(р', 0«( =а))0. 2) — ед(од =.О. Тогда полагаем ид„=и», едрр=аед, 0<а<1, где а — параметр метода, и снова переходим к рассмотрению задачи (32) с заменой множества (» на множество )„,,=-(Е 1«.
р'«т, — е»„«ир(и») «О). Величина а» в (ЗЗ) может выбираться из условий: 1) )д(а») = )п( )д(сс) =)»„где )д(а) = )(и»+аед). »(а(ад На практике это условие можно реализовать приближенно в следующем смысле: 1д(а»)«1»,+6», 6»)0, '~~ 6»(со, д=» или )»(ад)«(1 — Лд) )(ид)+Л»7»„, 0<Л«Лд«1. 2) Можно задать а»=!)», проверить условие монотонности: ) (и»»р) ( ) (ид), а затем при необходимости дробить а„до тех пор, пока не выполнится условие монотонности.
3) Если р'(и) ~ С' ' ((р) и константа Липшица Е для ,р" (и) известна, то в (33) можно принять ссд=пп)п(()»', !од! Ц, 4) Возможен выбор а» из условия У (ид) —,1 (и, +а,е») =-- еа»,' о» !, 0 (е (1)2; для определения такого а» сначала можно положить ад= !)д, а затем при необходимости дробить эту величину. 83 Заметим, что задача (32) далеко не всегда просто решается.
Поэтому методом возможных направлений пользуются для решения лишь таких задач (31), в которых решение вспомогательных задач (32) может быть легко найдено. Предлагаем читателю самостоятельно исследовать сходимость этого метода и рассмотреть, в частности, возможность обобщения теоремы 5.5.2 из 14)на случай банаховых пространств.
5. Метод сопряженных направлений применяют для решения задачи / (и) -э(п1; и е= Н, где Н вЂ” гильбертово пространство, ) (и) ен С'(Н). Зтот метод заключается в построении последовательности (и») по правилу и»„=и» вЂ” а»ры Ь=О, 1, ", (34) где ро = Г (ио), р» = .)'(и») — 6»р»-ь й = 1, 2, ..., (35) величина Р» определяется по одной из формул Р = (Г (и ), /' (и ,) — э" (и )) ) Г (и он)>-', или (1»= — ) У'(и„)10~ У'(и»,) 1-0, а а„в (34) находят из условия )» (а») = !п1 )» (а), )» (а) = / (и» вЂ” ар„), а ) О. (36) а')о Как показывает практика, погрешности, неизбежно появляющиеся при определении а, из условия (36), могут привести к тому, что векторы (р») из (35) перестают указывать направление убывания функции и сходимость метода может нарушиться.
Чтобы бороться с этим явлением, метод сопряженных градиентов время от времени обновляют, полагая в (35) (1»=0. В отличие от конечномерных пространств (см. с 5.6 из 141), в гнльбертовых пространствах нельзя ожидать, что точку минимума сильно выпуклой квадратичной функции ) (и) = - - (Аи, и) — (Ь, и), и ен Н, А ~ Х (Н -+ Н), Ь ен Н, 84 удастся найти за конечное число шагов метода сопряженных градиентов.
Предлагаем читателю самостоятельно сформулировать и доказать аналог теоремы 5.6.1 из [41 для гильбертовых пространств, а также рассмотреть возможность при-. менения метода сопряженных градиентов к задаче (1) — (3). 6. Метод Ньютона может быть использован для решения задачи !п(; и и, где У вЂ” выпуклое замкнутое множество пз банахова пространства В, / (и) еи С' (Ц. Зтот метод заключается в построении последовательности (и») по следующему правилу: по известному А-му приближению и» ~ (/ находят вспомогательное приближение й, еи(7 из условия (» (и») = )п! .)» (и), (37) где ,1»(и) =(('(и»), и — и»)+ „— (У" (и,) (и — и»), и — и,), и — и, н затем полагают и»„= и» -(- а» (й» вЂ” и„), О ( а» ( 1. (38) В частности, если У=В, то в точке минимума функнии ,(»(и) ее производная У;(и) обращается в нуль, т. е.
1» (й,) = 7' (и») + 7" (и,) (и» вЂ” и») = О, Если оператор ("(и») имеет обратный оператор (У" (и»))-', то отсюда имеем и» = и» вЂ” (Х" (и»))-' У' (и,). Подставляя это выражение для и» в (38), получим и,„,=и» вЂ” а»(Г'(и»))-'У'(и»), й=О, 1..., (39) Таким образом, при (/=В метод (37), (38) представляет собой широко известный метод Ньютона для решения операторных уравнений (в данном случае уравнения .У (и) =0). Существуют различные способы выбора величины а, в (38). Приведем некоторые из них: 1) в (38) часто полагают а»=1, А=О, 1,, В этом случае прн У=В нз (39) имеем и„„=и» вЂ” ()" (и»))-'('(и»), А=О, 1, ..., — это классический вариант метода Ньютона решения уравнения У' (и) =О.
2) В качестве яз в (38) можно принять а,=Л", где (а — минимальный среди номеров 1) О, удовлетворяющих условию 7 (и,) — 7 (их+ Л' (и, — иа)) ) аЛ' / Уз (и,) /, где Л, е — параметры метода, 0<Л; а <1. 3) Возможен выбор а, в (38) из условий )~(сх~) = ппп 1,(а), ~,(а) =У(и„+я(и~ — и,)). 0<а(! 4) Иногда полагают а„= 1, проверяют условие монотонности: l (и„„) < У (и„), а затем при необходимости дробят аа до тех пор, пока не выполнится условие монотонности. Метод Ньютона обычно применяют в тех случаях, когда вычисление производных ('(и), l (и) не представляет особых трудностей и вспомогательная задача (37) решается достаточно просто. Предлагаем читателю самостоятельно сформулировать и доказать аналоги теорем 5.7.1 — 5.7.3 из 141 о сходи- мости метода Ньютона для задач минимизапии в банаховых пространствах.
Достоинством метода Ньютона является высокая скорость сходнмости. Однако этот метод весьма чувствителен к выбору начально приближения иэ — если точка и, далека от искомой точки минимума, то метод может не сходиться. 7. Метод с кубической скоростью сходнмости, изложенный в З 5.8 пз [4) (см. также 12231), может быть применен для решения задачи у (и) -э !п1; и я В, где  — банахово пространство, 7(и) енС'(В).
Для описания этого метода нам понадобится понятие разделенной разности для градиента. О п р е д е л е н и е 4. Пусть ./ (и) ен С' (В). Разделенной разностью градиента 7'(и) называется линейный симметричный оператор Г (и, о), действующий из В в В* и такой, что У' (и, о) (и — о) = Х' (и) — У' (о) (40) при всех и, вен В. Заметим, что равенство МО), вообще говоря, неоднозначно определяет оператор ('(и, о) яЖ(В-~В*). Мы 86 будем дополнительно к равенству (40) еще требовать, чтобы для функций У(и) ен С'(В) оператор Г (и, о) удовлетворял условию г'(и, о)= /" (и)+е(и, о), и, оенВ, (41) где ~,'е(и, о),",— 0 при ~ и — о,-~О.
Пример разделенной разности для градиента функции конечногб числа переменных, удовлетворяющей условиям (40), (41), был приведен в 4 5.8 14]. Предположим, что функция У(и) ен С'(В) такова, что разделенная разность У'(и, о) при всех и, о енВ существует и, кроме того, имеет обратный оператор (Г (и, о))-'. Тогда для минимизации функции l (и) на В можно предложить следующий двухшаговый итерационный процесс: й„=и„— Гмр(и,), и„„=да — Г,У'(ир), й=О, 1, ..., (42) где Г~=(Г(и„, их — 5„Г(и„)))-', ()ь — параметр метода, ()а~О. Предлагаем читателю самостоятельно сформулировать и доказать аналог теоремы 5.8.1 из 14! для случая, когда В= — Н вЂ” гильбертово пространство, и убедиться, что при достаточно хорошем выооре начального приближения иа для сильно выпуклых функций метод (42) имеет кубиче- скую скорость сходимости. 8.
Метод штрафных функций может быть применен для решения задачи У (и) -+.1п(; и ен У, (43) Сl=-(и~(У,: д;(и)(0, (=Ъ, т; д;(и)=0, 1=-т+1, з), (44) где Н,— заданное множество из банахова пространства В, функции у(и), д, (и), ..., д,(и) определены на (l,.
0 п р еде лен не 5. Последовательность функций (Рь(и), й=1, 2, ...), определенных и неотрицательных на множестве Н,, содержащем множество У, называют штрафом или штрафной функцией множества У на мно- жестве Ум если 0 при и ен У, 1пп Ра(и)= к- ( +ос при и Ио .13. Примером штрафной функции множества (44) на множе- стве Уа является функция Р, (и) = А„Р (и), и я Ум (45) ЗУ где Р(и) = ~ (шах(8~(и); 0))д+ ~Ч,' !д;(и) )д, ие:-Уд, (46) г и -~--1 числа Ад, называемые штрафными коэффициентами, таковы, что Ад)0, у=1, 2, ...; 1!ш Ад=+со, р=1; д сю другие примеры штрафных функций см.
в Ч 5.12 из 141. Функцию (46) также часто называют штрафной функцией множества (44), подразумевая при этом, что после умножения на штрафные коэффициенты она превращается в штрафную функцию в смысле определения 5. Метод штрафных функций для задачи (43), (44) заключается в том, что вводят функции Фд (и) = У(и)+Рд(и), и е= Уд, й= 1, 2,, (47) и определяют последовательность (ид) условиями ид е= Уд, Фд (ид) =.
Фд, + ед, (48) где Рд(и) — штрафная функция множества У (например, функция (45), (46)), Фд„=-!п1Ф, (и), ед)0, й=!, 2, ... ио ..., 1!гп ед= О. Если существует точка ид ен У„для которой Фд (ид) = Фд„, то в (48) допускается возможность ед = О. Заметим, что точка им удовлетворяющая условию (48), вообще говоря, не принадлежит множеству У. При описании метода штрафной функции (47), (48) подразумевается, что Ф,„) — оо при всех й=!, 2, ... Приведем две теоремы о сходимости метода штрафных функций. Теорема 7.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
