Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 68
Текст из файла (страница 68)
Тогда существует хотя бы одна предельная точка о атой последовательности и подпоследовательность [и» В сходящаяся к о . Из (28) имеем 11ш оа — — и». «т~' в Согласно (23) с учетом (19) получаем (у'(иь), и — од,) > — (иа — иа, и — и,) и ~) — ( иа — иь ((и — ов(е, д. Отстода при й = й -» оо будем иметь (У'(о»), и — и») ~)0 при всех и ш бд, По теореме 4.2.3 тогдаи шП . Вспомним, что неравенство (27) было получено для любой точки и» ш У .
В частности, (27) верно и для и» = о». Но и» вЂ” предельная точка последовательности (ид). Из леммы 2.3ЛО тогда следует, что (ид) сходится к о». Теорема 4 доказана. Замечание 1. Если в (17) 6»=0 (й =О, 1, ...), то из (18) — (20) следует, что и»+1 са (й=О, 1, ...). Тогда из (27) имеем 284 вгетодьг минимиЗАЦИИ ФУНКЦНН МНОГИХ ПЕРЕМЕННЫХ ]ГЛ. 6 Т е о р е м а 5. Пусть (« — выпуклое замкнутое мновсвство ив Нь, о функция г (и) сильно выпукла на (7 и принадлггкит бч с(П], Пусть после- довательность (и») построено методом (2) при а» = а (й = О, 1, ..., О ( < а < 2/ь), Тогда 1и» ™в(((У(а))~]ие — ив(, й=0,1, ..., (29) гдв ~1 — рсс, Ыя — 1, 0 < сс < 2 (Ь -]- р) — » 2(Ь+ Р)»(я< 27.
г, Ч(~) ( 1, постоЯнные и, Ь гонты иг (2 3 б), (438), а и мула г(и) на К Наименьшее значение д(а) при 0 < а < 2Л с достигагтг«» при я = я„= 2 (Ь+ р)» и равно д (яв] = (Ь вЂ” р) (Ь+ р) Доказательство. Из теоремы 4.3.1 следует, что ль.м — со, (Г состоит из единственной точки ив. Тогда из теоремы 4 имеем 11ш ) и — и„')~ ».ь ю« «=О. Здесь мы предполагаем, что в (17) б» 0 (й = О, 1, ...), поэтому из (18), (20), (21) следует о» = и»ы (й = О, 1, ...). Учитывая последнее равенство н условие а» = а, подставим (25) в (24). Получим ) и„— иь ]з < (и,— ив (з — ( и,+ — и ]в+ 2сс (л«(и») — л«(и ), иь — и + ) = ) и, — ив ! — ~ и» вЂ” и» вЂ” я (л «(и») — л«(и )) ]в+ +а )л'(и ) — л'(ив)(з — 2Я(У'(и») — л'(иь), и„— ив), й=0,1..., (зо) Рассмотрим два случая: 1] если 0 < а < 2(б + )с]-' < р-', то иа (33) и левого неравенства (32) имеем( и„+» — и (т( ( и„— ив ]г(Я (Я вЂ” 2 (Ь+ 9)») 1»з+1 — 2ссЬР(Ь+Р]») ° = (1 — яр) ! и — ив]в; 2] если Ь «< 2(Х,+ р)-' < а < 2Л-', то из (33) и правого неравенства (32) полУчим ) и„+д — и ]~(]и» вЂ” ив]~(Я(а — 2(Л+ Р)») Ь + + 1 — 2абр (Ь+ р] г) = (Ья — 1) ( и„— ив ]з.
Объединяя оба случаи, име. ем ( и»+» — иь (< у(а) ( и» вЂ” иь ! (й = О, '1, ...), откуда следует оценив (29). Из графика функции д(а) (рис. 5.5) видно, что фуннция д(а) достигает минимума при 0 ( а < 2Л ' в точке аь = 2(Ь+ р)», причем у (яь) = (б — р) (Ь+ р). Теорема 5 доказана. Вспомним неравенства (4.ЗЛ7), (4.338), из которых имеем ~ л' (и,) — л'(иь) ) + Лр ~ и, — ив (з( ~((Ь+ Р) (о"'(и») — У'(иь), и» вЂ” ив), й = О, 1, ..., (31) Р!и» вЂ” ив]~() л" (и») — л'(ив)](Л!и» вЂ” ив(, й=О, 1, ... (32) Из (30), (31) следует )и, д — и (з( ! и,— ив]в+ ссз / л'(и») — у'(и„) ]з— — 2Я (Ь+ Р)» ) ло (и») — л" (ив) ]з — 2абР (Ь+ Р)» ~ и — и (з =а (я — 2(б-)- р) г] /л'(и») — л«(и ) )з+ + [1 — 2ссбР(Ь+ Р) г) ~ и» вЂ” ив ]г, » = О, 1, ...
(33) Ь1ЕТОД ПРОЕКЦИИ СУБГРАДИЕПТА у 3) Приведем пример, показывающий, что оценка (29) неулучшаема на классе сильно выпуклых функций иа С' '(У). Пример 1. Пусть и= (х, у) шУ=Ет, 7(и) = (Ехз+руз)/2 (0< < р < Е), Ясно, что зто функция сильно выпукла с константой к = р/2, принадлежит С' '(Е') с константой Е и достигает минимума на Ет в точке иа = (О, 0). Процесс (2) при аь = а (О < а < 25-') имеет вид хьы = хь — абхь = (1 — аб) хь, увы = уь — адуь = (1 — ар) ум 5=0, 1, ...
Положим здесь а = 2(5+0) ', 7 = =(Š— р)(5+у) . Тогда ХМ.1= — УХЕ Уз+1 = Ууь Следовательно ( иа+т — и = — 6 1+с — иа(= у) иа(б уь+т) и ), т, е, оценка (29) неулучшаема. Заметим, что ес- Рпс. 5.5 ли в теоремах 1 — 5 У = Е", то мы получим сходимость соответствующих вариантов градиентного метода (1.3). Упражнения. 1. Вычислить несколько итераций метода проекции градиента при различных способах выбора аь в (2) для фушсции 1(и) = (х — 1)т+ (у+ 1)з, и ш У = Ет+ — — (и = (х, у) ел Е; х ) О, у )~ 01. Рассмотреть начальные приближения из = (О, 0), ио = (О, 1), ио = (1, 0), из = (1, 1). 2.
Описать одну итерацию метода проекции градиента для функции (1.5), считая, что множество У представляет собой шар, гиперплоскость, параллелепипед, полупространство или положительный октант (см. примеры 4.4Л вЂ” 4.4.6). Исследовать сходимость метода. 3. Рассмотреть метод проекции градиента для функции У(и) = = ~Аи — Ь|', где А — матрица порядка т Х и, Ь ш Е, считая, что множество У имеет впд, описанный в примерах 4.4Л вЂ” 4.4.6. Исследовать сходвмость.
9 3. Метод проекции субгрлдиеитн 1. В рассмотренных выше градиентном методе и методе проекции градиента требовалась дифференцнруемость минимлзпруемой функции. Однако для выпуклых функций указанные методы более естественно описать на языке субграднентов (см. 4 4.6). А именно, пусть У вЂ” выпуклое замкнутое множество из Е", функция 1(и) выпукла на У п ее субдяфференцнал УУ(и) непуст при всех и ш У. Тогда для приближенного решения задачи У(и) -ьш1; и ш У, (1) можно предложить следующий итерационный метод: иьн = .'Хи(иь — азсь), аь ) О, сь ш ду(иь), й = О, 1,, (2) где и, — некоторая точка нз У, а субграднент сь выбирается из ду(иь) провзвольным образом. Если прп некотором й окажется, что ивы = им то про« песе (2) прекращается, так как в етом случае иь — решение аадачи (1). В самом доле, при иь = Уо(иь — аьсь) согласно теореме 4.4.1 <иь — (иь— — аьсь), и — иь) = (см и — иг)аь) 0 или (см и — иь) ) О при всех и ен У.
Отсюда из теоремы 4.6.4 следует, что иа ш У„. 286 МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ (ГЛ. з В том случае, когда функция 1(и) дифференцируема во всех точках и ел У, метод (2) превращается в метод проекции градиента, а при у = = Š— в градиентный метод. При выборе длины шага и, в (2) можно руководствоваться теми же соображениями, которые были описаны выше в 1 1, 2, Мы здесь ограничимся рассмотрением случая, когда ив в (2) выбирается из условий ив)О, у=о, 1, ...; ~Р сг„=, Х ит< (3) а=о в=о Как уже отмечалось в $1, в качестве ив можно взять ив = С()с+ 1) ", где С = совы ) О, 1/2 < и < 1; напрнвгер, ав = ()г+ 1) ' (7г = О, 1, ...).
Метод (2), (3) не гарантирует выполнения усаовия монотонности 1(ив) ) 1(ивьг) на каждой итерации и сходится, вообще говоря, медленно, во если проекция точки на множество У и субградиент св гн д1(ив) находятся несложно, то атот метод очень прост для реализации на ЭВ51. Докажем его сходимость.
Теорема 1. Пусть У вЂ” выпуклое сомкнутое множество иг Е", угунк ция 1(и) определена и выпукла на некотором открытом выпуклом множестве Ит, содержащем У (например, Ит Е"). Пусть 1» ) — со, множество Уь точек минимума 1(и) на У непусто и ограничено, и пусть, кроме того, аир епр ) с) = А<оо. (4) и=нежат(и) Тогда последовательность (ив), определяемая условиями (2), (3), такова, что 1(ш 1 (и„) = 1, Пш р (и„, Уе) = О.
(5) В гь В сь Доказательство. При сделанных предположениях функция 1(и) непрерывна на У, субдпфференциалы д1(и) непусты, выпуклы, завшнуты и ограничены при всех и гн У (см. теоремы 4.2.15, 4.6.1, 4.6.2]. Из ограниченности множества Уе и теоремы 4.2.17 следует что множество М(С) = = (и ш У: 1(и) < С) ограничено при любом С) 1».
Множество У выпукло и замкнуто в силу теореыы 4.2Л и леммы 2.1Л. Согласно определению 4.4.1 проекции точки на множество и теореме 4.4.2 имеем р (иа+ Уе)=! а+ УУ (ив+) <!иа+ УУ ( В)! = = ) У (и — плс„) — У (У (и )) )~ < ( и, — авсв — УУ (и„) )~ = рз(и„, У ) + аз ) с )з — 2ав (с, ив — УУ (ив)) или 2а (с, и — У г (и )) < ит) св')з+ р (ив, Уе) — р (ив+в, Уе), й = О, 1, ...
(6) Суммируя неравенства (6) по )с от О до некоторого т ) 1, с учетом условий (3), (4) получим гя г» ~~~~ 2ив(св, иа — УП (ил)) ~ (А ~ иг',+ р (иа, Уг) — р (им+в, Уе) ~ а=е в е ° ь ~А' ,"~', и'„+р'(и,, У,) =Е<, ы=1,2„.. (7) а=о Ь1ЕТОД ПРОЕКЦИИ ОУБГРАДИЕНТА 9 3! Далее, по определению субградиепта имеем О ~~ У (ий) — с'а = .»' (ий) — » (Уп (ий)) ( (с„, и — Уп (и„)), /с = О, 1,... (8) Нз (7), (8) следует, что числовой ряд сс, (с, и,— У (и,)) й=о с неотрицательными членами сходится. Но согласно (3) ~к~~ ай — — со.
Пой=о этому сходимость предыдущего ряда возможна лишь при 1цн (с, и„— в-»с» — У (и„)) = О. Это значит, что существу!от номера й, ( йс ( ., „( й ( ( ... такие, что 11пз (с„, ий — Уп (и )) =О, »п»»»»и йп» (9) Тогда из (8) при й= й -»-оо получим 11ш э'(ий 1» уюКроме того, из с»-» с ( о») (8), (9) следует, что с'(ий )~(Ха+акр(сй, ий — Уп (ий )) =С(оо» т. е. (ий ) сиМ(С). Но М(С) ограничено, а [ий ) — минимиаирующая последовательность, поэтому из теоремы 2.1.2 имеем 1!ш р(ий, Сс) =О.
о»-»сс Тем самым показано, что для подпоследовательности (и '), удовлетворяющей условию (9), справедливы равенства (5). Опираясь на это, покажем, что равенства (5) имеют место для всей последовательности (ий). Нэ (3), (4), (6), (8) получаем, что рз(и,+м П )(р (и„С„)+ай)сй(2(р (ий, Сс)+айзА2» !с=О, 1, ... Это значит, что числовая последовательность ай — — р (ий, Сс) (й = О, 1, ...) удовлетворяет условиям леммы 2.3.2, из которой следует существование предела 1!пг р (и„, С ).
Так как подпоследовательность (р (ий, Са)~ 2 1 2 ° й-» з»' сходится к нулю, то этот предел может равняться лишь нулю. Следовательно, 1!ш р(и„Са) =О. Покажем, что тогда 1пп э'(ий) =се. По услой» й--а впю множество Па ограничено. Тогда последовательность (ий), сходящаяся к С„, также ограничена. Возьмем любую предельную точку ис этой последовательности. Пусть (ий ! -ь иа. Так как С вЂ” замкнутое множество и йс) 1!ш р (ий, 0,„1 = р(и, П ] = О, то иа сн С . А тогда 1!ш Х(ий ) = с (и)=* с с (»' / с=эс.
Это означает, что числовая последовательность (с(ий)) имеет единственную предельную точку, равную хс, т. е. 1!пг э'(ий) =э" . теорема 1 й» доказана. Э а м е ч а п и е 1. В условии теоремы 1 предполагается выполнение условия (4). В том случае, когда С ограничено, то, как следует из теоремы 4.6.5, условие (4) всегда выполняется. Заметим также, что в теореме 1 вместо (4) можно потребовать сходимостьрлда ~ аз (сй)2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
