Л.А. Растригин - Теория и применение случайного поиска (1121205), страница 19
Текст из файла (страница 19)
Кифсром н Д. Вольфовицем 12]. Первая работа связана с отысканием корня функции, на которую накладывается помеха, вторая — с отысканием максимума (нли минимума) функции, на которую также накладывается помеха. Эти методы являются, по сути дела, модификацией метода градиента. Более широкое обобщение методов стохастической аппроксимации дано в работах 13--5], а подробный обзор дан в работе 15]. В работе ]7] показано, что самые разнообразные задачи идентификации, распознавания изображений, исследования операций и т.
д. связаны с методами стохастнческой аппроксимации. Однако в последнее время широкое распространение получили также и методы случайного поиска, которые успешно конкурируют с градиентными методами. Это и дало основание рассчитывать на большук~ эффективность случайного поиска по сравнению со стохастической аппроксимацией, предназначенной для отыскания экстремума функции. Наша задача заключается в оценке сходимостей обоих методов на одинаковых объектах.
Предварительно декан<ем сходимость алгоритма случайного поиска. пв й 52. СХОДИМОСТЬ АЛГОРИТМА СЛУЧАЙНОГО ПОИСКА Предложенные в методе стохастической аппроксимации критерии сходимости могут быть разбиты на два класса. !( первому классу относится критерии, применение которых требует подбора последовательностей, удовлетворяющих специальным требованиям. Примером такого критерия служит критерий, установленный в теореме Дворецкого. Второй класс критериев сходимостн содержит прямые (непосредственно проверяемые) условия, т.
е. позволяет вопрос о сходимостн решить алгоритмнчески [5). В настоящем параграфе будут рассмотрены оба критерия относительно метода случайного поиска. Пусть 1"1'(Х) — случайная функция; Я(Х) =МЯ'(Х) — - функция регрессии. Требуется найти значение Х*, при котором Я(Х) достигает своего единственного экстремума (минимума). Алгоритм стохастнческой аппроксимации, решающий данную задачу, записывается либо в виде Х,ч.~==Х; — а, Игаб'1.1(Х), (5.2.1) где дгаг) Я'(Х) = , , -- — градиент функции Я'(Х) дЯ'(Х) дЯ'(Х) дх, ''''' дх„ в точке Х= (хь, .., х„), либо в виде Х,ы — — Х;+ — '-Я'.г(Х;д,) — Я' (х;и;)), (5.2.2) Я~ где 9'~(Х, д) =[Я'(Х~де,),..., (~'(Х.+де„)); е~ = ( 1, О, О, ..., О), ез= (О, 1, О, ..., О), ..., е„ = (О, О, О, ..., 1 ) — базисные векторы; аь д, — некоторая последовательность положительных вещественных чисел.
Однако данную задачу может решать алгоритм случайного поиска с епарными пробами», который записывается в виде Х;+~ = Х; — а;д;-'АЯ'(и,.) Вь (5,2.3) где АЯ'(д;) =Я'(х;+й;Е,) — 1е'(х; — д, Я,); 119 Е = (ь!,..., о„) — случайный вектор, конец которого равномерно распределен на п-мерной гиперсфере с единичным радиусом, Х= (хь...,х„) — вектор аргументов. 1.
Докажем теорему о сходимости последовательности (5.2.3), которая является обобщением результатов работы [9). Теорема. Пусть функция 9(Х) имеет непрерывные первые дав и вторые производные, причем д д ограничены для всех дхадх А, т=1,...,п и ппп ! !(Х) > — оо. Пусть далее выполнены условия: (5.2.4) ~, а;=оо; ! ! ~; аРа,— (5.2,5) ;=! ~„а!й!! <., оо; о ! М(м'(Х!) — !',!(Х;)1Х„..., Х„) =!3; М((() (Х!) — ()(Х,)) )хь... Х!) ~й.~-; д!-~М(ЛЩ(д!)(1Е,))з/Х!... Х;) -й!< оо где йж йь ..
— положительные константы; ИЛ=( Х вз!ь)': — ноРма вектоРа Еь а- ! Тогда последовательность (5.2.3) сходится в точке Ха с вероятностью !. Доказательство. Обозначим через (Х, 7) = ~, хьр1, скаляр. ь-! нее произведение Х и У, а через В(Х) — матрицу вторых прои 1- водных функций (,1(Х) в точке Х. Разложим (1(Х!! !) по формуле Тэйлора: !!(Х;+!) =Я(Х;) — а!д,-!(Л!1'(д!)Еь пгаб 1!(Х!))+ + —.0,2а!-2ЛУТЫ<В(Х,— 1аМ'Ыа! 'Е!)Еь Е;) "- =Я(Х!) — а!у!-'(ЛЯ'(д!)Еь дга!1 Я(Х!))+ + — а! д!ЧРЯ'(д!) й,!)ЕЯ', 1 !20 Тогда д;-'М(т'(ц,:)Е;/Х,...
Х,) = = й4 ягас( Я(Х;) +г;до (5.2.! 3) где г; — и-мерный вектор, составленный из злементов /г,(х). Из (5.2.8) и (5.2.9) вытекает следующее неравенство: а. 'М (Л%'(В) !! Ел'/Хь..., Хм) = =-д -'[М([Лд (д ) !!Е !!Р/Хп ", Х*) +а 'М([Лд'(д ):с Х!!Е;!! — М(й;) [!Е;!!)'/Х,,..., Х;) л,+ +а* 'М(([9'(Х +4/'Е') — ЖХ*-+а*Е') Р+ +2 [Я'(Х;+д;Е;) — Я(Х;+дгЕ!)) [Я'(Х;— — д;Е,) -О(Х,-д,Ег)[+[О (Х,-д,Ег)— — Я(Х; — д Е')[')ЦЕ !!'/Хь..., Х|) =11+4/ганг — з.
(5.2.!4) !1одставляя (5.2.13) и (5.2.!4) в (5.2.11), получим М(д(Х,„)/Хь..., Х,) «Ц(Х,) — '~~'--'Х х (Ьт(а,) Е;/Х„..., Х,), д; — М[ЛЮ'(я;) Е;/Х„... ., Х;]-г;а;>+ — ' А++ -4) (5.2.15) где О =1=' 1. Последнее неравенство получается в силу ограниченности вторых производных. Возьмем от обеих частей неравенства (5.2.10) условное математическое ожидание при данных х„..., х;: МЯ[(Хгы)/Хь... Х,) -.Я(Х;) — а;а;-'(вагаб ЯХ Х (Х;), М (ЛЯ'(д;) Е;/Хп..., Х;) ) + —,аРу; — Чз Х ХМ(ЬЯ'(д;) [!ЕДз/Хь... Х,), (5.2.!!) Определим д;-чМ(ЛЯ'(д;)Е;). Учитывая, что Мве,х= —, имеем и* д; 'М (Л'Я'(у,) фгх/Хь..., Х;) = 1 =М ([2(дгаб Я(Х;), Е;)+ — д.;([В(Х;+ +/~д;Е;) — В(Х; — /зд;Е,) [ Еь Ед) $гхХь... ..., ХД вЂ” - — +/гз(х) дь 2 д() (Х) и дхь (5.2.12) В силу неотрицательности численного значения нормы и неравенстваа Каши — Буняковского М(Ц(Хгы))Хь..., Х,) «д(Х;) + + — '(гь М(ЬЯ'(й;) Е;/Хь..., Х;))в 4 "'а' цм(ЛЯ'(а;)Е,(Хь..., Х;) цт+ала,-ЧБК ~О(Х,-)+ — "цг,~!(М(ЛзО(д,) цВ,~!з)Хь..., Х,)!'-+ +алй';-зйз~Я(Х,)+ — 'д;ЦгЦй|ч1+йзалй;-', (5.2.16) где цгц=шахцг;ц.
! Это равносильно неравенству м(г, )хь..., Х;) ~кь (5.2.17) где йт О Й Х;=я(Х;)+ — 'цгц ~, а,й~+йз ~, а',й,— '. й4 Ь-1 Ь (5.2.18) Взяв условное математическое ожидание прн данных Яь...,У; от обеих частей неравенства (5.2.17), получаем М(Х; )гь..., Х;) ~Кь (5,2.! 9) Неравенства (5.2.19) показывает, что У; — полумартиигал, причем МУ;+,~МХ,~...<МЕ1 ~со, МЯ(Х;) "'ео. Осталось доказать, что Р(Игп Я(Х;) =ф„ы)=!.
(5.2.20) (5.2.21) так что, согласно теории полумартннгалов, последовательность Х! сходится с вероятностью ! к пределу, а значит, в силу (5.2.5) и (5,2.6), из (5.2.18) следует сходимость Я(х,) с вероятностью 1 к некоторой случайной величине. Причем из (5,2.18) следует, что Доказательство (5.2.21) проводится по методу, приведенному в (9). Из сходнмости Я(Х,) следует ее ограниченность с вероятностью 1.
Множество (Х: Я(Х) ~Щ является компактом, следовательно, угад Я(Х;) и !!ягад 9(Х,) !! являются ограниченнымн величинами. Пусть игаг( Я(Х,) !! - А=сопз1. Используя (5.2,13) и (5.2.!4), перепишем (5.2.!1) в следующем виде: М(Я(Х;+,)Хь..., Х;) =()(Х,— а,(игай 1~(Х;); й, угад Я(Х;) 4-г;уф+а,'йг-Чь~Я(Х;)— --ьпй,!!пгаг( Я(Х,) !Р+д,а;!!дгаг( Я(Х;) !! Х 'р,'!!г;!!+ аРИ;-~й~ -Ц(Х,) — ьпй4!!огай Я(Х;) !Р+ +а;д;А!!г!!+пай, тйь (5.2.22) Возьмем математическое ожидание от обеих частей неравенства (5.2.22): М9 (Хг м) .= й(Я (Х,.) — а АМ !! дгаг( () (Х,) Р+ +а;й,А!!г!!+а$2а;.тй5.
(5.2.23) Неравенство (5.2.23) можно переписать так: М9(Хьы) (Я(Х~) -й4 2, а,М!!йтао Я(Х,) !!~+ в ! +А!!г!! ~~ а„д,„+йз ~, пад,.'. (5.2.24) Из (5.2.24) и (5.2.5), (5.2.6), (5.2.20) следует, что ~ а,,М!!йтаг( Я (Х,) !Р ~ сю, з-! (5.2.25) !23 Учитывая (5.2.4), из (5.2.25) получаем М!!угад Я(Х,)!!т- О, т.
е. последовательность угад 9(Х,) сходится к нулю в среднем квадратическом. Это гарантирует существование подпоследовательности йгад1,1(Х х), сходящейся к нулю с вероятностью !. Принимая во внимание непрерывность функции Я(Х) и сходимость последовательности 1,~(Х;) к пределу с вероятностью 1, получаем доказательство теоремы. Покажем, что процедура случайного поиска дуовлетворяет условиям теоремы Дворецкого [1], откуда также следует сходимость с вероятностью 1 и в среднем квадратическом. Для этого воспользуемся теоремой 2 из [5], в которой доказывается сходпмость алгоритма (5.2.2) в силу того, что он удовлетворяет условиям теоремы Дворецкого, многомерное обобщение которой дано в теореме 1 из [5].
Теореиа 2 из [5] формулируется следующим образом. Пусть а, и и! — последовательность положительных чисел, удовлетворяющих условиям: ~ а!= ! -! (5.2.26) ~„ а!д! - со; ! — ! йщ й;==О. (5,2.27) (5.2.23) Пусть далее (5.2.29) М~~ХД'< И [()'(Х) -д(Х)Р~<о Для всех Хен)с" (5.2.30) Предположим, что для некоторого ер)0 (О-д~еа) существуют такие постоянные А и В, при которых для всех Хая)с" имеет место Щ (Х, й) — 1~ (Х, й) и ~А ~~Х вЂ” Х*!!+ В, (5 231) ИЯ+(Х б) З-(Х.б)П) >О о~о о !24 а где й Х!) = ( ~ хьз) ч . а=! Кроме того, предположим, что для произвольных постоянных о и !'. (0<й<Е) существуют такие е!>О (0<у=- е!) и й<!!Х вЂ” Х ))<1., при которых для й>= имеет место !! ! т'2 <(Х-Х*),[И (Х,а) — () (Х,а®» ~йЦХ-Х*!! Я+(Х, д) — Я (Х, и) )! (5.2.32) тогда (5.2.34) Р !пп (Х,=Х*) =1; ~'-~ О !пп М!~Х; — Х~!!'=0 (5.2.35) Для того чтооы доказать сходнмость алгоритма (5.2,3), представим случайный вектор ЛЯ(й)Я в виде вектора Ма (ЛЯ(д)Я) и случайного вектора с нулевым математическим ожиданием и ковариационной матрицей Ма(Л'9(д)ЯЯт).
Здесь Т -- знак транспонировання; Ма — осреднение по Я. Замеьп|м в условиях (5.2,32), (5.2.33) вектор Я+(Х, д) — Я (Х, д) на Мв (Щ(й)Е). Условия (5.2.26) — (5.2.30) остаются без изменения. Используя (5.2.30), получим, что суммарная дисперсия случайного поиска М[(~'(Х) -а(Х))з+!уа!!Да(д) Я!!'~й,: так как элементы ковариацпонной матрицы сот[5!;!(й) ХЯ) ограничены из-за того, что условие (5.2.31) для алгоритма (5.2.3) записывается в виде !![()(Х+дЯ) — а(Х вЂ” дЯ)) Я~!~А!!Х вЂ” Х")!+В. Теперь, повторяя дословно доказательство теоремы 2 из [5], получим доказательство сходимости алгоритма (5.2.3).
3, Заметим, что сходимость с вероятностью 1 и в среднем квадратическом имеет место для алгоритмов (5.2.2) и (5.2.3), если условия 1) !п!((Х вЂ” Х")„дгадЯ(Х)У= 0 при всех е~О; а<за 2) для всех й' и Хеп)с существует такое о>0, что М!!угад Я'(Х) !!з =а(1 — ХтХ) в теореме 1 из [8) заменить на условия Г) й-'!и! ((Х вЂ” Х"'),[Яч.(Х, д) — (,! (Х,д))))0 при всех е)0; е<;!х- х*~,'<~ 2') для всех д и Хан)с" существует такое И>0, что И-'МЩ' (Х,а) — д' (Х, К) )!'«а(!+Хтх) для алгоритма (5.2.2), либо на условия 125 1") д '!п(((Х вЂ” Х*),Ма(АЯ(д)Е)))О при всех е~О; а.,х -х"„м 2") для всех Хее!с" существует такое д>0, что д-з~ь1(х() з(,) 1~ Р)~~д(1 ! ХтХ) $ ВЗ. СОПОСТАВЛЕНИЕ СЛУЧАИНОГО ПОИСКА И СТОХАСТИЧЕСКОИ АППРОКСИМАЦИИ В ЗАДАЧАХ ОПТИМИЗАЦИИ Рассмотрим сначала метод стохастической аппроксимации.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
