XIV Аттетков и др. Методы оптимизации (1081420), страница 26
Текст из файла (страница 26)
2). При этом значение Дь может быть не единственным (в таком случае выбирают наименьшее значение). *Си.: Карманов В.Г. 172 4. ЧИСЛЕННЫЕ МЕТОДЫ БЕЗУСЛОВНОЙ МИНИМИЗАЦИИ При Ль = О (4.21) переходит в неравенство Т"1х~ '+Дьив) ( )'(х~ '). (4.22) Необходимость в решении задачи одномерной минимизации отпадает, а для выбора значения 7)ь можно использовать различные эвристические приемы. Рассмотрим промежуточный случай Ль Е (О, 1). Для 11 С 2 из (4.20) и (4.21) получаем )'(х ) — Т"(х )>Ль17'1х ) — пцп~(х +Ди )) > > Ль(Дх ') — ~(х '+11и )).
(4.23) Тогда при выполнении условий теоремы 4.3 оценка (4.15) при- мет вид Дх~) — ~(х*) ( ~ ~(хв ') — Т(хь '+Див)') где у — парамвпср сильной вьтуклости функции 1(х). Эта оценка позволяет установить роль параметра* Ль. Пока отношение ~1х~-1) ~~хь) ~К ОУ( ' ~)Р ' остается достаточно большим, значение Ль следует выбирать таким, чтобы произведение ЛЩ оставалось на каждой й-й итерации примерно постоянным. Тогда при сравнительно малом значении Ль нет необходимости в высокой точности вычислений значений Дя и решения задачи одномерной оптимизации функции ~(х" '+ Ди") по аргументу 71 и можно выбрать Бь просто из увловия (4.22). Однако по мере приближения к точке х' минимума целевой функции необходимо увеличивать значение Ль вплоть до единицы и выбирать значение Ня из более Смл Карманов В.Г.
173 4.2. Методы спуска точного решения задачи одномерной минимизации функции Дж" '+ 71иа) по аргументу Д, обеспечивая тем самым выполнение условия (4.17). Высказанные соображения качественного характера справедливы не только для сильно выпуклых функций., но и для еыпуклых функций, удовлетворяющих условиям теоремы 4.1. При некоторых дополнительных ограничениях эти соображения можно распространить на невыпуклые дифференцируемые функции*. Перед рассмотрением вопроса о выборе направления спуска докажем вспомогательные утверждения. Лемма 4.3. Если функция 1(х) непрерывно дифференцируема во всех точках в = у+ тр, т б [О, Ц, то справедливо равенство 1)У+Р) =1)У) ~.~)Р ~1)У+ Р),Р)И .
)с24) о М Функция 6(т) = 1'(у+ тр) действительного переменного т, как сложная функция, непрерывно дифференцируема на отрезке [О, 1), и ее производную для произвольного т е [О, 1), согласно правилу дифференцирования сложной функции, можно записать в виде 6'(т) = (рас1)'(у+ тр), р). Для этой функции верна формула Ньютона .
Лейбница 1 Г 6'(т) с1т = 6(1) — 6(0). а Поскольку 6(0) = ~(у), 6(1) = ~(у+ р), то записанная формула равносильна равенству (4.24). > *Смс Карманов В.Г. 174 4. ЧИСЛЕННЫЕ МЕТОДЫ БЕЗУСЛОВНОЙ МИНИМИЗАЦИИ Лемма 4.4. Пусть функция Т" (х) непрерывно дифференцируема на выпуклом множестве Х С ~"' и существует такая константа 7 ) О, что для любых х., у Е Х выполнено неравенство (4.25) ~ уай ~(х) — ягас17(у) ~ < .5~х — у~. Тогда для любых х, у Е Х справедливо неравонство г (х) — 1(у) > (Егас1Т(х), х — у) — — ~х — у~ . (4.26) г ~ Полагая р = х — у, согласно лемме 4.3 и свойствам скалярного умножения, получаем Л ) — ~Ъ)=~(к ОЪ+ р),п)6 = о 1 =ь ~я*),и-'-/о ~ли+ п) — ~ ~я ),й~.
о Используя неравенство Коши - Буняковского и (4.25), заключаем, что для интеграла 1 в правой части записанного равенства верны соотношения "--У>" ""-".> '- о 1 о 1 г = — Ь~х — у~ / (1 — т) оЬ = — — ~х — у~ . г 2 о В итоге приходим к (4.26). ~ 175 4.2. Методы спуска Вектор, противоположный градиенту функции, называют антпиерадиентном. Антиградиент функции ~(х) в точке х будем обозначать ис(х) = — рас13'(х). Если градиент определяет направление наибольшего возрастания функции ~Лс), то антиградиент, наоборот, задает направление наибольшего убывания этой функции. Для а-й итерации используем обозначения ис = — бгас13(х ) для антиградиента в точке х и ( /с к) ( .. 1У(ха — 1) к) (ис~) ( ягас1 3 (х~ ') ) для косинуса угла между направлениями спуска и антигради- ента. Теорема 4.4. Если выпуклая и непрерывно дифференцируемая в К" функция у(х) удовлетворяет на множестве Хе = = (х Е ~": 3" (х) ( )'(х~)) условиям леммы 4.4, множество Хе ограничено, а последовательность 1х~), построенная в соответствии с (4.20) и (4.21), является релаксационной, то справедлива оценка у(хт) у(ха) с дхе) с сх*) ~ — с ( 11+ 2 ~.
'), ек, (с.28) 2Ат12 я=с где 7 константа в условии (4.25), а т1 = с11ашХе диаметр множества Хе. ~ Используя (4.23), (4.26), (4.27) и учитывая, что ~иа~ = 1, заключаем, что у'(х ) — Дх ) > Ла171х ) — Дх +,Зи )) > > Ль(бгас17(хь ), х~ л — (х~' ~ + ри"))— — — )х — (х +сЗи )( = Ляс3ста)ис !— Л Ь „. ЛаК~З 2 2 для любых значений 33 > О.
Из условия максимума правой части полученного неравенства выберем )3 = ссь~ис" ~/Ь и после 176 4. ЧИСЛЕННЫЕ МЕТОДЫ БЕЗУСЛОВНОЙ МИНИМИЗАНИИ подстановки этого значения, обозначив ьгь = Т"(аь) — Д~ж"), запишем я~8 аог'1 )~ >0 2Ь Отсюда, используя (4.10) и учитывая, что ~х" — а'( < и, находим Льо г г 'Рь — ' 'Рь > г 'Рь — О 21,0г Сопоставляя это неравенство с первым неравенством в (4.3) и обозначая уь = Льаг~/(27л1г), согласно лемме 4.1, получаем оценку (4.28). ~ Оценку (4.28), доказанную в теореме 4.4, при некоторых дополнительных условиях можно упросгить, а именно если для некоторого номера итерации т коэффициент о- ненулевой, то сумма в (4.28) отлична от нуля и мы можем, немного ухудшив эту оценку, опустить в ней единицу.
В результате получаем ~(а ) — ~(ж*) < „, т > т. (4.30) 27 Нг г Теорема 4.5. Если сильно выпуклая и непрерывно дифференцируемая в ьс" функция 7(ж) удовлетворяет в ьс" условиям леммы 4.4, а последовательность 1а 1, построенная в соответй ствии с (4.20) и (4.21), является релаксационной, то справедливы оценки ~(а ) 1(в ) < ~ Ч х ~ г~ ю, < ехр~ — — ~Льоь), т, Е 74, (4.31) я=1 < — ехр1 — — ~ ~Льоь~), т Е 14, (4.32) я=1 177 4.2. Методы спуска где А — константа в условии (4.25),. а у — параметр сильной выпуклости функции у (х). Согласно теореме 3.18, имеем ~8гасУ('(х~ ~)~~ > у~рь с и, подставляя это неравенство в (4.29), находим 2 ~рь с — соь =7(х" ') — Дх") > у "соь и Й ЕИ. Сопоставляя это неравенство с первым неравенством в (4.8) и обозначая ть„= уЛяаф(27), согласно лемме 4.2, получаем оценку (4.31).
Оценка (4.32) следует из (4.31), если принять во внимание доказанное в теореме 3.18 неравенство ~х~ ' — х*~2 < < -'(У(х'-") -У(х*)) ~ у Если на каждой итерации направление спуска выбирать так, чтобы для всех ВАМИ в (427) 0< а<аь <1и 0<Л<Ль <1, то вместо (4.30) получим 7(~~) — у(х') <, Е И, 27 ту2 тпЛаз ' (4.33) а из (4.31) и (4.32) следуют оценки у (х ) — у'(х*) у уЛа2 < ехр( — сп), сп е И, (4.34) ~Хсп Х*~2 2 С,уйа2 о < — ехр( — та), сн Е И.
(4.35) Из (4.33), (4.34) видно, что при выборе ~аь~ = а = Л = 1 можно ожидать наиболее быстрой слабой сходпжости используемого метода спуска, а в случае сильно выпуклой минимизируемой функции — — и наиболее быстрой сильной схосУвлсостн. Отметим, что при аь = 1 единичный вектор и, задающий ь направление спуска на й-й итерации, сонаправлен антиградиен- Ф вЂ” 1 ту то(х" с) в точке х" ~, т.е. иь = .
Такой выбор векто- (' 'И' ра ик на каждой итерации характерен для лсетпода еродиентпиоео спдсха (хотя его точнее надо было бы назвать методом 178 4. ЧИСЛЕННЫЕ МЕТОДЫ БЕЗУСЛОВНОЙ ЫИНИЫИЗАЦИИ антиградиентного спуска). Если при этом на каждой итерации Ля = Л = 1, то это означает, что в направлении антиградиснта проводят одномерную минимизацию функции 1(хь 1+ диь) по аргументу )1. Такой вариант метода называют метподом наискорейилеео спуска.
4.3. Метод градиентного спуска Пусть целевая функция 1(х) ограничена снизу и непрерывно дифференцируема в Ко. Предположим, что существует точка х"' Е К", в которой эта функция достигает локального минимума. Рассмотрим некоторые особенности применения метода ерадиентноео спуска для поиска этой точки. В этом методе элементы релаксационной последовательности )х~) удовлетворяют рекуррентному соотношению вида (4.
20) и,ь х =х~ ~+Ки~=х~ ~+Я, И 6 И,. (436) ~шЧ' где Я > 0 шаг спуска на к-й итерации, а направ,ление спуска задано единичным вектором и = ы /~ш~~, сонаправленным антиградиенту шл = — Егад)'(х~ ) в точке х~ 1. Тогда из (4.27) следует, что оь = 1 для всех к Е И. Если у(х) является выпуклой фуньцией и удовлетворяет условиям теоремы 4.4, то градиентный метод обладает слабой сходимостью, причем справедлива оценка р т) у( ~) ° У(~ ) ~(~*) П*~)-П*) ~ 2ЬП2 ь=! 2Ецз 2ЕВ' « , т,НИ, (4.37) Л,+Лз+.,.+Лт Л ' где Ь константа в условии (4.25), ц = е11ашХо диаметр ограниченного множества Хо = (х Е К": 11х) < 1 (х ) ), а 179 4.3. Метод градиентного спуска «(х-) -Пх ) / Л «1хо) — «1х*) л 2«) 14.38) 14.39) где з параллетпр сильной еьшйклоспли функции «1х).
Возникает естественный вопрос, при каких условиях сходится метод градиентного спуска в случае дифференцируемой невыпуклой функции «1х). Рассмотрим один из вариантов этого метода, когда в 14.36) Д = хала"~, где х= сопв1 > О, т.е, шаг спуска на каждой к-й итерации пропорционален длине вектора антиградиента в точке х~ ~. Таким образом., вместо 14.36) получим рекуррентное соотношение х~=х~ +хю~, х>0, ЙеИ.
14.40) Теорема 4.6. Пусть функция «1х) ограничена снизу и непрерывно дифференцируема в К", причем для любых х, у Е К" выполнено неравенство ~а 'с1«(х) — К с1«(иП < «-4х — Ы, 14.41) где Л > 0 некоторая константа. Тогда последовательность 1х~«, определяемая рекуррентным соотношением 14.40) с х Е е 10,2/А), является релаксационной. При этом справедлива оценка «1х~) ( «(хь 1) — х(1 — х — ) ~6гал1«(х~ ~) ~ 14.42) А 2 и ~буассо«(хь)~ — ь 0 при и — ь оо. Ль > Л > 0 — параметр в условии (4.21), которому подчинен на 1с-й итерации выбор шага спуска Д.
Если же «1х) является сально еыцйклой функцией и удовлетворяет условиям теоремы 4.5, то этот метод обладает сильной сходиллостьло. При этом для любого пв е И имеем 180 4. чйсд~нн~|~ лс~1 Оды Б~~~с~тонооЙ лтинило4~ 1ци14 Положив в (4.24) у = х" ' и р = жю~, с учетом (4.40), равенства ~ю"~ = (ю ', ю ) = — (8гас1Дх" ), ю") и свойства линейности скалярного произведения находим л.з-л."-')=~а-~л"-'~- '), ')~.= а 1 =- ~ т-'- )ь ~й~ '-'- ')-к~я ' з ')~.
о Оценим интеграл в правой части этого равенства, приняв во внимание неравенство Коши Буняковского и (4.41): -'~Не ~л ' '~- ") — к ~л ' '), 'Н~ < о 1 1 м1" из <Ь )х +тмю — х Йю ~Йт=мй~ю ~ тс1т= — )ю ) . 2 В итоге получим 1(хь) — 1(х~ ') < — м(1 — хй(2Яю~~~, что с учетом равенства ~ю"~Я = ~рас1Дхь ')~з равносильно (442). Представив (4.42) в виде Дх~ ~) — Дх~) х(1 — хЛ/2) и просуммировав по к от 1 до т,, запишем ~8гас11(х )( < ь=1 181 4.3. Метод градиентного спуска Отсюда в силу ограниченности снизу функции 1(х) следует, что при ьч — + оо сумма в левой части будет конечна, т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
