И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 24

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 24)

162), найти такую ортогональную матрицу А», что сумма квадратов внедиагональных элементов матрицы А»В» (Н»») А» меньше числа р». Положить Н» = Н»»А» и обозна т » чить через 1»» м 1= 1, ..., п, собственные значения матрицы В» (Н~ (В (32 И предлагается также другой эффективный способ вычисле- ния матрицы Н„, основанный на преобразовании Хаусхолдера и ЯЬ вЂ” алгоритме для вычисления собственных векторов и собствен 1гз ных значений симметричной матрицы [300 с. !90 и 203). В начале строится такая матрица У„что матрица Г« = У»В» (Н» 1) У, т имеет трехдиагональную форму, а после с помощью алгоритма Я1. вычисляется матрица Ч», столбцы которой являются собственными векторами матрицы [У», и полагают Н» = Н»-~У»Ч») В качестве чисел )>«», ! = 1, ..., и, берут элементы главной диагонали матрицы Аг»В» (Н» ~) А».

Х. Положить 1= О. Х1..Вычислить числа е~» и тсм при которых выполняются следующие два неравенства 0(х'", е,м чс», Ь'+'»)(о»илб(еьм х'», Ь'+ь»)/ес»', 0(х", ес», том Ь'+'»)( — уаи» и одно из неравенств 0(х", есм чиль Ь'+''); въс»(! — о)6(есм х'", Ь'+ь»)!ас», или тс» и р. (Вычисление величины тс»(! О, 1, ..., и — 1) ре- комендуется начинать со значения, равного ()и+ь»)-'). ХП. Если ас» В з», то положить рс» = Чес» Ь (ею м х'», Ь+ ' ) и перейти к шагу ХП1, если ес» ( е,, то положить рс» = 0 ц-ь» и перейти к шагу ХП1. ХП1.

Положить х'+' " х'»+ рс«Ь'+ь» и перейти к шагу Х 1Ч. Х 1Ч. Если 1 + 1 = и, то положить х»+' х" » и перейтн к шагу ХЧ; иначе положить 1 ! + 1 и перейти к шагу Х1. ХЧ. Вычислить значение т» = ппп(т„[шах ~рс» 1[)'). О«<«-1 ХЧ1. Положить Ь = Ь -[- 1 и перейти к шагу ЧП. Теорема 1. Пусть выполняется предположение 1 и ! 1Ц .множество (х [ 1, (х) ( !» (х')> х с В") ограничено; (И) — матрица воюрых производных Ч~„!, (х) удовлетворяет неравенствам у«[!у[!'((Ч, !»(х)у, у)~у»[[у[~, 0(у«(у«(оо, Чх, уЕВ"; ((о) Д»~(и»~(т„Ь= 1, 2, .... Тогда, если в алгоритме 1 вычисление величины тс» (1 = О, ...

..., и — 1) на ии«ге Х1 начать со значения ()л„~ «)-', то последова- гпельность (х»)» ыюрожденная алгоритмом 1, сходится к единст- венному решению х* с квадратичной скоростью [[х»+> — х>«[(соп51[[х» — х»[[«> сопз1) О. Замечание 1. Если в алгоритме 1 матрицу Нм состоящую из >столбцов Ь'», ..., Ь" », вычислять по правилам Ь'» е', Ь'+ь»=*И+к»![Ь«+ь»[, 1 1, 2, .;., и — 1, $14 где Ь'+ь» = е'+' — ~ фЫ", 1 = 1, 2,..., п — 1; 1 е' (1 = 1, ..., п) — (-й орт; <р„(х», е'+, Ьа»1 ,чи ' л, если <р,,„(х», Ьь», Ьь») ~з,; О, если <р,(х», ЬЬ», ЬГ»)(з„ е»)0 — константа алгоритма; ~р,.: В с В к В -«В', ~р„(х, е, Ь) = а-' [1»(х+а(в+ Ь)) — 1»(х+ ае)— — р,(х+аЬ)+1»(х)[, х, е, ЬчВ", (злтр ачерез Ь»»,1= 1, ..., п,обозначнтьчисла~р»(х»,Ь»»,Ь»»), 1= 1, ..., п, то для такого модифицированного алгоритма 1 теорема 1 будет справедливой. 2.

уекореаныа вари»ах Алгоритм 2 Н а ч а л о. 1 — Ч1. Шаги 1 — Ч1 такие, как и в алгоритме 1. Ос нов но й ц и к л. ЧП вЂ” Х1Ч. Шаги 'ЧП вЂ” Х1Ч такие, как и в алгоритме 1. ХЧ. Положить Р = х"'». ХЧ1. Вычислить значение 1», удовлетворяющее условиям тео- ремы 2. ХЧП. Вычислить вектор а», 1-я компонента которого а~~ = Ц» (х» + 1»Ь"") — ~» (х» — 1»Ь» )Я21»), 1 = 1, ..., п. ХЧП1. Вычислить вектор у = х" — Н»Л» а', где Л» А»В» (Н» ~) А» — диагональная матрица, полученная прн т вычислении собственных векторов матрицы В» (Н~ ~).

(Для вычисления у нет необходимости вычислять обратную мат- рицу к Л». Достаточно обратить лишь диагональные элементы, так как оценка, полученная для недиагональных элементов, обеспечи- вает кубическую скорость сходимости). Х1Х. Если выполняется неравенство Д„(у) ~, (х»), то поло- жить х»+' = у и перейти к шагу ХХ; если )» (у) ~.:ю 1, (х ), то поло- жить х»+' = х и перейти к шагу ХХ.

ХХ. Положить Ь Ь+ 1 и перейти к шагу ЧП. Теорема 2. Если выполняется предположение 1, условия (й), (й») теоремы ! и 0(1»( [шах )ри»[)», р»(а»(~х» — х" '[», »чачи-~ ыь то для скорости сходимссти последовательности (х~)» ь порожденной алгоритмом 2, справедлива оценка ( х"+' — х' ( < сопз1 ( х» — х* 1», сопз1 ) О. Замечание 2. Если в алгоритме 1 матрицу Н, вычислять согласно замечанию 1, то в ускоренном варианте для такого модифицированного алгоритма вектор а» = (а»ы ..., а„) следует вычислять по формуле а,' = Ц, (х" + 1»е') — ~, (х» — 1»е')1/(21»), 1 = 1, ..., и, а вектор у по формуле (и», Ь'") с с» лл р„1», »и»,»и») где ~р„определяется по формуле (2.17). Библиографические у»и»инин.

Параграф написан на основании работ 1322, 323, 3241. 2.8. Итеративные етохастические методы, использующие аналог функции Ляпунова 3 а д а ч а 1. Найти ага ппп 1» (х) для заданной функции кялг 1» ° Л Приводимый ниже метод основан на введении аналога функции Ляпунова с, (х), т. е. функции г, (х), удовлетворяющей условию 1. Условие 1. Функция г, (х) неотрицательна, ш1 с, (х) = О, диффереицируема, а ее градиент удовлетворяет условию Гальдера 117с,(х) — 7г,(у)(<Х$х — у~', 0<1<1, О<Х<со. От с, (х) не требуется существования точек минимума.

Поэтому в качестве г, (х) можно брать с» (х) . 1» (х) — 1п(1» (х) даже в том случае, когда минимизируемая функция 1а не обязательно имеет точку минимума. Часто в качестве г, (х) берется г, (х) = г(, (х, Х*), где а', (х, Х*) — расстояние от точки х до множества решений Х* задачи 1. На й-й итерации в качестве вектора, определяющего направль ние движения к следующему приближению х»+', выбирается реализация случайного вектора а», удовлетворяющего условиям 2 и 3. Условие 2. Выполняется следующее обобщение условия псевдоградиентности относительно г, (х): (Чг,( "), .Ц»)>Е„с,(х») — ()„, Е,~О, Р,:.О.

Условие 3. (а) — распределение случайною вектора $ зависит только от й и х, т. е. $ = С" (х"); (Й)— ~»(х) й»(х)+~»(х), Е~»(х) =О, 11,6 где помехи Ь» (х) взаимно независимы, а й» (х) = Ез' (х) — детерминирована составляющая процесса; (»11)— К»г» "1'+'(ос»+'+ т»г,(х»), о»~ О, т») О.

1. Оевоввой алгорвтм Алгоритм 1. Н а ч а л о. 1. Выбрать функцию г, (х), удовлетворяющую условию 1. П. Выбрать начальное приближение х» Е К", удовлетворяющее условию Ег (хе) ( оо. П1. Положить й = О. Основной ци кл. 1Ч. Вычислитьшагбвый множитель р». Ч. Вычислить реализацию $» случайного вектора $", удовлетворяющего условиям 2 и 3.

Ч1. Вычислить следующее приближение х»+' = х» — рД». ЧП. Положить й = й + 1 и перейти к шагу !Ч. 2. Слодвмоеть алгорвтма в ередвом Теорема 2. Если выполняюпсся условия: (»)— О ( т» ( 1, й = О, 1, ..., ~ т» = ео, где т» = р» (0» — Хр'т»/(1+ 1)); (И)— 1ппр»(р, 1»~О, »-~ ею где 1»» = (р»сс)»+ ».1 1 р» о )1т» Х с+с с+й то для последовательности (х»)ь.о, порожденной алгоритмом 1, справедливо 11пт Кс, (х») ( 1». »-ме Если при мпом р» ( 1» для всех й, то »-с с» с Ег,(х»)(Кг,(хе) П (1 — тс) + 1»~1 — П (1 — тс) . с-о с=о Теорема 2'. Если выполняяипся условия.' (2)— 1=1; О,=О, й=о,1, ...; О„=О, й=о,1, ...; о»=»с; й=О, 1, ...; т»=т, й=О, 1, ...; 117 (И) — шаговый множитель р» в алгоритме 1 постоянный, причем р»=р, О<р<20/Хт, у=О, 1, ..., !пп Ег, (х») < Ха'р/(20 — Хтр) » со Кг, (х») < Кг» (х') (о,)» + Хо'р (1 — (о,)»)/(20 — Хтр), где о, = 1 — р (Π— Хтр/2) < 1.

Теорема 2 гарантирует сходимость алгоритма 1 в среднем в области малых значений функции г, (х) и дает оценку скорости сходи- мости. Теорема 2' гарантирует сходимость в среднем алгоритма 1 со скоростью геометрической прогрессии в области, где г» (х) < у, причем у = Хо»р/(20 — Хтр) тем меньше, чем меньше р и чем меньше адднтнвные помехи (т. е.

о'). В ситуации с мультипликативными помехами (т. е. когда о = О) можно выбирать постоянный шаговый множитель р» р, и если О < р < 20/Хт, то имеет место сходимость в среднем со скоростью геометрической прогрессии. Теорема 2". Если выполняется условие (1) теоремы 2 и 1пп р» = О, »-~аю то последовательность (х»)»=ь, порожденная алгоритмом 1, такова, что !ппЕг»(х») = О. » м Если, кроме того, (1)— 1!шу»<т< 1, »-~ в у» = (1»»/!»»+~ — 1)/тм й = О, 1, ..., Ег» (х») < р»/(1 — у) + о (р»); (И)— у»(у< 1 для всех й, то Кг,(х")<р» =+1, ' — — ! П (1 — (1 — т)ч,) ! 1 ! Ег,(х») ! — н ! — т г=ь (И1)— 1пп у',',~ у ) 1, т' =(1 — р»+~/1»»)/т»+ь я=О, 1, ..., ыв /» — ! Ег,(х») = О ~ П (1 — т!) ((о)— у»~ у) 1 для всех й, то » — ! Ег,(х») <(Егд(хв) + р,/(у — 1)) П (1 — т!).

!=о Теорема 2"'. Если выполняется условие (!) теоремы 2' и условия (1)— С 0(р»(2(8 — в)/Хт, 0<в<0, ~ р» = оо! »-в (И)— р»-!-0 при й-»оо, то последовательность (х~)» в, порожденная алгоритмом 1, такова, ипо Ег» (х») -» 0 при й -» оо. Если при мпом: (И!) — Ар» монотонно возрастает, йр» -» р ) О-! (возможно, р оо), то Ег (х») ((Ко»/2(0 — р-')) р»+ о(р ); (1о) — йр» монопюнно убывает, йр» -+ р < О-! (возможно, р = 0), где е — основание натурального логарифма. Теорема 2" является дискретным стохастическим аналогом теорем о сходимости по функционалу в детерминированных методах оптимизации и в ней даются оценки скорости сходимости как асимптотические (утверждения (1), (И)), так и справедливые при всех й (утверждения (11), ((о)).

Характеристики

Список файлов книги