Ф.П. Васильев - Методы оптимизации (1125241), страница 27
Текст из файла (страница 27)
Будем пользоваться обозначениями: С'(Х) — множество всех функций, непрерывно дифференцируемых на множестве Х, С'(Х) — множество всех функций, дважды непрерывно диффепенцируемых на множестве Х. Возьмем какую-либо функцию 7(х), определенную на множестве Х с Е". Пусть точки х, х+,6 е Х таковы, что 6 ф О, х+ 26 Е Х при всех (, 0 < ! < 1. Тогда можно рассматривать функцию одной переменной д(э) = у(х+ э6) при ( я [О, Ц. Оказывается, если Г'(х) Е С"(Х) при р = 1 или р = 2, то д(э) й С"[О, [[, причем д'(э) = (у'(х+ з6), 6), дэ(4) = (Уя(х+ !6)6, 6) О < ( < 1, (Ц В самом деле, если, например, 7"(х) е С'(Х), то, заменив в формуле (2.5) х на х + 16, 6 на 7Л(6, получим д(4+ (лэ) — д(4)=ЬЮ(У(*+(6), 6)+-'(Ь|)'(Ул(*+46) 6, 6)+~([д ( ['). Такое павло>кение означает, что д(э) е С'[О, Ц, и указывает на справедливость формул (1).
Для функции одной переменной имеют место формулы д(э) — д(0) = д (0 э)э = 1 д (т)ь(т = д(0)э + 2дл(022)з~, о д'(() — д'(О) = дл(0,4) (, 0 < 0„0„0, < 1. $ б. ВСПОМОГАТЕЛЬНЫЕ ПРЕДЛОЖЕНИЯ чаем раземенных: (2) (6) что точки 0<! <1, х — мномиыно эти точки асто при- условию ент у'(х) с посто- (6) ). Тогда (Т) ) гй. (6) полу. которые ции, при ва, что (6) Полагая в этих формулах ! = 1 и пользуясь равенствами (1), полу личные формулы для конечных приращений функции многих пер 7(х+ 6) — у(х) = (у'(х+ 0,6), 6) = 1(7'(х + 46), 6)г(э', у(х + 6) — у(х) = (у'(х), 6) + -(ул(х+ 026)6, 6), (у'(х+6) — у'( ) ") =(з'( +02~)6 ") где 0 < 0„02, О, < 1.
Далее, так как — „',(Г(х+!6))=Г(х+(6)6, 0<4<1, то, интегрируя это равенство по э' на отрезке [О, Ц, получаем 1 у'(х+ 6) — у'(х) = ) уэ(х+ 36)6г($ = ([ (ч(х+ 46)е(з) 6. о о Подчеркнем еще раз, что в формулах (1) — (5) подразумевается, х, х+ 6 принадлежат множеству Х вместе с отрезком х+ !6, В частности, эти формулы верны на любых выпуклых множества жествах, которые содержат вместе с любыми двумя своими точка и отрезок [ы, о) = (и, = о и + (1 — ст)о, 0 < ст < 1), соединяющий (подробнее о выпуклых множествах см. $ 4.1). 2.
При описании и исследовании методов минимизации нам ч дется иметь дело с функциями, градиент которых удовлетворяет Липшица. Определение 1. Пусть у(х) е С'(Х). Скажем, что гради этой функции удовлетворяет условию Липши>(а на множестве Х янной Х, > О, если [(ч(х) — у'(у)[ < Ь [х — у[, х, у Е Х. Класс таких функций будем обозначать через С' '(Х). Лемм а 1. Пусть Х вЂ” выпуклое множество, у(х) е С''(Х [У(х) — Х(у) — (~'(у), х — у)[ < Ь )х — у[2/2 при всех х, уе Х.
Д о к а з а т е л ь с т в о. С помощью формулы (2) имеем ! 1(х)- 1(у) — (Г(у) * — у) =1(Г(у+ 1( — у)) — Г(у), * — у о Пользуясь неравенством Коши — Буняковского, с учетом условия чим [у(х) — Х(у) — (у'(у) х — у)[ < 1 1 < ) [1"(у+ д(х — у)) — у'(у)[[х — у[йз < 1 Ь [ — у['(оэ = о о 3. Приведем несколько лемм о числовых последовательностях, нам пригодятся при доказательстве сходимости методов минимиза оценке скорости их сходимости.
Л е м м а 2. Пусть числовая последовательность Таь) така а„+,<а,+6а, 6 >О, 6=0,1,..., 2, 6„<оо. Гк 2, КЛАССИЧЕСКАЯ ТЕОРИЯ ЭКСТРЕМУМА $ б. ВСПОМОГАТЕЛЬНЫЕ ПРЕДЛОЖЕНИЯ 89 Тогда существует 1пп а, < оо. Если (ас) ограничена еи(е и снизу, то 11ш ас конечен. Заметим, что если 6 = О, й = 0,1,..., то,последовательность (а,.) не возрастает, и лемма 1 превращается в хорошо известное утверждение о пределе монотонной последовательности. Д о к а з а т е л ь с т в о. Суммируя первое из неравенств (8), имеем (9) а <а + ~ 6с<а+~ 6; пРи всех т>1с >О. ПУсть!1ш аь= !пп а„, й,<й„<о и=0,1,...; 1пп й„=со. Р Положим в (9) й=й„.
ПолУчим а„<а, + Х 6с 'Ут > й„, Следовательно, О =с„ 1!гп а <ас + Х , '6г длЯ всех и=1, 2,... Отсюда пРи и- оо имеем !пп а < П.-~ < 1пп а, = 1пп а . Но всегда 11гп а„< 1пп а„, поэтому !пп а = 1!гп а„. И Р т ж~.ы Отсюда следует существование предела (а,), Далее, при й = 0 из (9) следует ограниченность (ас) сверху.
Поэтому, если (а.) ограничена еще и снизу, то !!гп а„конечен. 0 Ле м м а 3. Пусть числовая последовательность (6.) такова, что 6,>6 — 6„6,>0< й=о,'1,..., Х 6с <со ь-о Тогда существует 1пп 6с > — оо. Если (6„1 ограничена еще и сверку, то Ипг 6с конечен. Эта лемма сводится к лемме 2, если принять 6ь = — а, й = 0,1,... Л е м м а 4, Луста числовая последовательность (а,,Х такова, что а„> О, й = О, 1,...; а„— а„, > Аас, й > йо > О. (10) Тогда аз=О(й '), й=1, 2,..., т. е. найдется постоянная В>0 такая, что 0<аз <Вй ', й=1,2,...
(11) Доказательство, Если а„=О при некотором гп > й, то из (10) следует, что а, = 0 при всех й > т, и оценка (11) становится тривиальнои— в (11) достаточно взять В = т шах а,, Поэтому пусть а„> 0 при всех !СГС < и > й,. Тогда из (10) имеем — — — — "+' > — о — А>А>0, и>й, о„< о„а„а„< ~ а„ Суммируя эти неравенства по и от й, до некоторого й — 1 > йо, получаем а,' — аг>А(й — й) или а„<А '(й — йо) ', й>й.
Но(й — й) '<(йо+ + 1)й ' при й > й, поэтому 0 < аь < (й + 1)А 'й '. Если 1 < й < й„то 0 < а„= йа„й ' < й ( гпах ас)й ', Остается в (11) принять В = гпах((й, + ~<с<А +1)А ', й„шах а,). С! 1 < С < Р„ Л е м м а 5. Пусть числовая последовательность(ас) удовлетворяет условиям (12) а,>0, йедг=(1,2,...); ос Л асР~ ~<со Л + сР~ йЕХо а, <Вй-ср, й 6Х,; а,,<ас+Сй ", йеХ„й+161о, (13) (14) (15) где А, В, С, р — положительные постоянные, р < 1, а множества индек- сов Х, 1, таковы, что Х, о Х, = Аг, 1, и Х, = И (случаи 1, = Я или 1 = О не исключаются), Тогда существует постоянная Р > О такая, что (16) 0<а, <Р1с ', й=1,2, Доказательство.
Можем считать, что А > В+ С, так как если неравенство (13) верно дли некоторого А = Ао > О, то оно верно для всех А > Асс Выберем натуральное число й так, чтобы (17) 4 < йс <(йо+1)Р < 6 Убедимся в том, что такое число существует. Для этого перепишем (17) в равносильном виде; 4' < 66 < 6" — 1, где е = р ' > 1. Существование'такого числа й будет доказано, если покажем, что длина отрезка 14',6' — Ц при любом г > 1 не меньше 1, т. е. 6' — 4' — 1 > 1 или д(е) = 6' — 4' > 2 при всех е > 1.
Но д'(е) = 6' 1п 6 — 4' 1п 4 >!п 6(6' — 4') > О, г > 1, так что д(е) строго монотонно возрастает при г > 1. Следовательно, д(е) > д(1) = 2 для всех г > 1. Таким образом, при каждом р, 0< р < 1, число й„, удовлетворяющее условиям (17), существует. Покажем, что а~„, < 2А(йо+ 1) '. (18) Может случиться, что й, е 1. Тогда воспользуемся неравенством (13). Заметим, что функция /„(а) = а — а'А ' + Ай 'Р достигает своего максимума на числовой оси при а= А/2, и поэтому /с(а) </с(А/2) =А/4+Ай " для всех а > 1, й = 1, 2,, Тогда из (13) с учетом неравенств (17) имеем Оценка (18) доказана. Далее, сделаем индуктивное предположение; пусть при некотором й > й + 1 верна оценка аь < 2Ай Р, Возможно, что й е Х,.
Тогда с учетом (17) имеем а, < 2Ай ' < 2Ай,, Р < А/2. Поскольку /„(а) аг,, </ь(Ц, ) < А/4+Айо " <А/4+А/16 < (бА/16)6(й +1) Р < 2А(й +1)- . Если же й, е 1„то возможно и й, +1 е 1,, Тогда из (14), (17) следует, что а,, < В(й +1) "< В(й + 1) '/4 < 2А(й +1) '. Если йо е 1, но й, + 1 е 1о, то из (14), (15), (17) получим Чм < Вй,ос+ Сй сР < Ай,,зр < 2А(й +1) Г $6, ВСПОМОГАТЕЛЬНЫЕ ПРЕДЛОЖЕНИЯ 91 90 где 0<в,<1, <( >О, Й=1,2,..., зпр дй/з, = с < оо. (24) йй! Тогда 1, 2, ... (25) кции. При й = 1 оценка (25) > 1, то из (23), (24) следует (1 — в,)с+се, < ш, +с, что и ельность (а,) такова, что с, = сопз! > О, а, > О. (26) Тогда справедлива оценка с„так что зцр дй /вй = с < со.
й> ! , что равносильно оценке (27) 0 < ай, < (1 — 1/Йз)ай + с, /Й с, =сова(>0, 0<,3 < й = 1, 2, 1, а, > О. (28) Тогда Гз. 2. КЛАССИЧЕСКАЯ ТЕОРИЯ ЭКСТРЕМУМА монотонно возрастает на отрезке 10, А/2], то из (13) следует, что ай, < < /й(а ) ( /й(2АЙ з) = 2АЙ з — ЗАй вз < 2А(й з — й йй). Но при 0 < р < ! справедливй соотношения Й-з й-'р < (й' ! 1)-! < (й'+йз-!)-! — Й-йй!(й ! 1)-! < (й ! 1)-л (19) поэтому ай „, < 2А(й + 1) й.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
