И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 14
Текст из файла (страница 14)
Функция 7' удовлетворяет условию Липшица на отрезке [а„Ь,!. В методе кусочно-кубической аппроксимации в качестве модели функции 1а (х) используется кусочно-кубическая кривая <р» (х), проходящая через точки (х[, [а (х[)), 1 Р [О: й[»), и моделирующая поведение фУнкции 1е (х) полиномами тРетьей степени на отДельных участках отрезка [а„Ь,1. Отыскание приближенного значения глобального минимума функции 7» (х) сводится к вычислению минимумов кубических парабол на отдельных интервалах отрезка [а„Ь,! (т. е.
к решению соответствующих квадратных уравнений). 61 Алгоритм 1 Н а ч а л о. 1. Выбрать константу е ) О, характеризующую относительную ошибку аппроксимации функции г» (х) кусочно- кубической кривой. П. Положить М, = 5. П1. Положить й О. 1Ч'. Вычислить точки х', ! е [О: М» — П по формулам =,+ о„'а 1, (с[О!М, 1] и значение функции 1, в этих точках. Основной цикл. !Ч. Положить]=0.
Ч. Провести кубическую параболу ф»ь~ (х) через четыре точки (х~, 1, (х/)), (х~+', ~» (х/+')), (х~+' ~»(х!+')) (х/+', ~ (х»+')). Н]. Если ! = О, то иа отрезке [х», х'] аппроксимирующую кусочно-кубическую кривую у» (х) определить по правилу ~р»(х) = ф,(х), хй[х», х'] и перейти к шагу 1Х; иначе перейти к шагу НП. ЧП. Если ! + 3 ( М» — 1, то на отрезке [х»+', х!+~! аппроксимирующую кусочно-кубическую кривую ~р» (х) определить по правилу ср»(х) = фн.~ (х), х~ [хг+', хг+'] и перейти к шагу !Х; иначе перейти к шагу ЧП1.
НП!. Если ! + 3 = М» — 1, то на отрезке [х"» з, х~» '] аппроксимирующую кусочно-кубическую кривую ~р» (х) определить по правилу ~р»(х) = фсь~(х), хе[х», х"» '] и перейти к шагу Х; иначе перейти к шагу Х; 1Х. Положить ! = ! + 1 и перейти к шагу Ч. Х. Положить М»~.~ = 2М» — 1. Х1. Вычислить точки х'=а,+ ' " 1, !с[О:М»~.~ — !]. »+!— ХП. Если выполняется неравенство шах [(!» (х') — ~р» (х'))/!»(х') [( е, ока<и»+,-~ то перейти к шагу ХП1; иначе положить й = й + 1 и перейти и шагу !Ч. ХП1. Положить ! = О. Х1Ч. Если ! = О, то вычислить точку минимума х' кубической параболы ф, (х) на отрезке [х», х»] и перейти к шагу ХНП; иначе перейти к шагу ХН.
ХЧ. Если ] + 3 < М» — 1, то вычислить точку минимума х[ы кубической параболы ф,+~ (х) на отрезке [х[+', х[+з] и пе. рейги к шагу ХЧП; иначе перейти к шагу ХЧ1. ХЧ]. Вычислить точку минимума хо» ' кубической параболы ч]зм (х) на отрезке [х~» ', х"» ') и перейти к шагу ХЧ]П. ХЧ11. Положить ] = ] + 1 и перейти к шагу ХЧ.
ХЧ111. Найти точку ха (приближенное решение), принадлежащую множеству точек (хз, ] с [О: ]Ч».ь~ — 1]; х[, ] Е [1: У вЂ” 3]], такую, что [о(х) =-п[]пЦо(х[), ]с[О:М»чл — !)' 1о(хв) [с[1:]Ч» 3]). Библиографические указания. Параграф написан па основании работ 137З, 17]. В работе 1472] предложен метод, использующий квадратичную и кубическую интерполкдию и не требующий вычисления производных минимизируемой функпии. 1.10.
Методьх глобального поиска Задач а О. Найти ага ппп 7о(х) для заданной функции «е[ев Ов! ]о: Л' -» 1]' и заданного отрезка [а„Ь,] вещественной оси 1]'. Приводимые ниже алгоритмы применяют для вычисления абсолютного минимУма многоэкстРемальной фУнкции 7о на отРезке [а., Ьо). 1. Алгоритм глобального поиска Алгоритм 1 Н а ч ало. 1. Выбрать произвольную константу сс) 1 П. Положить х'= а„х'= Ь,. Ш. Положить й = 1.
О с н о в н о й ц и к л. ]Ч. Разместить точки последовательности [х')[~ о в порядке возрастания их значений и обозначить новую последовательность через [х'), о, т. е. ао = х' < х' < ° ° < х" = Ь,. Ч. Найти максимальное абсолютное значение относительной первой разности б, = и[ах [(7 (х') — [о(х[ '))/(х' — х' ') [. в<в<» Ч]. Если Ỡ— — О, то положить ]]» = ! и перейти к шагу ЧП; иначе положить р» = аб» н перейти к шагу ЧП. 'Ч11.
Положить 1 = 1. Ч11! Вычислить у (<) — характеристику интервала (х' — ', х<) < — > у(<) = Вл (х' — х< ') + 1'(" 1: ' " )! — 2 (~ (х') + 1 (х' ')). В (х< — х< '! 1Х. Если < ( й, то положить < = < + 1 и перейти к шагу Ч1П; иначе перейти к шагу Х. Х. Найти наименьшее значение 1» Е (1: й), при котором выполняется равенство у(<„) = шах у(1). >«<л Х1. Вычислить следующее приближение хл ы (х<» + х<» <)12 (>е (х<») ~о (х<» <))12(<» ХП. Положить й = й + 1 и перейти к шагу 1Ч. Теорема 1.
Пусть функция <о (х) удовлетворяет на (а„Ьо! условию Липшица с константой т ( оо (1о(х') — ~о(х")((у(х' — х"), Чх', х" Яа„Ьо!. Тогда: (!) — если функция 1» (х) имеет на отрезке (а„Ь,! конечное число локальных экстремумов, то любая предельная >почка х последовательности (х")»=о, порожденной алгоритмом 1, локально- оптимальна; (ее) — если наряду с предельной точкой х сущгствует другая предельная точка х последовательности (х»)» о, пю <е (х) = = 1» (х); (!!!) — если х — предельная точка последовательности (х") =-о, то 1о (х») ~ 1» (х), й = О, 1, ...; (1о) — если на некоторой итерации алгоритма 1 справедливо неравенство ()») 2у, то множество предельных точек последовательности (х») >,=о совпадает с множеством точек абсолютного минимУма фУнкЦии 1» на отРезке ! а„Ь,!.
Теорема 1'. Пусть для наперед выбранной константы е ) О (в — точность вычисления абсолютного минимума) при помощи алгоритма 1 построена последовательность точек х', х', ..., х'<'>, где lг (в) — наименьший индекс Ь, при котором выполняется неравенство х<»(е) — х "< > '(г. Тогда: (е) — если в (й (е) + !)-й итерации выполняется неравенство р»<е> )~ ">'(2!л + 1)1(!л — !), х< — х где р, = ш!п; о<= (<)х — х«) г, 1~ «й(в)), то <вт <о(х)~ )ппп <о(х<), хс[х' ', х'), <еоы, о«<л<е> т. е.
точка х* абсолютного минимума не может принадлежать интервалу, длина которого превышает заданную точность е; (И)— если а) У)ь>(')'>> — 1), то 1п(го(х'), го(х и) ш>п го(х>), ок>иг>г> т. е. оценка ппп >о (х>) минимального значения функции го достигаем>име> ется на одном из концов интервала, длина которого не превыи>ает точности е; (!!1) — для любого положительного б существует столь большое значение когффициента а, чпо точки х, хг, ..., хг!'> образуют (е + Ь)-сеть в интервале (ао, (>о).
Замечание !. Значение константы а должно быть достаточно большим, чтобы удовлетворялось неравенство ()ь) 2у, которое является достаточным условием сходимости алгоритма !. Но, с другой стороны, с ростом а возрастает (приближаясь при а -~ оо к количеству узлов сетки метода перебора) число вычислений функции (о. В случае, когда известна константа Липшица у, выбор значения а не вызывает затруднений. В случае, если известны лишь грубые априорные верхние оценки константы Липшица, можно воспользоваться описанным ниже алгоритмом.
2. Рвидомнэироввниый алгоритм глобвльного подоив Алгоритм 2 Н а ч а л о. 1. Выбрать нижнюю а, и верхнюю ад оценки параметра а. П вЂ” Х. Шаги П вЂ” Х такие, как в алгоритме 1, с тем лишь отличием, что при вычислении ()г на шаге Ч1 вместо константы а следует взять кон:танту а,. Х1. Вычислить о! = рг(х'г — х'г ') — (До(х>г)+ ~,(х'г ')). ХИ. Положить />= >ю у>= У (!г) Х1И. Если 6„= О, то положить рг = 1 и перейти к шагу Х1Ч; иначе положить р> = а,б„и перейти к шагу Х1Ч. Х1Ч.
Положить ! = 1. ХЧ. Вычислить у(!) =~г(х — х ) + г — — 2К>(х) Ро(х ))' (>, (л> — г' ) ХЧ!. Если ! .с' й, то положить ! = ! + 1 и перейти к шагу ХЧ; иначе перейти к шагу ХЧП. ,ХЧИ. Найти наименьшее значение индекса >в с (1: й), при ко- тором выполняется равенство у (>г) = !пах у (!).
!«<г ХЧП1 Вычислить >г >;-! уг — рг (' — х ) — (>о(х ) + >о(х )) Х!Х. Положить 1,= /а, у,= у (!а). ХХ. Если 1,= !„то вычислить р = а,/(а,+ ссо) и перейти к шагу ХХ1; иначе вычйслить р = (ч, + ча — уа)/(2о, + 2та — у, — уо) н перейти к шагу ХХ1. ХХ1. Однократно реализовать случайный механизм с двумя исходами 1 и 2, соответственно, имеющими вероятности р,= р и Рв= 1 — Р ХХ П.
Если случайный механизм дал исход 1, то положить )! = = ра, 1 = !, и перейти к шагу ХХП1; иначе положить б )!», / = !, и перейти к шагу ХХП1. ХХП1. Вычислить следующее приближение х'+' (х/+ х' ')/2 — (/о (х') — /о (х/ '))/(26). ХХП/. Положить й = й + 1 и перейти к шагу 1Ч. Библиографиооскиа укониин.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
