И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 11
Текст из файла (страница 11)
Практическая эффективность таких алгоритмов зависит от удачного выбора множеств О„так как этим определяется и объем вычислений при разрешении системы )я (х„х» и) = 0 и скорость приближения х» к х*. С этой целью часто выбйрают множества 6~»~~~»(~~»( ", е )й ((! ~,( ")>Е(х') — е ) () () (/(~ и~ — л~(х )(>Е(х ) — ) с небольшими значениями е» ) 0 и строят аппроксимации обратной функции (~~,) ' (или обратного гессиана) и развязывающих операторов в некотором выбранном параметрическом классе функций » 1 вида 7 (р», Г7», х, и, ~я, (х, и)).
Параметры р» оценивают и уточняют по вычисленным значениям х', х', ..., х». В случае аппроксимации обратного гессиана удобно использовать матричное тождество с А, + КЕ С ) — ' ('А»+ А»СМРА» — А,СМ Р А) (, — МРА, М (0.47) где А, = А~ ' (Š— К (Е + ЕА, 'К) ' (.А~ ') = (А, + КЕ) ', М =(А,— РА,С) ', которое получаем как следствие утверждения 17 для линейных 7. С помощью (0.47) получаем эффективный А,-алгоритм для вы- числения (псевдо)обратной матрицы А ' к матрице А = (ан, ( = ):г =Е,С~О, г~+' = г»+ г," (60 — (а~», г7))7(а~», г~У~), где (омз) 1» =- агн ш(п ф (1'), или 1» = ага (~р (1) ( С], р(Ц=~~г+'~ ру,) =1(а'», з;»Ц Утверждение 20.
Если на некотором шаге й ( п задача (0.48) не разрешима, то Я является С-псевдообратной к А, иначе Л" = =А',апри и = агд ((Е + (А' — Е) Х») о = (А' — Е) г», а,' 7= ац, о;а! = 0) имеем А 'Ь = Е~Ь вЂ” Я~о. Ошибки округлений в 2" можно существенно уменьшить с помощью А,-алгоритма: Во=2 Ьо=Ь В~~~ =В +(Š— В,АфВ„, х"+'=х" +( — В,.А)~'х~, обеспечивающего при (, ~ ( и быструю сходимость В„-~- А ', хл-~ А Ь согласно следующим утверждениям [271.
Утверждение 21. Если Ь„+1 = Ь„+ В'"Ь„, Ь = Ь, ВА = — С, Ах = Ь вЂ” Сх, то Ах = Ь,ч ~ — В'"+' — 'Сх. Следствие. Если В0= 2", С = Š— В,А, Ь,= Ь, Вь+1 = В» + СаЯВю х~+~ = хл + Салхь, то Вь~1 =А '+С"+'А ', х'+'=А 'Ь(-С'"+'А 'Ь. Подбором ю', ~ в А,-алгоритме уменьшается влияние ошибококруглений. Часть 1 МЕТОДЫ ОДНОМЕРНОЙ И БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ Глава 1 МЕТОДЫ ОДНОМЕРНОЙ ОПТИМИЗАЦИИ 1.1. Методы Фибоиаччи 3 а д а ч а О. Найти агу пнп Го (х) для заданной функции /о ~ кЛ!аг»к! Е' — Е' н заданного отрезка 1а„Ь,). 11редположение О.
Функция го такова, что на отрезке (ао, Ьо) точка ее локального минимума хо является точкой абсолютного минимума ~, на отрезке 1а„Ь,). Методы Фнбоначчн являются оптимальными (для класса функцнй г„удовлетворяющнх предположению О) по колнчеству вычнслений минимизиРУемой фУнкции го пРн заданной точности вычнслення х*.
1. Ооиоваой алгоритм Алгориполо 1 Н а ч а л о. 1. Выбрать число е ) Π— точность вычисления точки минимума функции !о на отрезке (а„Ь,); положить Р, = = Ро — — 1. 11. Положить ! = 1. 1П. Вычислить число Р;.~т — — Рьь~ + Рн ! 1Ч. Если Р;+~ ( — (Ь, — ао) ( Рг~т, то положить и = 1 н перейти к шагу Ч; иначе положить ! = ! + 1 н перейти к шагу 1П.
Ч. Вычислить точки У» = ао+ (Ьо ао)' Ем+2 г, = а, + Ьо — ум Ч1. Если Го (у,) (Го (г,), то положить а, = ао, Ь, = г, н перейти к шагу Ч11; иначе положить а,= У„Ь,= Ьо н перейти к шагу Ч11. Ч11. Положнть й = 1. 0 с нов н ой цн к л. Ч111. Если )о (у,) (1о (г»), то вычнслить точку у»+~ — — а„+ ܄— у„вычнслнть значение )о (у»к ~) я перейти к шагу 1Х; иначе положить у»+~ = гм 1о (ум-~) = = 1» (г„) н перейти к шагу Х. 1Х. Положить г»~.~ = У,; 1о (г».о~) = 1» (У») и пеРейти к шагУ Х1. Х. Вычислить точку г»< ~ — — а„+ Ь» — г„, вычислить значение (о (г»+~) н перейти к шагу Х1. Х1.
Если !о (у,+,) ( Го (го„), то положить ао+, а, Ьоь~ = г~, ~ и перейти к шагу ХИ; иначе положить а1,, * уо ь1, Ьоь~ = Ь, и перейти к шагу ХП. ХИ, Если Ь ( 1п — 1, то положить й й + ! я перейти к шагу ЧШ; иначе положить х'= (а + Ь )/2 н прекратить вычисления. Теорелоа1. Если выполнено предположение О, то для произвольного е ) 0 точка х*, порожденная алгоритмом 1, удовлетворяет неравенству ~ х" — х' ~ ( е. Эамечание!. Недостатком алгоритма 1 является то, что погрешности в вычислениях точек у„г„могут етоль быстро накапливаться, что ожидаемая точность решения будет существенно отличаться от реальной.
Следующая модификация метода Фибоначчи менее чув. ствительна к погрешностям вычислений. В. Модификация метода Фябояаччп Алгоритм 2. Н а ч а л о. Шаги 1 — 1Ч такие, как в алгоритме 1. Ч. Вычислить точки г„ у, = а, + — (Ь, — а,); ум+2 ~ -Ь1 г1 — — ао + — (Ьо — ао). ~т+2 Ч1. Если !о (у,) ( )о (г1), то положить а1= ао, Ь1= г, и перейти к шагу ЧИ; иначе йоложить а,= у„Ь,= Ьо и перейти к шагу ЧИ.
ЧИ. Положить й = 1. О с н о в н о й ц и к л. Ч1И. Если !о (уо) ( !о (го), то вычислить точку 1~ — о уо+1 = ао+ (Ьо ао) ~я+2 вычислить значение 1о (уо.ь1) и перейти к шагу 1Х; иначе положить уоь1 = гм 1о (уо+1) = го (г„) и перейти к шагу Х. 1Х. Положить уо+1 = г„го (уо+1) !о (г„) и перейти к шагу Х1. ! т — А+! Х. Вычислить точку го+~ = ао+ „(Ь,— ао), вычислить т+1 значение (о (го+1) и перейти к шагу Х1. Х1. Если !о (уо+~) ( !о (го.ь~), то положить ао.ь а„ Ьо+1 = Ь, и перейти к шагу ХП; иначе положить ао+1 — — уо+1, Ьо+1 = Ь„и перейти к шагу ХП. ХИ. Если й т — 1, то положить й = й + 1 и перейти к шагу ЧИ1; иначе положить х*= (а + Ь )/2 и прекратить вычисле. ния.
Точка х' удовлетворяет неравенству ~ х* — х* ~ ( е, если выполнено предположение О. Библиографические ркозокия. При написании параграфа использовались раь боты !194, 358, 378!. 1.2. Метод золотого сечения 3 а д а ч а !. Найти ага ппп 1о (х) для заданной функции ко[а„о ! [о: В' -ь В' и заданного отрезка (ао, Ьо1 Лредположение 1. Функция 1о такова, что на отрезке !ао, Ьо! точка ее локального минимума хо является точкой абсолютного минимУма [о на отРезке (ао, Ьо). Алгоритм 1 Н а ч а л о. 1. Вычислить константу а = (3 — )/б)/2 (а гя ы 0,38!9). 11.
Вычислить точки у, = а, + а (Ь, — ао); г~ = по+ Ьо — уз И ЗначениЯ [о (Уз), [о (гз). П1. Если 1о (у,) ( 1о (г,), то положить а,= ао, Ь,= г, и перейти к шагу 1Ч; иначе положить а,= У„Ь,= Ьо и перейти к шагу !Ч. !Ч. Положить Ь = 1. Основной цикл. Ч. Если )'о (уа) ()о (го), то вычислить Уа+~ = аь+ Ьо — Уа Й (уа»») и перейти к шагу Ч1; иначе полож"ть Уо»» = гм )о (уа»») = 1о (г„) и перейти к шагу ЧП.
ЧЕ Положить го+[ = Ум 1о (гь»») = [о (Уа) и перейти к шагу ЧП1. ЧП. Вычислить го»» = аь + ܄— го, [о (го» ~) и перейти к шагу ЧП1. ЧШ. Если 1о (уо» [) < ), (го»»), то положить аь» ~ = а„, Ьао» = га»» и пеРейти к шагУ 1Х; иначе положить аа» ~ —— = Уз+и Ьь»» = Ь, и перейти к шагу 1Х. 1Х. Вычислить х' = (ао»» + Ь», ~)12. Х. Положить й = Ь + 1 и перейти к шагу Ч. Теорема 1. Если выполнено предположение 1, то последовательность (хо)а+н порожденная алгоритмом 1, такова, что !пи[о(ха) = 1о(хо); !!и ! х" — хо! = О. о-~м о Замечание 1. Длина отрезка (а„, Ь„!о „построенного по методу золотого сечения, на !7 % больше длйноы отрезка (ао,Ьо) ь„о, построенного по методу Фибоначчи. Однако метод золотого сечения обладает тем достоинством, что на каждой его итерации приходится делать меньше вычислений.
Замечание 1'. Иногда на практике комбинируют оба метода: первые шаги делают по методу золотого сечения, а когда оптимум достаточно близок, вычисляют число и и переходят к методу Фибоиаччи. Библиографические укизоиил. При написании параграфа использовались ра. боты [!94, 358, 378!. 1.3.
Оптимальный метод поиска экстремума унимодальных функций, удовлетворяющих условию Липшица го ! = ш!и 1о(х;). !«<о-! ЧП. Если значение 1о ! в (!.1) достигается в двух соседних точках хо„хо„й, Е [1: (й — 1)), Ьа ~ [1: (й — 1)), таких, что хо, ( (1.1) 49 3 а д а ч а 1. Найти агй ппп )о (х) для заданной функции «а!«„оо) 1о: Н' — ь В' и заданного отрезка 1ао, Ь,!. Предположение 1. (о) — функция 1о определена, непрерывна и удовлетворяет условию Липшица с константой у на интервале [а„ Ьо); (11) — фУнкциЯ 1о Унимодальна, т. е.
имеет на отРезке [а„Ьо! единственную точку минимума, слева от которой )о строго убывает, а справа строго возрастает с ростом х. Приведенный ниже алгоритм является оптимальным для класса функций, удовлетворяющих предположениям 1, т. е. дает наименьшее гарантированное значение длины интервала, содержащего минимум функции 1„ после вычисления ее в заданном числе )Ч точек. В й-й итерации алгоритма в начале находят (используя кон- стантУ У и значениЯ фУнкции 1о в точках х„ хм ..., х~ ~) интеРвал локализации [а„ Ь,! точки минимума функции 1о, затем внутри интервала [а„ Ь,! — точку х„, в которой следует вычислить функцию 1о. При вычислении интервала локализации учитывается конечность константы Липшица у, что в практических задачах приводит к значительному выигрышу (по сравнению, например, с методом Фибоначчи, который является оптимальным на классе унимодальных функций при у = оо). Алгоритм 1 Н а ч а л о.
1. Задать константу )Ч вЂ” число вычислений функции )«. 11. Найти числа Фибоначчи Ро, Рп ..., Рн+), определяемые соотношениями Ро = Рт = 1, Р«ч-~ = Р«! + Р«, и = 1 2, П1. Положить а,= а„Ь,= Ьо. 1Ч. Положить й = 1. О с н о в н о й ц и к л. Ч. Если й = 1, то перейти к шагу ЧП1; иначе перейти к шагу Ч1. Ч1. Вычислить ( х»„то положить а,= х»„Ь,= х», и перейти к шагу ЧП1; если значение [» ~ в (1.1) достигается в одной точке х»„й, Р Н ' (Й вЂ” !)[, то положить х» ~ = х», и перейти к шагу Х. (Последующие шаги ЧП1 — 1Х алгоритма соответствуют той ситуации, когда внутри интервала [а„ Ь,! не проводились вычисления функции 1,).
Ч1П. Если й = Л + 1, то прекратить вычисления (в этом случае точка минимума функции 1, принадлежит интервалу [а„ Ь,[, длина которого не превышает гарантированного значения (Ь,— — а,)!Р», иначе перейти к шагу 1Х. 1Х. Вычислить точку х» следующего вычисления функции 1» х„= а, + (Ь, — а,) Ги — ».»~4Рх-»+» (или х» = а, + (Ь, — а,) Гх»1Ех»+»); вычислить г» (х»); положить Й = й + 1 и перейти к шагу Ч.
(Шаги Х вЂ” ХЧ111 алгоритма соответствуют той ситуации, когда внутри интервала локализации [а,, Ь,! точки минимума существует точка х» ь в которой на предыдущих итерациях проводилось вычисление функции ~»). Х. Если функция г, не вычислялась слева и справа от точки х» ~ (такой случай имеет место при А = 2), то положить а, = а„ Ь,= Ь» и перейти к шагу Х1Ч; если для всех [Е [1: (й — 1)! выполняется неравенство х» ~ ( х, (т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
