Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 91
Текст из файла (страница 91)
Пусть 4бз 2~ б~ 2 +2!х! — 46, !х!> б, где х е Е', а б — сколь угодно малое фиксированное положительное число, 0 < б < 1. Нетрудно видеть, что /(х) е С'(Е') и, кроме того, /"(х) > 1 при всех х е Е', так что /(х) сильно выпукла на Е'. Далее, ясно, что /, =О, х, = О. В качестве начального приближения возьмем х = б. Из (8) получим последовательность х„=( — 1)ь 2, й =1,2,..., которая расходится, хотя начальное приближенйе хо отличается от х. =0 на малое число б. $10.
МЕТОД НЬЮТОНА 308 304 Гл. 5. МЕТОДЪ| МИНИМИЗАЦИИ ФУНКЦИИ МНОГИХ ПЕРЕМЕННЫХ Метод (8) часто применяют на завершающем этапе поиска минимума, когда с помощью более грубых, менее трудоемких методов уже найдена некоторая точка, достаточно близкая к точке минимума. 3. Исследуем сходимость метода (2)-(5) без предположения, что Х = Е". Теорема 2. Пусть Х вЂ” выпуклое замкнутоемножество изЕ", функция /(х) сильно выпукла и принадлежит классу Сз(Х) и !/ (х) / (уИ< о]х — у], ж,уЕХ, Е =сапы, (18) Тогда последовательность (хй) однозначно определяется условиями (6), при любом еыборе начального приближения жо.
Если (! 9) 2=(Е/(2р))!х! — о! <1 то последовательность (хй), определяемая условиями (6), сходится к точке х, — реше нию задачи (1), причем спраеедлиеа оценка <Рйд2<~~дз(142)рйо т=й (20) здесь р > 0 — постоянная из теоремы 4.3.4. Доказательство. В силу теоремы 4.3.1 функция /(х) ограничена снизу и достигает своей нижней грани на Х в единственной точке х,. Из теоремы 4.3.4 следует (/ (х)с,с)>р]с]2, хеХ, с еь», (21) где Е» — подпространство, параллельное аффинной оболочке множества Х.
Так как /, ь(ж) = = /" (х ), то из предыдущего неравенства и теоремы 4.3.4 вытекает сильная выпуклость функции /й(х) на мномгестве Х при всех й =О, 1,... Снова обращаясь к теореме 4.3,1, заключаем, что условия (6) однозначно определяют точку хй+ !. Таким образом, существование последовательности (хй) иэ (6) доказано.
Применив теорему 4,2.3 к функции /й(х) на Х, получим (/й'(жй „!), х — жй „!) > О, х е Х й = О, 1,... (22) Так как Уй'(х) ю /'(хй) + /е(хй)(ж — жй), то неравенство (22) перепишется в виде (/'(хй)-1-/г(хй)(хй „! — хй), х — хй !) >О, хЕХ, й =О, 1,... (23) Может случиться, что хй „! — — хй. Тогда на (23) имеем (/'(хй), ж — хй) > 0 при всех х е Х Согласно теореме 4.2.3 в этом случае жй — — х, — задача (1) решена.
Поэтому можем считать что хй т' хй „! при всех й = О, 1,... Положим в (23) х = жй. Получим (/ (хй)+ /г(х,)(х„„! — ж„), ж, — х„!) > О. (/й !'(хй), жй — хй „р) < О, й = 1, 2,... Отсюда, из формулы (2.6.5) и условия (18) следует (/'(хй),хй — хй „!) «(/'(хй) — /й !'(жй),жй — хй+!)= = (/ ( й) — / ( й — !) — / (хй — !)(*.й хй — !) хй хй ь !) = ! =(][/рр(хй !+ 2(ж, — хй !)) — /е(жй !)]йг(хй — хй !) жй — хй „!) < Е 2 < 2 ] й й - р] ] й й + р] Отсюда и иэ (2!) имеем р]хай!-хй] <(/ (хй)(хйьр-хр),хат!-хй)«((/(хр),хй-жр,„,), !с=0,1,... (24) Оценим правую часть (24) сверху.
Для этого в (22) заменим й на й — !. Получим (/й рР(хй), х— хй) В >О, ж е Х. Полагза здесь х = хй ь р, имеем Подставив полученную оценку в (24), имеем ]хй+ ! хй] «((Е/(2р))]хй — жй р]2 й = 1 2 Докажем оценку (25) Тогда из формулы /(х ) — /(хй) =/й(х )+(а2/2)((/е(хй Е да(яй — хй))— /г(' й))(*й 'й) й хй) 0(а<1, (31) с учетом условий (28) получим /( ' ) /(хй) (/й( ) + (а~/2)(М р)]хй — хй] < < и/ (хй) Ч- (аа/2)М]х — ж,]2, О < а < 1, (32) ]х, — ж„]<(2р/Е)Ч2', й=.о, 1, (26) При й = 0 эта оценка следует из условия (19). Сделаем индуктивное предположение: пусть рхй — хй р] < (2р/о)д~ при некотором й > 1.
Отсюда и иэ (25) имеем ]х — х ) < 2 2'-' 2 хйь! хй ((ь/(2р))(2р/Е) (д ) =(2р/Е)д . Оценка (26) доказана. Из (26) следует Р— ! Р-! 2 ьо рхй — ж р< Т ]х,— хт]< ~- Я22-< ~ Р,2-< ~Е,2'(1 2Р)-! 0П) Р=й для всех р, й, р > й > О, Так как 0 < д < 1, то правая часть (27) стремитсв к нулю при й Р со. Это значит, что последовательность (хй) фундаментальна и сходится к некоторой точке х, В силу замкнутости множества Х точка х„ е Х.
Переходя к пределу при р -~со, из (2р") получим оценку (20). Остается убедиться в том, что х, — точка минимума /(х) на Х, Так как /(х) Е С (Х), то при й -~ ос нз (23) имеем (/'(х,), х — х„) > 0 при всех х Е Х. Учитывая выпуклость /(х), отсюда и из теоремы 4.2,3 заключаем, что х, — решение задачи (1). Теорема 2 доказана.
П Из (20) п]ри й =0 имеем ]хо-х,]<(2р/5)у(! — д) '. Это неравенство означает, что метод(6) при Х ф Е, так рке как и метод (8), который получен из (6) при Х = Еь, сходится, вообще говоря, лишь при выборе достаточно хорошего начального приближения. 4. Перейдем к рассмотрению метода (2)-(4) с выбором шага ай = ЛЬ, где ' — минимальный номер, для которого выполняется неравенство (10). Этот ва иант метода Йьютона будем называть методом (2)-(4),(10). Покажем, что метод (2)-(4),(10) сходится при лробом выборе начального приближения и этим выгодно отличается от метода 2)-(4),(5). Т е о р е и а 3.
Пусть Х вЂ” замкнутое ее!пухлое множество из Е", /(х) е Са(Х) и р]с! <(/ (х)8,8)<М]с], жеХ, бей», (28) еде Е „— подпространстео, параллельное аффинной оболочке множества Х, а рь М— постоянные, 0 < р < М. Тогда последовательность (хй), определяемая методом (2)- (4), (10), при любом начальном приближении мое Х существует и сходится к точке х„— решению задачи (1), Если, кроме того, /е(х) удовлетворяет услоеию Липшица (18), то найдется номер йо такой, что е (4) ай — — 1 при всех й > йо и справедлива оценка ] < 2Е ~,2- < 2Е,2'(1 уз')-! й > й, (29) 1ь й До к за а тел ь с т а о. Согласно теореме 4.3.4 функция /(х) сильно выпукла, Тогда из теоремы 4.3. | следует существование и единственность точки жй, удовлетворяющей условиям (3). Согласно теореме 4.2.3 тогда (/р,'(жй, х — жй) > 0 или (/(хй)+/рр(хй)(яй — хй),х — жй) >0 при всех жеХ (30) Если оказалось, что хй — — жй, то иэ (30) имеем (/'(жй), ж - хй) > О, ж е Х.
В силу теоремы 4.2.3 и выпуклости /(х) отсюда следует жй = х, = х, — задача (1) решена. Поэтому можем считать, что хй ф ж„. Тогда / (ж„) < / (хй) = О. Покажем, что тогда существует хотя бы один номер ! > О, для которого выполняется условно (!0). С этой целью возьмем произвольное число а, 0 < а < 1, и положим ж = жй + а(яй — жй). Отсюда и иэ выпуклости /й(ж) следует /р (х ) ( а/р (хй) + (1 — а)/й (хй ) = а/й(хй) < О.
306 Гл. 5. МЕТОДЪ| МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ $10. МЕТОД НЪЮТОНА ЗОТ (33) ~к» ! = хк ак(/ (хк)) /'(х„), й =О, 1 (39) (42) (45) (46) Так как хк — точка минимума сильно выпуклой функции /к(х) на Х, то согласно теореме 4.3,1 — к!г < (2/„)! „(,к) /„(х„)! = (2/и)!/,(-„)! Подставив эту оценку в (32), получим /(х«) — /(хь) ~ (-и!/к(хк)!+ а~(М/!к)!/ь(хк)!, 0 ( а < 1. Возьмем произвольное а, удовлетворяющее условиям О< =Л(! — е)и/М «(! —.)д/М<!.
Отсюда и из предыдущего неравенства будем иметь /(жк) — /(ха+ а(хк — жк)) > а(1 — а(М/и))!/к(жк)!) еа!/к(хь)! (35) при всех а, удовлетворяющих условиям (34). Возьмем такой номер пк ) 1, для которого Л ж ( (~ (1 — е)и/М < Л '. Отсюда следует, что 0( еа — — Л(! — е)и/М ( Л ((1 — з)и/М. (Зб) Таким образом, а = Л™ удовлетворяет условиям (34) и, следовательно, при а = Лх будет справедливо неравенство (35), Это значит, при к = т выполняется условие ( ! О).
Тогда найдется наименьший номер к = ьг 0 < ы < гп, удовлетворяющий неравенству (10). Приняв в (4) ак — — Л", получим следующее приближение х Тем самым показано, что последовательность (хк) из метода (2)-(4), (10) при любом начальном приближении существует. Из (10) при к = ко имеем /(хк) /(хк.
1) > за»им(хк)! й О 1 Учитывая, что согласно (36) аь — — Ль ) Л ж > ео, отскода получим /(хк ) — /(хк „! ) ) екг!/к(хк)!, й = О, 1,... (37) Таким образом, /(хк) ) /(хк „,) > /ы й = 0,1,... Тогда существует 1пп /(хк) ) /, и 1пп (/(хк) — /(жк ь ~)) = О. Из (37) теперь имеем !пп /(жк) = О, а из (33) следует к «« к ю 1ип !хк — ха ! = О. (38) Далее заметим, что согласно (37) последовательность (ж„) 6 М(хо) = (х.' х 6 Х /(х) ч /(хоН. Для сильно выпуклых непрерывных функций множество М(хо) выпукло, замкнуто и ограничено. Тогда последовательность (ж ) имеет хотя бы одну предельную точку. Пусть о, — прок 2 извольная предельная точка (жь) и пусть (жк ) — к а„.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
