И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 12
Текст из файла (страница 12)
е. если функция ~, не вычислялась слева от точки х» ~), то найти точку х»,, й» Е [1: (Й вЂ” 1)[, х», ~ х» ь ближайшую к точке х» ~ с правой стороны, положить Ь, = х», и перейти к шагу Х1; если для всех 1 Е П: (й — 1)! выполняется неравенство х», ) ~: х, (т.
е. если функция )» не вычислялась справа от точки х» ~), найти точку х»„й, Е П ~ (й — 1)[, х», ~ х» о ближайшую к точке х» ~ с левой стороны, положить а, = х», и перейти к шагу Х П; если фУнкциЯ 1» вычнслЯлась слева и спРава от точки х» ь то найти точку х»„й, Е [1. (й — 1)), х», Ф х» ь ближайшую к х» ~ слева, и точку хм, й»Е И; (А — 1)), х», ~ х~ ь ближайшую к х» ~ справа, положить а, = х»„Ь, = х,, и перейти к шагу ХП[. Х1.
Найти интервал локализации [а„Ь,! точки минимума функцииг", (после вычисления функции /» вй — 1 точках хы хм ..., х» ~) по правилу а, =а,; ! Ь„= Ь, — —,([,(Ь,) — 6,) и перейти к шагу Х1Ч. Х!1. Найти интервал локализации [а„Ь,! точки минимума функции г»(после вычисления функции'г»вй — 1 точках х,, ха, ..., х» ~) бо по правилу 1 а, = а1 + — (/ь (а,) — /ь-1); ь, = ь, и перейти к шагу Х1Ч. Х111. Найти интервал локализации (а„ Ь,) точки минимума функции /ь (после вычисления функции /ь в й — 1 точках х„ х„ ... ..., хь 1) по правилу а, = а, + — (/ь(а1) — /ь 1); 7 1 ь, = ь, — — (/, (ь,) — /" 1) и перейти к шагу Х!Ч. Х1Ч.
Если й = й/ + 1, то прекратить вычисления (в атом случае точка минимума функции /ь принадлежит интервалу (а„ Ь,), длина которого не превышает гарантированного значения (Ьь— — аь)/Рн); иначе перейти к шагу ХЧ. ХЧ. Вычислить сь — — (х', — а,)/(Ь, — а„). ХЧ1. Вычислить 1 — (1 — с,) Рн я+1/Рн ь, ы если О < с„~ ('/,; 1 сьрн — гч-1/Рн — л+ы если /,<с„<1.
ХЧ11. Вычислить точку х„= а, + (Ь, — а,) 1„. ХЧ111. Вычислить значение /ь (хь), положить й = й + 1 и пе- рейти к шагу Ч. Теорема 1. Пусть выполня1отся предположения 1 и (а„ь,!— интервал локализации точки минимума функции /ь, вычисленный в й-й итерации (й = 1, ..., 11/). Тогда за оставшиеся й/ — й + 1 ите- раций алгоритм 1 прйводит к интервалу локализации точки мини- мума функции/„длина которого не превышает значения (Ь, — а,) 1с х зн 1+1, где шах ((1 — с„)/Рн — ь+ь с„/Рн — ь), О~=с,<'/,; и '+' гпах ((1 — с,)/Рн м с,/гн г;ь1), 1/,<с,<1, если внутри интервала локализации (а„Ь,) точки минимума вычис- ления функции /ь проводились; гн — ь.ь1 = 1/Рн — ь+1, если внутри интервала локализации (а1, Ь1) точки минимума вы- числения функции /ь не проводились.
Замечание 1. Если у = ьо, то алгоритм 1 дает оптимальный га- рантированный результат, равный (Ь,— а,)Гй+„т. е. такой же, 6! как и метод Фибоначчи. На практике учет конечности значения константы Липшица у в алгоритме 1 приводит к значительному выигрышу (по сравнению с методом Фибоначчи), который получается за счет специфического построения интервала локализации [а„Ь,) точки минимума на каждой итерации. Библиографические укоаоиия. Параграф написан на основании работ !386, 389!.
1.4. Оптимальный метод поиска экстремума выпуклых функций 3 а д а ч а 1. Найти ага ппп [а (х) для заданной функции «Е[ое»е) [а: 1!т;е- 1»т и заданного отрезка 1ао, Ьа). Предположение 1. Функция [а выпукла на интервале [а„Ь»1. Приведенный ниже алгоритм является оптимальным на классе выпуклых функций, т. е. дает наименьшее гарантированное значение длины интервала, содержащего минимум функции Г„после вычисления функции Га в заданном числе У точек.
В и-й итерации алгоритма по известным значениям функции [а в точках х„х„..., х», строится интервал локализации [х, хр! точки минимума функции [„ затем внутри интервала локализации [х, х+) находят точку х», в которой следует вычислить функцию [а. Алгоритм 1 Н а ч а л о. 1. Задать константу У вЂ” число вычислений функции [а. П. Найти числа Фибоначчи Ро, Р„..., Рн+ь определяемые соотношениями Р +~ = Р„[+ Р„, и = 1, 2, 1П. Положить й = 1. О с н о в и о й ц и к л.
1Ч. Если й = 1, то положить х = аа, хи —— Ьа и перейти к шагу ЧП; иначе перейти к шагу )!. Ч. Вычислить [;, = пт!и [а (х,). (1.2) 1<он» вЂ” 1 Ч1. Если значение [~ [ в (1.2) достигается в двух соседних точках х»„х»„й, Е Н: (й — 1)1, Йа Е [1: ()» — 1)1, таких, что х»,(х»„то положить х = х»„х„= х», и перейти к шагу ЧП; если значение [1 [ в (1.2) достигается в одной точке х»„й, Е ~ 11: (й — 1)1, то положить х» [ = х», и перейти к шагу Х; если значение [и-[ достигается в трех соседних точках х»о х»„х»„, Лт 6[1: (й — 1)1 йа 6[1: ()г — 1)1.
[га 611: ()г — 1)1 таких, что х», ( х»,( х»„то прекратить вычисления (в этом случае все точки отрезка [х»„х»,1 являются решением задачи !). (Шаги ЧП вЂ” 1Х соответствуют той ситуации, когда внутри интер- вала локализации [х, х~1 точки минимума не проводилось вычисление функции )о)- ЧП. Если Ф = Ф + 1, то прекратить вычисления (в этом случае точка минимума функции ~, принадлежит интервалу [х, х+1, длина которого не превышает гарантированного значения (Ь,— — а,)(Рх); иначе перейти к шагу ЧП[. ЧП1. Вычислить точку х следующего вычисления функции ~> х„= х + (х~. — х ) Рм а.ьдРх ььз 1Х. Вычислить ~з (х„), положить Ь = А + 1 и перейти к шагу 1Ч.
(Шаги Х вЂ” ХХ соответствуют той ситуации, когда внутри,интервала локализации [х, х ь) точки минимума существует точка х~ в которой на предыдущих итерациях проводилось ' вычисление функции Я. Х. Если справа от точки х~, существуют по крайней мере две точки, в которых функция ~, вычислялась на предыдущих итерациях, то вычислить точку 1д — ! !О (хм) х-ь — хм+ 1 ( ) 1 ( )(хь — хь), где хм, хь„й~ р И: (й — 1)1, йз р И: (й — 1)), ближайшие справа к х~ ~ точки, такие, что х~ ~ < хм ( хм, и перейти к шагу Х1П; иначе перейти к шагу Х1. Х1.
Если справа от точки х~ ~ существует только одна точка ха„й, Е И: (Й вЂ” 1)1, (хь ~ С хм), в которой функция ~, вычислялась на предыдущих итерацйях, то положить хь — — х~, и перейти к шагу ХП1; иначе перейти к шагу ХП. ХП. Если справа от точки х~ ~ не существует точек, в которых функция ~, вычислялась (т. е., если х, (хь и 1= 1, ..., й — 1), то положить х ь —— Ьо и перейти к шагу ХП1. ХП1. Если слева от точки х~ ~ существуют по крайней мере две точки, в которых функция ~, вычислялась на предыдущих итерациях, то вычислить 1,' , — 1о (х,,) х — = хм+ 1 („) 1 („' )(хь — ха,), хм где хм, хм, йз Е И: (й — 1)1, йг Е И: (й — 1)), ближайшие слева к х~ ~ точки, такие, что хь ~ » хм ) хм, и перейти к шагу ХЧ1; иначе перейти к шагу Х1Ч. Х1Ч.
Если слева от точки х~, существует только одна точка ха„йети И: (й — !)), (х~ ~ ) хм), в которой функция ~з вычислялась на предыдущих итерациях, то положить х = хь, и перейти к шагу ХЧ1; иначе перейти к шагу ХЧ. 53 ХЧ. Если слева от точки х«, не существует точек, а которых функция /а вычислялась (т. е., если х, ~ х, и ! 1, ..., Ф вЂ” !), то положить х = аа и перейти к шагу ХЧ1. ХЧ1. Если й = /Ч + 1, то прекратить вычисления (в этом случае точка минимума функции /з принадлежит интервалу [х, х+), книна которого не превышает гарантированного значения (Ье — аз)1Рн); иначе перейти к шагу ХЧ1!.
ХЧ!1. Вычислить с, = (х', — х )/(х~ — х ). 'ХЧ!11. Вычислить, 1 — (! — с«) Рн-«+~/Рн — «+з, если О ( с«( т/а; 1 с„рн ьь~/Рн «+з, если т/з(с«(1. Х1Х. Вычислить точку х«следующего вычисления функции /а х„=х +(х+ — х )1,. ХХ. Вычислить значение /е (х,), положить й = й + 1 и перейти к шагу Ч. Теорема1. Пусть выполняются предположения 1 и [х, х+!— интервал локализации точки минимума функции /„ вычисленный ей-й итерации (й = 1, ..., й/). Тогда за оставшиеся /Ч вЂ” й + 1 итераций алгоритм 1 приводит либо к интервалу, каждая то ига которого является решением задачи 1, либо к интервалу локализации точки минимума функции /„ длина которого не превьииает значения (х+ — х )зн «+и где шах((! — с«)/Рн «+и с«/Рн «), О(с«х/а; " «+' гпах [(! — с,)/Рн-ы с«/Рн — «4 ~), '/,(с«(1, если внутри интервала локализации [х, хч ! тоиси минимума вычисления функции /, проводились; зн «+1 = 1/Рн «я.ь если внутри интервала локализации [х, х+! точки минимулза вычисления функции /а не проводились.
Био«возрос«ические рхоззняя. Параграф написан на основании работ [887, 3891. В работах [9, 101 предлагаются оптимальные алгоритмы поиска минимума функций с ограниченной второй и третьей производной. В работе [4991 рассматривается алгоритм минимизации на заданном отрезке многозкстремальных функций, являюп«ихся суммой вогнутой и выпуклой функций (в этот класс входят, например, функции с ограниченной второй производной).
1.5. Методы тица Ньютона 3 ад а ч а О. Найти зги ппп /з (х) для заданной функции «аеьд /е: 11'-ь В' и заданного отрезка !ао, Ь,!. Алгоритм 2 Н а ч а л о. 1. Выбрать произвольное начальное прибли>кение ' Е [а., Ь,[; положить й = О. Основ ной ци кл. П. Вычислить 1о(х') — первую произвоДнУю фУнкции 1о в точке х'. П1. Если 1о(х") = О, то прекратить вычисления (в атом случае точка ха ЯвлЯетсЯ стационаРной точкой фУнкции 1о), иначе перейтн к шагу 1Ч. 1Ч. Вычислить следующее приближение ха+' = х"— 1 (х")(х" — хе >) (о(х ) — !о(х ) Ч.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
