И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 17
Текст из файла (страница 17)
«яи Теорема 2'. Если выполнены все условйя теоремы 2 и функция /ь является сильновыпуклой с параметром сильной выпуклости ч ) О, т е. / (Ох + (1 — 0) у) ( О/ (х) + (1 — 0) / (у) — 0 (1 — 0) ч ( х — у (', )/х, уЕВ", 0~~0(1, то для бесконечной последовательности (х»)» ь, порожденной алгоритмом 2, справедливы оценки скорости сходимости /»(х») /о ((%(хь) /о) ехр( — чЛя/2а), я = 1, 2, ...; '1 х' — х* 1» ( (2/ч) (/«(х') — Д) ехр ( — тЛ/г/2а), /« = 1, 2.
Замечание 2. Реализация алгоритма 2 на ЭВМ не приводит к ис- комому решению из-за наличия ошибок вычислений. Поэтому ал- горитм 2 используют до тех пор, пока выполняется неравенство У» (х') — /ь (х"+'))/( Ч/ь (х») Г > г, (х.х) где е ) О выбранная на данном этапе точность вычислений. Если же неравенство (2.2) нарушается, то следует либо повы- сить точность вычислений, либо перейти к другому, более эффектив- ному в данном случае методу. Такая ситуация обычно возникает в окрестности точки минимума х* или при «попадании в овраг». Замечание 2'.
Неравенство (2.1) эквивалентно неравенству /о(х ) — /о(х +') > Л»(/о( )»и»). Отсюда видно, что при малых Х» точность вычислений ()» (как минимума функции 1, по направлейию — Ч1, (х»)) может быть невысокой. Однако с уменьшением )»» скорость сходимости уменьшается и поэтому важно удачно выбирать числа Х» для каждого конкретного случая.
В. О»воевой аарвавт традвевтвото метода Алгоритм 3 Н а ч а л о. 1. Выбрать произвольное начальное приближение хо е В", произвольную константу р ) О, произвольный множитель 9 е Р/о, 1), произвольную константу е) О (е =ы»1»); положить я = О. Ос н о в но й ц и к л. П. Вычислить 71» (х"). П1. Если 71» (х») = О, то положить хо= х» и прекратить вычисления; иначе перейти к шагу 1Ч. 1Ч. Положить а = р. Ч. Вычислить точку х = х» — аЧ1» (х'). Ч1. Если выполняется неравенство 1о (х) — 1о (х') ~ (еа (Ч1» (х') Ч1»(х»))~ то положить р„= а и перейти к шагу ЧП; иначе положить а = ар и перейти к шагу Ч.
ЧП. Вычислить следующее приближение Р»т1»(» ). ЧШ. Положить й й + 1 и перейти к шагу П. Теорема 3. Если выполнено предположение 1 и (1) — функция 1» ограничена снизу 1о(х)~до) — со* ЧхсВ ' (И) — градиент функции 1о удовлетворяет условшо Липшица Мо(х) — Ч1»(у))~а»1х — у)* Чх УЕВ" а»(оо, то для бесконечной последовательности (х»)» о, порожденной алгоритмом 3, справедливо 171»(х»)1-о О при й-+ оо. Теорема 3'. Если функция 1, дважды непрерывно дифференцируема в В" и ее матрица вторых производных Ф„1» (х) удовлетворяет неравенствам при любых х, у с й", то для бесконечной последовательности (хе)т, е, порожденной алгоритмом 8, справедливы соотношения ха -е хе при /г-»- оо; /е(~") †.
/е(х ) при й-+ «~. где х* — единственная точка минимума функции /е, и следующие оценки скорости сходимости ~)х» — хе!!<61цм2, 6»(оо; /е(х") — /е(х') <(/е( ) — /е(х*)) «/е, где «7 = 1 — 2е (1 — е) у, (1 + у,/у,)/ум причем минимальное зна- чение «/ = 1 — (у,/27,)(1 + у,/у,) достигается при а = '/,. Теорема 8". Если выполнены все условия теоремы 8 и существует такое число бе) О, что ~ Ч/е (х) !! ~ бе (/е (х) — /о) Ч х Е Л ° где/о = !и! /е(х), кяяе то для последовательности (хе)е о, порожденной алгоритмом 8, справедлива оценка /е(хл) /о ~~% (/е(хе) /о) где О < «1,< 1.
а. Градвевтвый метод е поетопввым шаговым мвошвтелем Предположения 4. (!) — функция /е непрерывно дифференцируема; (!!) — градиент функции /е удовлетворяет условию Липшица с известной константой а ( оо. Алгоритм 4 Н а ч а л о. 1. Выбрать произвольное начальное приближение хе Е В" и произвольную константу е Е (О, 1) (целесообразно выбирать а = '/,); положить /е = О. П. Выбрать произвольное значение шагового множителя р из полуоткрытого интервала (О, (1 — г)/а).
О с н о в н о й ц и к л. !П. Вычислить Ч/е (хе). 1Ч. Если Ч/е(хе) = О, то положить хе х" и прекратить вы. числения; иначе перейти к шагу Ч. Ч. Вычислить следующее приближение х" »' = х — рЧ/ (х"). Ч!. Положить я = /е + 1 и перейти к шагу 1П. Теорема 4. Если выполнены предположения 4 и функция /е ограничена снизу, то для бесконечной последовательности (хе) ь" о, порожденной алгоригпмом 4, справедливо ) Ч/е (хк) ) -~ О при /«в 77 Предположения 4'. (1) — функция /о дважды непрерывно диффе- енцируема; (11) — матрица вторых производных Ч„„/о (х) функции~ , удовлетворяет неравенствам У,ЦУЦт~~(Ч~„~о(х)У, У)(УоЦУЦт, ус~У,)О, при любых х, у Е В", причем константы у, и ут известны.
Алгоритм 4' Шаги 1, !1!, 1Ч, Ч, Ч1 такие же, как и в алгоритме 4. Шаг 11 алгоритма 4 следует заменить шагом П', т. е. выбрать произволь- ное значение шагового множителя р из полуоткрытого интервала (О, 2 (1 — з)/ут). Теорема 4'. Если выполнены предположения 4', то для бесконеч- ной последовшпельности (хо) о" о, порожденной алгоритмом 4', справедливы предельные соотношения 11ш /о (» ) = /о (х ) огде хо — единственная точка минимума функции /о, и следующие оценки скорости сходимости: Цх' — хоЦ~~бтуьа, б,<оо; Уо (х ) — Уо (х') ~ ~(Ро (х') — Ро(х*)) ц" где д = ! — 2з (1 — е) у, (1 — у,/у,)/у„причем минимальное значение д = 1 — (у„/2у,) (1 + у,/у,) достигается при з = т/о. А югоритм 4" Шаги 1, Ш, 1Ч, Ч, Ч1 такие, как и в алгоритме 4.
Шаг 11 алгоритма 4 следует заменить шагом 11", т. е. выбрать произвольное значение шагового множителя р из открытого интервала (О, 2/у,). Теорема 4". Если выполнены предположения 4', то для бесконечной последовательности (хо)о ~, порожденной алгоритмом 4", справедлива оценка скорости сходимости Цхо хоЦе цоЦ»о хеЦ где д = шах ( Ц 1 — ру, Ц, Ц 1 — ру, Ц), причем минимальное значение у = (у — 71)/(уо + у ) достигаегпся при р = 2/(ус+ ут). Если же в алгоритме 4" выбрать шаговый множитель р 2/(у,+ + у,), то, кроме того, справедливо неравенство Ро(х ~) Ро(х )<~((уо ут)/(ус+ ут)) (Ро(хо) Ро(хо)).
5. Вариант градиентного метода с натрицей усиорения снодниости Предположения 5. (1) — функция /о непрерывно дифференцируема; (И) — задана матрица ускорения сходимости Н (х) размера п Х и, элементами которой являются непрерывные функции от х. Алгоритм 5 Н а ч а л о. 1. Выбрать произвольное начальное приближение »» б Н" и произвольные константы е Е (О, 1), Д Е (О, 1), р > О (рекомендуется выбрать е = '/„() ~ (»/„4/ ), р =* !); положить И О.
Основной цикл, П. Вычислить вектор движения И(х') к следующему приближению х»+' по формуле И (х») = — Н (х ) ч/»(х»). П1. Если И (х») = О, то положить х'= х» и прекратить вычисления; иначе перейти к шагу 1Ч. 1Ч. Положить р = р. Ч. Вычислить значение 0()», х ) =/»(х»+ рй(х»)) — /9(х») — ре(ч/9(х ), И(х )).
Ч1. Если 8(р, х") ( О, то положить р» = р и перейти к шагу ЧП; иначе положить (» = р(» и перейти к шагу Ч. ЧП. Вычислить следующее приближение х»+' = х» + р„И (х"). ЧП1. Положить И = А + 1 и перейти к шагу П. Теорема 5. Если выполнены предположения 5 и условия: (1)— функция /» дважды непрерывно дифференцируема; (И) — матрица вторых производных Ч,',/ь (х) функции /» удовлетворяет неравенствам у,)у1»<(Ч„'/,(х)у, у)<у,((у(р, у,~у >О, при любых х, у Р К"; (111) — Н (х) — симметричная матрица, удовлетворяющая неравенствам у»(у(('((Н(х)у, у) у,(у(~, у,~у»>О, при любых х, у Е Н", то для бесконечной последовательности (х»)» ь, порожденной алгоритмом 5, справедливы оценки скорости сходимости ()х» — х*(< б,д»п, б» < оо; Ро (х') — Ро (х*) ~ <Уо (х') — Р» (х')) ц'> где д = 1 — 2е (! — е) у»у» (1 + у,/у»)/(у»у4); х~ — единственная точка минимума функции /», причем минимальное значение о = !— — у»у» (1 + у,/у )/(2у»у») достигается при е = Ч».
Теорема 5'. Если выполнены предположения 5 и условии' (1)— — Н (х) — положительно-определенная матрица; (11) — начальная точка х» такова, что множество Х»= (х(/» (х) (/» (х»)~ х с Л ) ограничено, то каждая предельная точка х' бесконечной последовательности (х»)» о, порожденной алгоритмом 5, удовлетворяет условию Ч/„(х') = О.
Замечание 5. Выбор матрицы Н (х) существенно влияет на скорость сходимости алгоритма 5 (примером этого служат методы типа Ньютона и методы с растяжением пространства). 79 б. Модифииироввииый трвдиеитиыи метод, ие требующий вычиевеиив ироивводиыв Этот метод применяется в тех случаях, когда вычисление градиента !/„1» требует значительно больших затрат, чем вычисление значений минимизируемой функции 1„илн когда вычисление градиента вообще невозможно (например, когда функция 1, задана таблнчно, или вычисляется с помощью экспериментов). Алгоритм 6 Н а ч а л о.
1. Выбрать начальное приближениехе Р х1", удовлетворяющее условиям теоремы 6, и константы ео ) О, Л') О, [) ) ) О, Л с (О, '/,) (РекомендУетсЯ выбиРать ео Р [10, !О 1, Л'6 Р [10., 10 1, [! Е [6, 10[, Л = 0,4). 11. Положить й = О, е =- ео. Основ ной ц и кл. П1. Вычислить вектор Ь", !-я компонента Ь; которого /»! = — —,(1о(х»+ ее') — 1»(х»)), 1= !. 2, ", л, где г! — /-й орт. 1Ъ'.
Вычислить й» =1»(хе+ ер/» ) 1»(х ). !/. Если Л»(0, то, используя алгоритм 6А, вычислить такое число р, что , !» (1,(х»+ р/») — 1,(х") ( ~ и перейти к шагу !/1; иначе положить е = е/2 и перейти к шагу П1. '»/1. Если 1, (х + рй») — 1, (х") ( — Л'е, то перейти к шагу Ч11; иначе положить е = е/2 и перейти к шагу Ш. '»/11. Вычислить следующее приближение х»+' = х» + рй». Л/П1, Положить й = й + 1 и перейти к шагу Ш.
Алгоритм 6А (алгоритм вычисления шагового множителя р для алгоритма 6) 1. Выбрать константу р ) 0 (рекомендуется выбирать р = !). П. Определить функции ф»(и) = 1.("+ ий') — 1,( ')— ч»(и) = 1»(х»+ и" ) 1»(х») ео соха» П1. Положить !» = р. 1Ч.
Вычислить значение ф„ (р). 80 Ч Если ф (р) = О, то положить р = р и прекратить вычисления; если»р (р) ~ О, то положить р = р + р и перейти к шагу 1Ч; если»р» (1») ) О, то перейти к шагу Ч1. Ч1. Вычислить значение»ь» (р). Ч11. Если ~р» (1») ч ' О, то положить р = р и прекратить вычисления; иначе поцожить а» = р — р, Ь, = р и перейти к шагу Ч1П. ЧП1.