3 часть (1081356), страница 49
Текст из файла (страница 49)
Метод градиентного спуска. Пусть у'(х) — выпуклал дифферснцирусмал во всем пространстве б„функция и требуется найти ес точку минимума х*. Выбрав произвольное начальное приближенис х~о~ 6 5„, построим последовательность х~ " ~ = хйй — агу'(хйц), й = О, 1, ..., (1) где величины ог ) О (парамстрические шаги) выбираются достаточно малыми для того, чтобы выполннлось условие у(х~ь+0) < у(х~"~), л = О, 1, (5) В качестве условия окончания вычислений обычно использустсп близость к нулю градиента у'(х~"~), т.
с. выполнение неравенств ду(х~" ~) <г, г=1,2,...,п, Ох, или йу (х~ ~)ц = ~ < е (6) (ОУ(хбй)) г дх; (г — заданнос достаточно малое число), после чего налагают х' = х~ь . Г Г(хйб). Если при некотором й условие (5) нарушается, то шаг оь в (4) уменьшают (дробят) в заданное число раз до выполнения неравенства (5) и продолжают вычисления. 3 2. Безусловная минимизацин функций многих псрсаюнных 345 Пример 4. Минимизировать в Еа функцию у(х) = >(хм хт) = хт1 + 2хт + е"+" методом градиентного спуска, завершив вычисления при ~ОУ(х>а>)/дх,~ < 0,05, 1 = 1, .2. ~ Выбрав начальное приблньчснпс х = (О, 0) н но — — 1, построим по<о> следоватсльность (4), записывая результаты вычислений в таблице 2.1.
Таблица 2.1 Итак, х* а ( — 0,301, — 0,163), У* 0,772. с Для квадратичной функцш1 (3) формула (4) принимает вид х>ь+'> = х>а> — оа(Ях>а> + г), и = О, 1, . (7) В задачах 17.117-17.120 совершить один шаг градиентного спуска (4) из точки х(о> с шагом ао и сравнить значениа у(х(~>) и )(хО>): 17.117. 1(х) = хт + 2хт ~+ е*'+*', х(о> = (1, 1), а) гто = 0,1; 6) сто = 0,265; в) гта = О 5 17.118.
~(х) = 2х>~+х~т+х>хг+х>+ха, хОО = (О, 0), а) сто = 0,1; б) ао = 0,5; в) гто = 1 17.119. Дх) = х, + хз + хз + х>хз + хзхз, х( > = (О, 1, О), а) сто = 0,1; б) то = 0,638; в) сто = 10. 17.120. у" (х) = е* + (х> +ха+ха)т, х(о> = (1, 1, 1), а) сто = 0,1; 6) оа = 0,21268; в) сто = 1. Гл. 17. Методы оптимизации 346 17.121. Показать, что если функция у(х) дифференцируема в точке х(~> и Г'(х(ь>) ~ О, то при достаточно малом шаге аь из (4) будет выполнено условие (5).
Метод наискоребшеео спуска отличаетсп от метода градиентного спуска способола определения всличины аы которая находитсл из условия Фь(аь) = пцп Фл(а), где Фь(а) = ([х>ь> — ар'(х>ь>)!. (8) в>о Такой выбор аь обеспечивает максимально возмоа~нос уменьшение функции у(х) вдоль направления се антиградиента — 1'(х>ь>) в точке х>~>.
Таким образом, для определения аь на каждом шаге метода наискорейшего спуска решается одномерная задача минимизации (8), для чего можно использовать методы, рассмотренные в 3 1. Пример 5. Решить пример 4 методом наискорейшего спуска. Шаг 1. Положим х>о> = (О, О), тогда г'(х>о>) = (1; 1), Фо(а) = = >(Π— а 1, 0 — а 1) = Зат + е з . Для нахождения точки минимума функции Фо(а) используем метод перебора: т. е. а = ао = 0,22, откуда хи> = (О, О) — 0,22 (1, 1) = ( — 0,22, — 0,22). Шаг 2. У'(хи>) = (0,204, — 0236), Ф~(а) = ( — 0,22 — 0,204а)т + + ( — 0,22+ 0,23ба)з + е ол4 лоозза >>1инимизиргем Ф,(а) т.
е, а = а~ — — 0,32, откуда х1 > = ( — 0,22, — 0,22) — 0,32 (0,204, — 0,236) = = ( — 0,2853, — 0,1445), Ш а г 3. У'(хии) = (8,007, 7,268) 10 ~, Фз(а) = ( — 0,2853 — 8,007 х х 10 ~) +( — 0 1445 — 7268.10 ~ а) +е олза ~л згл'" . 51инил~изируем Ф2(а): т.е.
а = а = 0,24, х>з> = ( — 03045, — 0,1619), Г'(х<з>) = (1821 — 2,051) 10 '., позтому требуемая точность достигнута и х* и х~з> = = ( — 0,305, — 0,162), >* >(х>з>) 0 772 в З 2. Бедзтловная минимизация функций многих переменных 347 Если «(х) — квадратичнал функция (3), то величина оь моьдет быть найдена в явном виде (уды удтй) ать =- ', где Г' = ах~в~ + г. (б21дь] удь~) (9) Таким образом, длв квадратичной функции метод наискорейшего спуска состоит в построении последовательности (х~ь~) по формулам (7), (9) . 17.122*. Показать, что градиенты Г'(х1ь)) и Г'(х1"ч О) в последо- вательных точках итерационного процесса метода наискорейшего спуска ортогональны, т.е.
(Г'(х1ь)), Г'(х(в+1))) = О, й = О, 1, ... 17.123. «(х) = х~1 + х~з + х1+ хз, х1~1 = (О, 0). 17.124. «(х) = хз + х1хз + хзз, х1о~ = (1, 1). 17.125. «(х) = хз + 2х~з + е" +~', х1о1 = (1, 1). 17.126. «(х) = 2хз + х~~+ х~хз+ х~ + хе, х~~) = (О, 0). 17.127. «(х) = х", + х~~+ ха~+ х1хз + хзхз: х(о1 = (О, 1, 0). 17.128. «(х) = е ~ + (х1+ хз + хз)~, х~~1 = (1, 1, 1).
В задачах 17.129-17,144 минимизировать квадратичные функ- ции методом наискорейшего спуска, заканчивая вычисления при д«(х00) <001,1=1,2, ..., и: дх, 17.129. «(х) = 7х1~ + 2х~хз + 5х~ ~+ х1 — 10хз. 17.130. «(х) = Зх~1 — Зх~хз + 4хзз — 2х1 + хз. 17.131. «(х) = х1 + 4х1хз + 17хз + 5хз. 17.132. «(х) = бхз1 — 4х1хз + 5х~~ — х1 — хз.
17.133. «(х) = 4х1, + 4х1хз + бхз~ — 17хы 17.134. «(х) = 2х~~ — 2х1хг + Зх~~ + х1 — Зхз. 17.135. «(х) = 10х~1 + Зх1хз + хз + 10хз, 17.136. «(х) = хз1 — 2х1хз + бхз + х1 — хз. 17.137. «(х) = 4хз1 + 5хз~ + 7хз з— 2х1хз + х1тз + х1 — хз + хз. 17.138. «(х) = Зхз+4х~з+5хз+2х~хз — х1хз — 2хзхз+х~ — Зхз. 17.139.
«(х) = хз1+5хз~+8хзз — х|хз+х1хз-хзхз+5х1 — Зхз+хз. 17.140. «(х) =- 2х1 + 4хг+ 8х~+2х1хз — х1хз+ 2хвхз+ 6х1 — 7хз. 348 Гл. 17. Методы оптимизации 17.141. ) (х) = 7х~)+4хг+бхз~ — Зхлхг+х)хз — хгхз+х( — ха+ха, 17.142. )'(х) = 5хг) + Зхгг + 2хгз + 2х) хг+ х) хз + хгхз + 5х ( + хз, 17.143. гс(~) = Зхг) + 5~~а +4хгг+ 2х)хз — х)хз — хгхз + 7х) + х). 17.144. 1(х) = 4х)+4х~+х~ — х)хг+2х)хз+тгхз — х(+хг хз, Метод сопряженных гродиентае состоит в построении последовательных приближений х(") к точке минимума функции г(х) следующим образом: х(ьею = х(") — олр(~), Й = О, 1, ..., х( ) Е Ен, (10) где х(о) — заранее выбранное начальное приблигаенис, шаг он выбира- ется аналогично (8): Фь(ол) = ш!пФь(о), где Фл(о) = Г(х(л) — ор(ь)), (11) а>о а направление спуска — р(л) определяется по формуле р(л) = Г (х( )) + Ар л л), 1 = 1, 2, ..., р( ) = У (х( )), где (12) Таким образом, метод сопряженных градиентов отличается от методе наискорейшего спуска только выборам направления уменьшения функции на каждом шаге (-р(л) вместо — Г'(х(л) )).
Отметим, что р(л) из (12) определяется не только антиградиентом — Г'(х(л)), но и направлением спуска — р(л ') на предыдущем шаге. Это позволяет более полно, чсл~ в градиентных методах, рассмотренных выше, учитывать особенности функции )(х) при построении последовательных приближений (10) к сс точке минимума. 1лритсрием достижения заданной точности вычислений в методе сопряженных градиентов обычно служат неравенства (6). Часто для уменьшения влияния накапливающихся погрешностей вычислений через каждые%итерацийй (10) полагаютД„гг = О,т = О, 1, ..., т.с.
производят обновление метода (Х вЂ” параметр алгоритма). Для минимизации выпуклой квадратичной функции в Ея требуется не более и итераций метода сопряженных направлений. Пример 6. Методом сопряженных градиентов найти точку минимума х" функции ('(х) = хл + 2х~з + хлхг — 7х~ — 7хг. 3 2.
Безусловная минимизация функций многих переменных 349 а ~(х) — квадратичная функции, заданная в Ем Поэтому точка х' будет найдена после двух шагов метода сопряа.енных градиентов. Ш а г 1. Выбрав начальное приближение х~е~ = (О, 0), по формулам (9Н11) находим рбб = Г'(хкп) = (2х1 + ха — 7, х1 + 4хт — 7)~и> = ( — 7, — 7), Фе(а) = 98(2ае — о). Из условия Фо(ае) = О минимума Фе(а) пол1 ~им 1 1 /7 71 ао — — —. Отсюда хО~ = (О, О) — -( — 7, — 7) = ~-, -). 4 ' 4 ' ~4'4) / 7 71 Ш а г 2.
Г'(хрд ) = ~ — —, — ~, откуда с учетом (12) имеем 4' 4 А = —, Р~О = ~ — —, -) + — ( — 7, — 7) = ~ — —, — у). Позтому 16' 1 4' 4) 16 ' 1, 16' 16/ Ф1(о) = — ~-а~ — 4а — 392( и а1 =- —. Окончательно хйй 32 12 ( 7 — — — = (3, 1) = х'. 17.145. Показать, что при обновлении метода сопряженных градиентов на каждом шаге (т. с. если Д,. = О, 1 = 1, 2, ... ) он перс- ходит в метод наискорейшего спуска.
17.146. Минимизировать одну из квадратичных функций задач 17.129-17.136, совершив две итерации метода сопряженных градиентов из произвольного начального приближения х~с) Е Ез. 17.147. Минимизировать одну из квадратичных функций задач 17.137--17.144 с помощью трех итераций метода сопряженных градиентов, используя произвольное начальное приближение х(0) е Ез, 17.148. Минимизировать функцию Дх) = х~~ + х~ ~+ х~~ + х42— — 2хт+ 2хз — 2ха с помощью четыРех итеРаций метода сопРЯженных градиентов, используя произвольное начальное приближение хОО Е Е4. В задачах 17.149 — 17.174 минимизировать функцию ~(х) метод.ПЫ )) дом градиентов, заканчивая вычисления при < 10 з, дх; 1 = 1, 2, ..., ги 17.149. ДХ) = ХЗ + 2ХЗ2 + Е*1 Гяа — Х1 + 2жт, 1 1 пльо. нс =,й' гз+т ~ —,, — —,;.
17,1Ы. ~(х) = х1~ + 2х~~ + х1~х~~ + 2х1 + хт, 350 Гл. 17. Методы оптимизации 17.152. гг(х) = хг) + Зхг г+ соя (х) + хг). 17!53. 7) ) = 577 7 2, 5.. '5 .*'" " †.ч — ... 17.154. у (х) = х) + 5хг + е~!+""г. !7.155. !) ) = !,' 5 *:,' 5,/2 8-Н 77--Ч,' — 2 5 3: . 1Т.156. )'(х) = 2хг) + Зхгг — 2з)п + хг. 2 1Т.157. ~(х) = 1п(1+ Зхг+ 5хгг+ соя(х~ — хг)). 17.158. у (х) = хг + се!+*2 + 4х! + Зтг, 17.153. 7) ) =..:,-,-2,„„-3,7! ~ ',~5., г+1 г 17.160.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
