Ф.П. Васильев - Методы оптимизации (1125241), страница 91
Текст из файла (страница 91)
< < г г" 'г г" йе! хй ч~(Е/(2и))(2р/Е) (у ) =(2и/Е)у . Оценка (26) доказана. Из (26) следует г — ! '2 г 2 г 2и г' га-~ [Х вЂ” Х„! < ~„)Х вЂ” Х [ < ~' Куг'" < ~ +2 г < 2и Чг'(! гх) (27) х= й ж й т=й для всех р, й, р > й > О. Так квк 0 < у < 1, то правая часть (27) стремится к нулю при й -~ со, Это значит, что последовательность (хй) фундаментальна и сходится к некоторой точке х . В силу замкнутости множестве Х точка х„ е Х. Переходя к пределу при р -ч со, из 27) получим оценку (20). Остается убедиться в том, что х — точка минимума /(х) на Х. Так г как /(х) е С (Х), то при й — ~со иэ (23) имеем (/'(х„), х — х,) > 0 при всех х е Х, Учитывая выпуклость /(х), отсюда и иэ теоремы 4.2,3 заключаем, что х, — решение задачи (1).
Теорема 2 доказана. ь! Иэ (20) при й =О имеем [хэ — х„[<(2р/Е)г(1-у) !. Это неравенство означает, что метод (6) при Х р' Е", так гке как и метод (8), который получен из (6) при Х = Е", сходится, вообще говоря, лишь при выборе достаточно хорошего начального приближения. 4. Перейдем к рассмотрению метоэл (2)-(4) с выбором шага ай — — АЬ, где ' — минимальный номер, для которого выполняется неравенство (10) Этот ва иант метода Йьютона будем называть методом (2)-(4), (10). Покажем, что метод (2)-(4), (10) сходится при любом выборе начального приближения и этим выгодно отличается от метода 2) — (4), (5).
Те о р е и а 3. Пусть Х вЂ” замкнутое выпуклое множество из Е", /(х) е Сг(Х) и МЕ[' < (/л(*)66) < Ай[6[', *с Х, 6 6 Ех (28) эде Ех — подпростраяство, параллельное аффииной оболочке множества Х, а и, М— постоянные, 0 < р < йе. Тоеда последовательность (хй), определлемая методом (2)- (4), (ГО), пРи любом начальном пРиближении хо Е Х сУЩествУет и сходитсл к точке х,— решению вада и (1), Если, кроме тово, /л(х) удовлетворвет условию Лившица (18), то найдется номер й такой, что в (4) а, = 1 при всех й > йо и справедлива оценка [х, — х [< -~.
~: у'" ц -~у" (! — у")-', й > й,. (29) До к а э в т е л ь с т в о. Согласно теореме 4.3.4 функция /(х) сильно выпукла. Тогда из тео- ремы 4.3.1 следует существование и единственность точки хй, удовлетворяющей условиям (3). Согласно теореме 4.2.3 тогда (/й'(хй, х — хй) ) 0 или (/'(хй) +/е(х )(хй — хй), х — жй) >0 при всех хе Х. (30) Если оказалось, что ий —— жй, то из (30) имеем (/'(хй), х — х ) ) О, х Е Х. В силу теоремы 4.2,3 и выпуклости,/(х) отсюда следует жй = х = х, — задача (1) решена. Поэтому можем считать, что ий р' хй, Тогда /й(ий) < /й(хй) =О. Покажем, что тогда существует хотя бы один номер 4 ) О, для которого выполняется условие (10).
С этой целью возьмем произвольное число а, 0 < а < 1, и положим х = хй + о(хй — хй). Отсюда и из выпуклости /й(х) следует /,( .)< /,(яй)+(! — )/„( й)= /„(ий)<о. Тогда из формулы /(ж ) — /(хй) =/й(х ) + (аз/2)((/л(хй + да(хй — хй))— — /е(хй))(хй — хй), Ий — хй), 0 < и < 1, (31) с учетом условий (28) получим /( ) /( ) < / ( ) + ( г/2)(йг )[ - [г < <а/й(х )+(аг/2)М[хй хь[г 0<се<1 (32) 306 Гл. 5. МЕТОДЫ МИНИМИЗАь(ИИ ФУН!(ЦИЙ МНОГИХ ПЕРЕМЕННЫХ 9 10.
МЕТОД НЪЮТОНА Так как И вЂ” точка минимума сильно выпуклой функции /ь(х) на Х, то согласно теореме 4.3.1 ~'ь хь(~ <(2/р)!/ь( 'ь) /ь(хь)1=(2/Р)!/ь(*ьН. Подставив зту оценку в (32), получим /(х ) — /(х ) < -а(/ь(хь)(4 а (М/!з)(/ь(хь)( 0<а <1. (33) Возьмем произвольное а, удовлетворяющее условиям 0 < го —— Л (1 — з) и/М < а < (1 — з) и/М < 1.
(34) Отсюда и из предыдущего неравенства будем иметь /(хь) — /(ха + а(хь — хь)) > а(1 — а(М/р))//ь(хь)() за(/ь(яь)( (35) при всех а, удовлетворяющих условиям (34). Возьмем такой номер гл ) 1, для которого Л т < < (1 — з)р/М < Л'" '. Отсюда следует, что О < = Л(! — з)р/М < Л'" < (! — )р/М. (36) Таким образом, а = Л'" удовлетворяет условиям (34) и, следовательно, при а = Лт будет справедливо неравенство (35).
Эта значит, при 1 =аз выполняется условие(1о), Тогда найдется наименьший номер 4=(!, 0 < ы <т, удовлетворюощий неравенству (10). Приняв в (4) аь — — Лч, получим следующее приближение хь е !. Тем самым показано, что последовательность (хь) из метода (2)-(4), (10) при любом начальном приближении существует. Из (10) при т = ы имеем /(хь) — /(хь „,) > заь(/ь(хь)(, й = О, 1,... т. е. /( ) /(х ) ) !/ (хь))а(1 — а(ь/р)(я — хь() > аз(/ь(6ь)( при всех а, 0 < и < 1, й > йа, В частности, при а = 1 отсюда занлючаем, что условие (10) выполнено при з =(!=О, и, следовательно, аь = Л = 1, хье! — — я„при квжд ким образоьь начиная с номера й = йо, метод (2)-(4), (1О) превращается в метод (2)-(5) с начальным приближением хгь, удовлетворяющим условию ч =(Ь/(2р))!хь ! — х (=(Е/(2р)))жз, — хь ! <(1 — з)/2 <1.
Отсюда и иэ теоремы 2 следует оценка (29), что и требовалось. П Учитывая, что согласна (36) аь — — Лй > Л'" > зо, ото~ода получим /(хь) — /(хь !) ) езо(/ь(хь)(, й =О, 1,... (37) Таким образом, /(х„) > /(хье!) > /, й = 0,1,, Тогда существует Иш /(хь) ) /, и Ига (/(хь) — /(хь „!)) = 0 Из (37) теперь имеем Иш /(Вь) = О, а из (33) следует Ь ьь 1пп (ха — хь(= О. (38) далее заметим, что согласно (37) последовательность (хь) бМ(ха) =(х: хе Х, /(х) </(ха)). Для сильно выпуклых непрерывных функций множество М(ха) выпукло, замкнуто и ограничена. Тогда последовательность (хь) имеет хата бы одну предельную точку. Пусть а, — произвольная предельная точка (хь ) и пусть (х„ ) -е а,, С учетом (38) и условия /(х) ц Сз(Х) иэ (30) при й = й -есо получим (/'(а ), х — а,) >0 для всех ха Х.
Согласно теореме 4.2.3 то. гда а„= х, — точка минимума /(х) на Х. Следовательно, Иш /(х„)= Иш /(хь )=/(х„)=/„ т. е. (хь) — минимизирующая последовательность. Отсюда и из теоремы 4.3.1 следует (х„) -е -е х,. Пусть теперь выполнено условие (18).
В силу (38) существует номер йа такой, что (Ь/р)(хь — хь) < 1 — е при всех й ) йа. Из (31) с учетом условия (18) и оценки (33) тогда имеем /( ) </ ( )+( 3/2)Е~- ~з < ~/ (- )~+ з(г/ )(/ ( — )((- Таким образом, метод (2)-(4), (10) ненамного сложнее метода (2)-(5), (10), по скорости сходимости не уступает ему и в то же время не сталь чувствителен к выбору начального приближения, как метод (2)-(5).
При наличии эффективных методов минимизации квадратичной функции /ь(х) на множестве Х метод (2)-(4), (10) можно с успехом применять для минимизации достаточно гладких функций. Другие теоремы о сходимости описанных выше вариантов метода Ньютона читатель может найти в (603(. 5. Существуют н другие модификации метода Ньютона, широко используемые в вычислительной практике. Так, например, в случае Х =Е" вместо (8) часто применяют метод Ньютона с переменным шагом: хь, ! — — х, — а„(/л(х„))-'/'(хь), й = О, 1 (39) Параметр иь > 0 в (39) выбирается из тех же соображений, что и в основном варианте метода Ньютона.
Заметим, что приближение ха е, в (39) мажет быть получена, как решение задачи минимизации: х а Ь'" (40) /ь(х '*)ж '"(/'(хь) - хь) + 2(/з(х И - хь) х - хь) при а = аь. Задача (40) подсказывает, как обобщить метод (39) на случай Х ~ Е" — тогда приближение хь е г следует определять как решение задачи: /ь(х, а) е !и!1 х ц Х при а = аь, или как решение вариационного неравенства (41) (/л(хь)(хь „! — хь) -1- аь/г(ха), х — хь „!) > 0 Чх ц Х. (42) Практика показывает, что, умело выбирая параметр а„в (39)-(42), можно сделать эти методы менее чувствительными к выбору начальнога приближения ха. Еще раз подчеркнем, что все выше перечисленные варианты метода Ньютона могут быть эффективна использованы лишь тогда, когда матрица вторых производных /л(хь) легко вычисляется и все последующие вспомогательные задачи решаются достаточно просто.
Желание преодолеть возникающие здесь трудности привело к появлению так называемых кзазиньютонозских методов хь ! —— хь — аьЛ /'(хь), аь >О, й=0,1,..., (43) предназначенных для решения задачи (1) при Х = Ь"". В (43) матрица Аь выбирается иа условия Иш ~( ! (/е( ))-!(~ 0 Оказывается, при таком выборе Аь метод (44) также сохраняет высокую скорость схадимости, присущую методу Ньютона. Другое достоинство методов (43) — существуют конструктивные способы построения матриц Аь со свойством (44) на основе достаточно простых рекуррентных соотношений, использ)~ющих информацию с предыдущей итерации, обходясь без вычисления и обращения матрицы /'(х).
Примером квазиньютоновского метода является метод Дазидона — Флетчера — Пауэлла, в ко~ором матрицы Аь определяются соотношениями -и ььаь|с й=ь,1 ..: р =р т т (45) где Чь =/ (лье !) — / (х„), ть = лье ! — хха а величина сг„находится нз условия ! г яь(аь) = ш!и яь(а) яь(а) =/(хь — аА /'(х„)) ало (46) а( Отметим, что векторы рь — — Аь/'(хь) удовлетворяют равенствам (9.29), так что метод (39), (45), (46) одновременно является методом сопряженных направлений. С квазиньютоновскими методами читатель моэкет подробнее познакомиться в (76; 222; 586; 603; 721; 738; 759; 769). Непрерывные варианты метода Ньютона и его обобщений рассмвтри- ':4,"::. за~ется в следующем параграфе 308 Гл.
5. МЕТОДЫ МИНИМИЗАНИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ 6 11. НЕПРЕРЫВНЫЕ МЕТОДЫ С ПЕРЕМЕННОЙ МЕТРИКОЙ 309 9 11. Непрерывные методы с переменной метрикой Рассмотрим задачу минимизации 7(х) и !и[, х Е Х, (1) где Х вЂ” выпуклое замкнутое множество, функция 7"(х) дифференцируема на Х, Пусть при каждом х е Е" определена квадратная матрица С(х) п-го порядка, симметричная, положительно определенная. Всякая такая матрица С(х) в Е" задает новое скалярное произведение (у, я) = (С(х)у, к) тп гг', у ху г у<у! =ч<о<чуу~"" Р л Р менную (зависящую от х) метрику р(У, я)= !Су я!о = (С(хНУ я) У вЂ” х) которую мы кратко будем называть С-метрикой.
Оп р еде ле ни е 1. Точку юе Х будем называть С-проекцией точки я е Е", если !ю — к!о = 1и[ !У вЂ” я[о. эе х и будем обозначать через ю ='Ряс<*1(х). Иначе, С-проекция точки к является решением задачи минимизации Р(у)=-,(С(х)Ь вЂ” ) у — к) !и[, уеХ (2) Так как срл(у) = С(х) > О, то функция Чэ(у) сильно выпукла на Е" и на выпуклом замкнутом множестве Х достигает своей нижней грани, притом в единственной точке ю (теорема 4.3.1). Как вытекает из (2) и теоремы 4.2.3 точка ю будет С-проекцией точки к е Е" тогда и только тогда, когда (уз'(ю), у — ю) = (С(х)(ю — г), у — ю) ~> 0 <Уу е Х.
(3) Если С(х) = Մ— единичная матрица, то С-проекция превращается в обычную проекцию точки на множество (см. $4.4). По аналогии с теоремой 4.4.4 с помощью С-проекции можно сформулировать критерий оптимальности для выпуклых задач (1), Справедлива Теорема 1. Пуста Х вЂ” выпуклое замкнутое множество, Х,— множество точек минимума функции 7(х) на Х.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
