Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 67
Текст из файла (страница 67)
Доказательство. Из неравенства (2.3.7) при о=и„, и= и»+, имеем У(и») — 7(и»»,) > <У'(и»), и„— и„.,> — (Ы2)!и» вЂ” и»+»Р, й О, 1, ... (9) Из (2) и теоремы 4.4.1 следует, что <и»+» — !и» вЂ” а»Х'(и»)), и — и„+,>>О Ри~У. Перепишем это неравенство в виде <1'(и»), и — и„,,> > <и„— и»+„и — и»,,>/а„7с= О, 1, ... (10) Еяе методы минимизАции ФУНКЦИЙ МНОГИХ ПЕРЕМЕНныХ 1гл. $ Отсгода при и и, с учетом условия (4) получим <П(ие), и, — и»+,> > !и, — иеы!'/аь >(Ы2+ е) !и„— и+,!'.
Подставим эту оценку в (9): г( ) — г( + ) е!и — и+!*, й= О, 1, ... (11) Так как л (иь) ) г е ) — со и последовательность У(и„) ) — убы- вающая, то существует конечный предел Иш л(иь))л и, слез в довательно, 1па (л (иь) — л (из+,)) = О. Отсюда и из (11) сразу получим 1ш1 !ид — иь+г! = О. ь»о Пусть теперь множество М(и,) ограничено. Так как согласно (11) 1(и,+») ( У(и„) <... < г (и,), то (и,) ~ М(и,).
По теореме Больцано — Вейерштрасса ограниченная последовательность (и„) имеет хотя бы одну предельную точку. Пусть ив — произвольная предельная точка (и„) и (иь )-»-и„. По доказанномуИш!иьег— ь-» — и„! =О, поэтому (иь +,)-+.и . Переходя в (10) к пределу при й=у -, с учетом условий (4) и непрерывности П(и) полу- чим (Г (и„), и — ие) )~0 при любом и я П, т. е. ие ед„.
По лем- ме 2.1.2 расстояние р (и, Яе) непрерывно по и, поэтому 1пп р(иь, Я„) = р(ие, Я„) = О. Отсюда следует, что (р(ию Яе)) »»» имеет единственную предельную точку, равную нулю, т. е. Иш р(ию Яе) = О. Теорема 1 доказана, Теорема 2. Пусть выполнены есе условия теоремы 1 и, кроме того, функция г(и) выпукла на К Тогда для последова- тельности (и„) иг (2), (4) имеем Ишу(ид) = гю Иш о(ию С„) = О, (12) причем справедлива оценка 0<7(иь) — У,„(С,й ', С, = совет)0, й= 1, 2, ... (13) Д о к а з а т е л ь с т в о.
Из ограниченности М(и,), непрерывности У(и) согласно теореме 2.1.2 следует ле) — оо, Пе=(и: иее ~ г», г (и) = ле) чь О, П„с: М(иг). Возьмем произвольную точку и е:— П . Из неравенства (4.2.4) тогда имеем 0(а„=,7(иь) — л'(ие)((Х'(иь), иь — изг = = (,Г (из), иь — из+,) — (л" (из), ие — иь+г), й=0,1,. ° . МЕТОД ПРОЕКЦИИ ГРАДИЕНТА 281 Пользуясь неравенством (10) при и=из и условием (4) выбора аь отсюда получим О ( ад « . (Г (ид), ид — ид+ь) — (ид — ид+„и„— ад+ ьььад ( ()ид — ид+ь)( зир )Г(и))+ Р)г 'ь= С„)ид — ид+ь), й=0,1, ... )М(вд) (14) Здесь мы учли ограниченность множества М(и,), позтому .Р= зир )и — о)(оси, кроъье того, У (и) ! < У'(и) — У'(и,))+ ч дам(чд) + У'(и,) ! <7.)и — и,)+ У'(и,) ! <И+ У'(и,) ! при любом иж ьиМ(и,), так что еир ! Х'(и) !( со.
Из (11), (14) следует М(ид) ад — ад+,' в еС, 'а'„= Аад (й = О, 1, ...). Отсюда с помощью лем- мы 2.3.4 придем к оценке (13), из которой также следует пер- вое из равенств (12). Второе равенство (12) является следствием теоремы 2.1.2. Рассмотрим случай сильно выпуклой функции, предполагая, что в методе (2) величина а„выбирается постоянной.
Т е о р е м а 3. Пусть ьь — выпуклое замкнутое множество, уьункция У(и)жС' '(П) и сильно выпукла на П. Пусть 0<а< < 2)ьЛ ', где постоянные )ь, Ь, )ь< Ь, взяты из (2.3.6), (4.3.8). Тогда последовательность (и,), получаемая из (2) при а„= а (й =О, 1, ...), сходится к точке минимума и„, причем справед- лива оценка )ид — и )(! и„— и„,, )(д(а))~, й = О, 1, ..., (15) где д (а) = (1 — 2)да+ аП) 'и, О < д (а) < 1. Д о к а з а т е л ь с т в о. Введем отображение Аи =Ус(и — ау'(и) ), действующее из П в П. Покажем его сжимаемость при 0< а< < 2)ьС '. С помощью теоремы 4.4.2 имеем )Аи Ао! )Уо (и ау (и) ) Уо (о аь (о) ) ! < )и — аг'(и) — и+ау'(о) !' )и — РР+аь)Г(и) — у'(и) !'— — 2а<у'(и) — П(о), и — о> < )и — и!'(1+ а'Рь — 2)ьа) = д'(а) )и — и!', т.
е )Аи — Ао! < ь)(а))и — и), и, оьи П. (16) Так как 0< а< 2)ьЬ ', то 0< д(а)< 1. Это значит, что отображение А — сжимающее. Заметим также, что замкнутое множество ПжЕ" представляет собой полное метрическое пространство с метрикой р(и, и)= )и — и!. Следовательно, можно пользоваться принципом сжимающих отображений [179!. Метод (2) при а„=а, записанный в виде иды —— Аи„представляет собой 282 мктоды минимизации югнкцин многих пкгвмкнных (гл, з известный процесс поиска неподвижной точки и„сжимающего отображения А, т. е.
точки и„, для которой ие = Аие. Известно (179), что такая точка ие существует, единственна и Иш(пав алы — и. ) = О. Из (16) следует, что (иа — и„(~ ((д(а)) (ио — иы-а ! 'Зсти~)/с. Отсюда прн т- получим оценку (15). Так как ие= Уп(ие— — ау'(ие)), то нз теоремы 4.4.3 следует, что и„— точка минимума функции Х(и) на множестве (/. Теорема 3 доказана. Заметим, что наименьшее значение 9(тх) из (15) при 0(а < < 2)ьг' ' достигается при сс = )ьг. з и равно г/(сз ) = (1— — (М)')"' 3. Следуя (29), рассмотрим сходнмость метода (2), (4), не требуя, в етлнчне от теоремы 1, 2, отравнченностн множества М(иг).
Кроме того, будем считать, что вычисление граднента функцвв в проектпрозанне на множество на каждой итерации проводятся с погрешностями. Т е о р е м а 4. Пусть С вЂ” выиуклое замкнутое множество из Е", функция г(и) выпукла на С, Х(и) с=С''(С), ге.л — оо, Се тьо. Пусть вместо точного значения градиента П(и) и проекции Уо(и) ив У(и) известны Р их приближения г"а (и) и соответственно Уь(и) с погрешностью ~У'(и) — У,(и)~<ба, игнС; (У(и) — Уа(и)/<Саба, ы (17) и тн Е", Се = сопят ) О, б„ > О, й = О, 1, ...; ~~~~~ ба = б < О. а-о наконец, пусть последовательность (иь) определяется условиями иа+г = Уа(иа — Яад~ (иа)), и ш С, й = О, 1, ..., (18) еде иь выбирается так: 0< е,(иь(2(1 — з)/Б, й=О, 1, ..., 0<с< 1.
(19) Тогда (иг) сходится к некоторой точке ое Ш Сю Доказательство. Наряду с (иь) введем вспомогательную последовательность (оь), определяемую следующим образом: оь = У(иг — агХ'(иь)), й = О, 1, ...; ог = ио. (20) Отсюда н вз (18) с помощью теоремы 4.4.2 н условий (17) получаем ) иа+д — оа) (~ У,(и„— над (и„)) — У (и,— ссаг, (и,)) ~+ + ! У(иа сна,/~ (и~ )) У (иа — ссг у (иа))~( Саба + иа ~ /а(и~ ) / (иу )) ~ (С ба+(2(1 — з)/6) ба —— С ба, й=О, 1, ... (21) Возьмем пронзвольпую точку и„гн С . Согласно теореме 4.2.3 тогда (У' (ие), и — ие)) )О, и ш С.
(22) На (20) в неравенства (4.43) получаем (23) с'оа — иа + ссаг" (иа), и — о,) )~ 0 )/и ги (/. йг) МЕТОД ПРОЕКЦИИ ГРАДИЕНТА 283 Положим в (23) и= и», а (22) умножим на сдд) 0 п прпмом и = оь Сложим получившиеся неравенства (оа — и,, и» вЂ” оа) + иа (Р (и,) — .Г (и»), и — оа) Ъ О, (24) й =О, 1, ... Преобразуем каждое слагаемое в правой части (24). Прежде всего имеем 2(о„— и„, и» вЂ” оа) =( и„— и» (з — ( иа — и,(з — ! о„— и»(з. (25) Далее, воспользуеыся неравенством (4.2.20) при и = ид, о = и», м = = ом получим (у'(иь) — з'(и ), и — иа) <(б)4) ) иа — оа )з, й = О, 1, ...
(26) Подставив (25), (26) в (24), получим ( иа — и» '(» — ( и~ — и» (з — (1 — иаЬ/2) ( иа — оа (~ > О. Отсюда, учитывая условие (19), имеем (иа — и»)з в(оа — и (з+з)иь — оа(з, й=0,1, ... (27) Далее, воспольауемся леммой 2.3ЛО при зд = ид, з» = и», иь = од; из (17), (21), (27) получим 1(ш (иа — и»( 11ш (оа — и») < оо, (28) а а э 11ш(о~ иа(=0 з»» ) иь — и»(з) )( иа+ — и»)а+ е( ив — иа+д(з, й = О, 1, ..., Уи» ди У». Польауясь произволом в выборе и» ев У», отсюда получаем )иа — и»())иа+д — о ), р(и„У)Ър(иа+д, П»), й=О, 1, ..., причем равенство здесь возможно лишь при ид+, = им что в силу теоремы 4.4,3 означает из ш У».
Таким образом, при точной реализации метода (17) — (19) расстояние от точки иь до множества У или до точки о» монотонно убывает. Как мы видели, таким же свойством обладает градиентный метод (1.3), (1.21), (1.22). 4. Опирансь на неравенства, полученные при докааательстве теоремы 4, можно оценить скорость сходимости метода (2), (4) для сильно выпуклых функций, причем, в отличие от теоремы 3, новая оценка оказывается неулучшаемой на классе сильно выпуклых функций, принадлежащих бч '(У). Отсюда следует, что последовательность (ид) ограничена.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
