И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 13
Текст из файла (страница 13)
Положить й = я + 1 и перейти к шагу П. Теорема 2. Если выполнены все условия теоремы 1, то последовательность (хе)е о, порожденная алгоритмом 2, сходится к стационарной точке х функции 1о со сверхлинейной скоростью ! ха+' — х ! 2!о (х) 1!гп а ~ [ха — х[о 1о (х) где т — решение уравнения (а= 1+ 1 (с = (1+ у'6)/2 м 1,618). Библиографические указании.
При иаписаиии параграфа использовались работы !425, 49!. 1.6 Методы касательных 3 ад а ч а О. Найти агд ш!и 1о (х) для заданной функции хо[а,л,) го. В'-ь В> и заданного отрезка [аа, Ьо[ 1. Случай лвфферевпвруемой фуввввв Предположение 1. (о) — функция 1о непрерывно дифференцируемая иа отрезке [ао, Ьо[„(!1) — функция 1о выпукла на отрезке [ае, Ь,[; (И) — [о (а,) ( О и (о (Ьо) ) О Алгоритм 1 Н а ч а л о. 1. Выбрать число о) Π— точность вычисления точки минимума; положить й = О.
П. Вычислить производные 1о (а,) и 1о (Ь,) функции [о в точках ае и Ь„ соответственно, Оси о в н о й ци к л. 111. Найти точку хе — корень уравнения [е (аа) + (о (ае) (х — а ) = [о (Ьа) + 1; (Ьа) (х — Ьа). 1Ч. Вычислить 1о (хе) Ч. Если ~о (х») = О, то положить х"= х" и прекратить вычисления; иначе перейти к шагу Ч1. Ч!. Если 1о(х») (О, то положить а»+г — — х», Ь»ч.г = Ь» и перейти к шагу ЧШ; иначе перейти к шагу ЧП. ЧП. Если [о(х') - О, то положить а»+г —— аю Ььг-г = х» и перейти к шагу ЧП1.
ЧП1. Если Ь»л г — аьгг ( е, то положить х* = (аьг.г+ Ь»ег)/2 и прекратить вычисления; иначе перейти к шагу 1Х. [Х. Положить й = й + 1 и перейти к шагу П1. Теорема 1. Если выполняются предположения 1, то для последовательности (х»)»=о, порожденной алгоритмом 1, справедливо !ип(о(х») = пип 1»(х). » о «Иена«! еча Если, кроме того, точка минимума хе единственная, то 1ип х» = х*. »-«« е о 2.
Скучав кедвфферевввруевоа фувкввк Предположение 2. (г) — функция 1о выпукла на отрезке (ае, Ьо); (»1) — (о (а, + 0) < О, го (Ьо — О) < 0 Алгоритм 2 Н а ч а л о. 1. Задать число е ) 0 — точность вычисления точки минимума функции 1»; положить Ь = О. П. Вычислить правостороннюю 1о (ао + 0) и левостороннюю 1„(Ь» — 0) производные функции 1» в точках а, и Ьо соответственно и положить уо = го(ао+ О) ([о= Го(Ь» О).
Ос н о в н о й ц и к л. П1. Найти точку х» — корень уравнения )о(а,) + У» (х — а,) = 1» (Ь») + Р» (х — Ь»). 1Ч. Вычислить правостороннюю 7о (х'+ 0) и левостороннюю 1о (х» — 0) пРоизводные фУнкции го в точке х». Ч. Если [о (х» + 0) [о (х» — 0) ( О, то положить х* = х» и прекратить вычисления; иначе выбрать любое число 6» из отрезка [го(х» — 0), го(хе + 0)1 и перейти к шагу Ч!. У1. Если 6»<0, то положить а»+г = х», у»+г = бю Ььгг = = Ь», ~»+г —— б» и перейти к шагу ЧП; иначе положить а».гг = = а», у»+г = у», Ь»+г = х", р»+г = б» и перейти к шагу ЧП. Ч11. Если Ь», г — а»ег ( е, то положить х"= (аьг г + Ь»+г)12 и прекратить вычисления; йначе перейти к шагу ЧШ. ЧП1.
Положить й = й + ! и перейти к шагу Ш. Теорема 2. Если выполняются предположения 2, пго для последовательности (х»)» о, порожденной алгоритмом 2, справедливы утверждения теоремы 1. Библиографические указания. Параграф написан на основании рабогы [!941. 57 1.7. Метод квадратичной аппроксимации 3 а д а ч а 1. Найти агд ппп !о (х) для заданной унимодальной «ел функции (о! В' -!- В!. Сущность метода квадратичной аппроксимации заключается в следующем. По трем точкам функция )о аппроксимируется квадратной параболой, после чего находится точка минимума этой параболы. На следующем этапе аппроксимации используются три соседние точки, между которыми находится точка минимума функцик (о.
Алгориизхо х Н а ч а л о. !. Выбрать произвольное начальное приближение хо ~ !зз, точность вычисления точки минимума е ) О и начальное смещение 6, ) О. П. Если го (хо — е) ~ !о (х') и !о (х'+ е) ) 1о (х'), то положить хо = хо и прекратить вычисления; иначе перейти к шагу П1. П1. Если го (хо) ( го (х' — е), то положить 6 = 6, и перейти к шагУ 1Ч; если Го (хо) ()о (х'+ е), то положить 6 = — 6, и пеРейти к шагу 1Ч. !Ч.
Положить й = О. Ч. Положить хо+' = хо + 6. Ч1. Если Го (хо+') ()о (х"), то положить 6 = 26, й =й + 1 н перейти к шагу 'Ч; иначе перейти к шагу ЧП. ЧП, Если го (хо+') ) го (х") и 6) О, то положить хз = х"-', хз = х", х, = х"+' и перейти к шагу Ч1П. Если Го (хо+') ) )о (хо) и 6 ( О, то положить хз = хо+', х, = хо, х, = х' ' и перейти к шагу ЧП1. Примечание: интервал [х„х,! содержит точку минимума х* функ- ПИИ ЧП1. Если х, — х, ( е, то положить х* = х,и прекратить вычисления; иначе перейти к шагу !Х. 1Х. Найти точку хо по формуле 6 Оо (х!) — !о (хо)) 4 (/о (х!) — 2!о (хз)+ /о (хз)) ' Основной цикл. Х. Если х,(х„то: 1) пРи !о (хо) !о (хз) и !о (х\) ) !о (хз) пОлОжить хз хо~ хз = х„х, = хз и перейти к шагу Х1; 2) при 1о (хо) = !«о (хз) и !«о (х!) ( 1о (хз) положить хз = хи хз = х„х, = хо и перейти к шагу Х1; 6) при )о (хо) ( )о (х,) положить х, = х„х, = х„х, = х, и перейти к шагу Х1; 4) при )о (х,) ) !о (хз) положить х, = хо, х, = х„х, = х, и перейти к шагу Х1.
Если х,) х,, то: 1) пря 1о (хо) = 1о (хз) и 1о (х,) ( ~о (х,) положить х, = х„х, = = х„хз = х, й перейти к шагу Х1; 2) ПРи [о (хо) [о (хо) и [о (хв) ) 1о (хв) положить хв хв хо = х„х, = х, и перейти к шагу Х1; 3) при 1о (х,) < [о (х,) положить х, = х„х,= х„ха= х, и перейти к шагу Х1; 4) при )о (х,) ) ~о (х,) положить х, = х„х, х„х,= хо и перейти к шагу Х1. Х1. Если х,— х,«е, то положить х* х, и прекратить вычисления; иначе перейти к шагу ХП. ХП.
Вычислить точку хо по формуле (кз — кз) 1 (к,) + (кз — ко) [о (к,) + (к~~ — кз) 1, (кв) х,=— (кв кв) [о»кв) + (кв ко) [о (кв) + (кв кв) 1» (ко) и перейти к шагу Х (точка х, является точкой минимума квадратичной функции, проведенной через три точки х„х„х,). Замечание 1. Алгоритм, определяемый шагами 1 — 1Х, называют алгоритмом Дэвиса, Свенна, Кэмпи (ДСК).
Алгоритм, определяемый шагами Х вЂ” Х!1, соответствует алгоритму Пауэлла. Поэтому алгоритм 1 в [378] называется комбинированным алгоритмом Дэвиса, Свенна, Кэмпи — Пауэлла. Теорема 1. Если функция 1о унимодальна, то за конечное число шагов алгоритм 1 приводит в точку х*, лежащую в з-окрестности точки ха (здесь х* решение задачи 1). Библиографические указания. Прв написании параграфа использовались рабаты [378, 425!. 1.8.
Метод отыскания абсолютного мнннмума функций, удовлетворяющих условню Лнпшнца 3 а д а ч а 1. Найти агя ппп го (х) для заданной функции к«[а„бо) 1о: 11' -ь 11' и заданного отрезка [а„Ь,!. Предполоясение 1. Функция 1о непрерывна на [а„Ьо] и удовлетворяет условию Липшица с константой у, т. е. [1, (х') — ~, (х") ] < у [ х' — х" ], ч х', х" Е [ао, Ь ]. На й-й итерации приводимого здесь алгоритма строится ломаная ор» (х, х', ..., х'), ограничивающая 1о (х) снизу, и вычисляются два числа 1» и 1", которые являются, соответственно, верхней и нижней границами абсолютного минимума функции 1, на отрезке [ао, Ь,], такие, чго 1" '<)' < [п 1о(х)<~' <[-, Ь 2 3 кя(а„оа причем, для каждого а ) О существует номер й такой, что 1» — [» <в.
Число 1» является ординатой наиболее низкой из «верхних» вершин ломаной ~р», а 1 — ординатой наиболее низкой из «нижних» вершин ломаной»р». Абсциссы точек ломаной ~р» (х, х', ..., х»), лежащие ниже прямой у = 1», образуют множество, содержащее множество решений Х, задачи 1. Начальное приближение в алгоритме пооизвольно. По существу вычисления на каждой итерации сводятся лишь к решению двух линейных уравнений и выбору минимальных величин из конечного набора. Алгоритм 1 Н а ч а л о. 1. Выбрать произвольное начальное приближение х' Е [а„Ь«) (обычно выбирается х» = (а»+ Ь»)/2). И.
Выбрать величину е ) О (точность вычисления минимума функции 1„по функционалу). И1. Положить я = 1. Основной цикл. 1У. Вычислить 1,(х»). У. Определить функцию и» (х, х»), (х Е [а„Ь»[) по правилу а»(х, х») = 10(х») — у[х — х»[. (1. 3) Ч1. Определить функцию <р» (х, х', ..., х»), (х Е [а„Ь»[) по правилу ф, = (х, х', ..., х») = гпах д,(х, х') »=ь...,» и найти множество Я» «нижних» вершин ломаной <р» (х, х', ..., х') на отрезке [а„Ь»[: если А=1, то Я» = [(а„1»(х') — у(х' — а,)), (Ь», 1,(х') — у(Ь,— х'))); если а ) 1, то ф, = (Д» ~'~,[(х», ~р» 1(х", х', ..., х" — ')))) [) 6„ где 6» определяется: если х» = а„ то 6» состоит из одной точки — точки пересечения прямых у = 1„(х»*) + у (х — х»~), (1.4) р = 1»(х») 7(х — х ), (здесь х»* — абсцисса ближайшей справа к (х", 1, (х»)) «верхней» вершины ломаной <р» (х, х', ..., х»)); если х» = Ь„то 6» состоит из одной точки — точки пересече- ния прямых у = 1»(х *) — у (х — х *), (1.6) у=1»(х)+7(х х) (здесь х» — абсцисса ближайшей слева к (х", 1, (х»)) «верхней» вер- шины ломаной ~р» (х, х', ..., х»)); если х» ~ а, и х» Ф Ь«, то 6» состоит из двух точек — точки пе- ресечения прямых (1.4) и точки пересечения прямых (1,5).
ЧИ. Вычислить 60 А!11. Найти точку х»+', являющуюся точкой абсолютного минимума функции гр» (х, х', ..., х') на отрезке [аа, Ье! гр,(х"+', х', ..., х») = ппп чз»(х, х', ..., х»), [[.б! а,<ккь» и положить 1 — = чг» (х +, х > "» х ). 1Х. Если выполняется условие то прекратить вычисления (в этом случае абсциссы точек ломаной гр» (х, х', ..., х»), лежащие ниже прямой у = Д~, образуют множество Х„заведомо содержащее решения хэ задачи 1, и, кроме того, выполняется !' ~ ~Да (хе) (1" ); иначе положить й = й -[- 1 и перейти к шагу 1Ч. Теорема 1. Пусть выполняетсп предположение 1, тогда алгоршпм 1 порождает последовательность чисел 1+, й = 1, 2, ...
и 1», й = = 1, 2, ... такие, что ~«( ш!и Де(х)<~~~, й = 1, 2, «а[а»,«.1 и, кроле того, при а = О имеют место предельные соотношения 1!ш[» =!пп!» = ппп 1е(х) = 1»(хе). «-» «с[а».ь»! Библио«до[рике«иве укшаниа. Прн написании параграфа использовались работы 1281, 107!. В работе 1202! для специального класса многоэкстремальных функций, не нвлиющихси вогнутыми, строитси оптимальный алгоритм по критерию, равному максимальной возможной величине ошибки в определении экстремума минимизируемой функции. 1.9. Метод кусочно-кубической аппроксимации 3 а д а ч а 1. Найти агд ппп [о (х) для заданной функции ке[а„»,1 1ь. Вз-»- В' и заданного отрезка [ае Ье! Предположение 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
