И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 60
Текст из файла (страница 60)
Пусть /Ч = (О, 1, 2, ...). Будем называть функцию 1: Ь/-«.й/ функцией прерывания, если для каждого 1Е/Ч найдется такое число р р /Ч, что 1 (й) > 1 при всех й ) р. Алгорип«м 4 На ч ало. 1, Вычислить начальное приближение хо РХ и положить й = О. П. Выбрать функции прерывания 1, ( ), 1« (.). Основной цикл. П1. Положить х=ха, 1=1,(й). 1Ч.
Решить задачу линейного программирования (5.46) — (5.49) и получить и+ 1-мерный вектор (Ь, (х), Ь (х)). Ч. Если Ьо (х) = О, то положить х»+' = х' и прекратить вычиеления; иначе перейти к шагу Ч1. Ч1. Положить 8 (р) = А (х + р/«(х), х) и использовать для вычисления )» алгоритм 4' — модификацию алгоритма поиска минимума одномерной функции по методу золотого сечения. ЧП.
Если /о(х+ ~й(х)) (/е(х), то положить х+' = х+ + )»/» (х), Й = Й + 1 и перейти к шагу Ш; иначе положить х"~' = х", 1=1,(й), й=й+4 и перейти к шагу Ч1. Алгории«м 4' (модификация алгоритма поиска по методу золотого сечения) 1. Выбрать р) О, вычислить дроби Фибоначчи Р, = (3 — )l 5)/2, Р» = 9"5 — 1)/2. П. Вычислить 8 (0), 8 (р). П1.
Если 8(р) ~- 8(0), то положитьа = О, Ьо ри перейти к шагу ЧП1; иначе перейти к шагу 1Ч. 1Ч. Положить 1 = 0 и ро = О. Ч. Положить )и+~ = )»~ + р. Ч1. Вычислить 8 (~ц+1). ЧП. Если 8 (1»,) и 8 (р ), то положить ао = («» — и Ье ° = )и+~ и перейти к шагу ЧП1; йначе положить 1 = 1+ 1 и перейти к шагу Ч. Примечание. Теперь минимизирующая точка лежит в (а„Ь,). Ч111. Положить 1 = О. 3Г9 1Х. Положить о1 — — а1 + Р, (Ь1 — а1), св1 —— а1 + Ра (Ь1 — а ).
Х. Если О (о1) ( О (ш1), то положить а1чг = ан Ь;+1 = иг1 и пеРейти кшагУ Х1; иначе положить ан ~ = он Ь»~ь~ = Ь1 и пеРейти к шагу Х!. Х1. Если 1(1, то положить 1 ! + 1 и перейти к шагу !Хг иначе положить [» = (а1+ Ь;)/2 и прекратить вычисления. Теорема 4. Пусть выполнены предположения О и пусть функции 1; ( ), ! = О, 1, ..., т — выпуклы. Тогда последовательность х', х»,... ..., построенная алгоритмом б, либо конечна и ее последний элемент х»~' = х» удсвлетворяеп условию й, (х') = О, либо бесконечна и тогда каждая ее предельная точка хе удовлетворяет условию йе (х') = О. Библиографические укоэииил. Пункты 1, 2 написаны на ссноааннн рабат [285, 496, 4971, пункты 3, 4 — на сснонаннн работы [285!.
6Л». Методы чебышевсвих центров 3 а д а ч а О. Найти агу шах уе (х) для заданной функции 6» 1е: В" -э В' и заданного выпУклого множества Х (х((а', х)~аь 1=1, ..., т, »~В"). Предположение О. Функция Ге — вогнутая. 1. Метод чебышеасннх центроа В методе чебышевских центров каждое последующее приближение х»+ находят решением специальной задачи линейного программирования. Алгоритм 1 Н а ч а л о. 1. Выбрать произвольное начальное приближение х' Е Х. П. Положить й = 1.
О с н о в и о й ц и к л. П1. Вычислить обобщенный градиент Ч('е (хе) и положить а"+» = Ч[е(х»), а +1 = (71е(х"), х"). 1Ч. Вычислить точку х»~' ~ Х, удовлетворяющую условию гпах ппп ((а', х) — а,) = ппп ((а', х'+') — а,). гб» ы+«гиы+» ы+1<г<е+» Ч. Положить Ь = й + 1 и перейти к шагу 1П. Творе»»а 1.
Если выполняегпся предположение О и функция-. ((7 1е (х) (( ограничена на Х, то последовательность (х»)» ь порожденная алгоритмом 1, такова, что каждая предельная точка ее монотонной подпоследовательности (х'»)», относшпельно функции )е (х) является решением задачи О. 320 2. Модифицированный метод чебышевеиих иентров В модифицированном методе чебышевских центров на каждой итерации производится выбрасывание лишних ограничений, при этом на каждой итерации требуется решать задачу максимизации суммы кусочно линейной и квадратичной функций.
Алгоритла 2 Н а ч а ло. 1. Выбрать произвольное начальное приближение х' с Х. 11. Положить 9, = (т + !). П1. Положить й = 1. О с н о в н о й ц и к л. [Ч. Вычислить обобщенный градиент Ч/о (х ) и положить а"+" = Ч/ (х»), а, » = (Ч/е(х»), х»). Ч. Вычислить точку х»~~ ~ Х, удовлетворяющую условию 1 1 шах ш[п (а', х) — я, — — =(х, х)) = ех !ЕО» ! 2 р«» ппп /(а', х'+') — и, — — = (х"+', х»+')) . Ч1. Положить т» = ш! и /(а', х"+') — а, — — — (х"+', х»+')) . 2 р«» Ч11.
Найти минимальное подмножество б» множества [с», т. е. такое, что 1 1 шах ппп/(а', х) — а, — — =(х, х)) = т»1 «ех !6о» т 2 у'» 1 1 !пах ппп /(а', х) — а,— — =(х, х)))т», У/сб», «ЯХ гев»!!и ! 2 у'» Ч!11. Положить Яь+! = Я» [) (т+ й+ 1). 1Х. Положить й = й + ! и перейти к шагу [Ч. Теорелш 2. Если выполняется предположение О и функция (( Ч /е (х) (( ограничена на Х, то последовательность (х»)» !, по.
рожденная алгоритмом 2, такова, что ее монотонная подпоследовательность (х~»)» ! относительно функции Да (х) бесконечна и каждая предельная точка х* является решением задачи О. Кроме того, О«/,(х*) — /,(х') = О(!7Уг,). Биб«иогрофиееские у«озолин. При написании параграфа использовались работы [303, 309!.
Дополнительные сведения о методах чебышевсиих центров можно найти в работах [307, 46!. 321 11 зза - 5.10. Методы типа Ньютона 1. Метод твоа Ыьютова с регулвроввоа волга 3 а д а ч а 1. Найти агд ш)п 1» (х) для заданной функции »ох 1, «В"-» В' и заданного выпуклого компактного множества Х с= с В". Предположение 1. Функция 1,— дважды непрерывно дифференцируема на выпуклом компактном множестве Х. Алгориоом 1 Н а ч а л о. 1. Задать начальное приближение хо Е Х. П; Выбрать константы г Е (О, 1), р Е (О, 1) (рекомендуется г = Ч„р = 0,8).
П1. Положить й = О. Основной цикл. 1Ч. Положить х=х». Ч. Вычислить матрицу вторых производных Ч,',к1,(х) и гра. диент Ч1, (х). Ч1. Вычислить точку у», обеспечивающую минимум квадратичной функции «р»(у) на множестве Х, где ф» (у) й (Ч1» (х), у — х) + 2 (Чкк1» (х) (у — х), у — х). (5.52) Еоли ф»(у») О, то прекратить вычисления (в атом случае у" — решение аадачи 1); иначе перейти к шагу ЧП. ЧП.
Положить й' у» — х. Ч111. Положить р» 1. 1Х. Еоли выполняетоя неравенство 1о(х+ р»Ю — 1о(х) < гр»ф» (у"), (6;53) то перейти к шагу Х1; иначе перейти к шагу Х. Х. Положить р, = рр» и перейти к шагу 1Х. Х1. Положить х»+' = х + р»Л»,й й + 1 и перейти кшагу 1Ч, Теорема 1. Если минимизируемая функция 1, выпукла и дважды непрерывно дифференцируема на выпуклом компактном множестве Х, то для бесконечной последовательности (х»)» о, порожден- ной алгоритмом 1, выполняются условия: а) (1о(х»))~, монотонно убывает) б) 1пп1,(х') ппп1,(х).
» *ах Еоли, кроме того, а )У1»<(Ч„»1»(х)У, У)<со,~)У/~, а,)0, хЕХ УсВ", (564) то последовательность (х»)» о сходится к решению задачи 1 со сверхлинейной скоростью, т. е. )х«+» х )( т Хо ° . ° )ч+ь (6Л6) где 1,т,< оо, )л+~< 1 при любом 1~ О, Х,-» 0 при 1-» оо. 322 Теорема 1'. Если выполняется условие !б.б4) и матрица Ч 1» (х) на выпуклом компактном множестве Х удовлетворяет условию Липшица с константой у, т.
е. )Ч'„«1»(х) — Ч 1»(у)1(7(х — у~, Чх, убХ, у(оо, то бескон ная последовательность (х»)». е, порожденная алгориптмом 1, сходится к решению хе задачи 1 с квадратичной скоростью, т. е. 1хьм — хе,'((ттр), т»(оо, 1(оо, р,(1. Приводимый ниже алгоритм является принципиальной схемой для алгоритма 1. Алгоритм 1' 1 — ЧП. Шаги 1 — Ч11 такие, как и в алгоритме 1. Чш. Вычислить число р,~ [О, 1), удовлетворяющее условию 1»(х+ р„й») = ш(п Ге(х+ рй'). еа!ал! 1Х. Положить х'+' = х + р„й», й = й + 1 и перейти к шагу ГЧ.
Теорема 1". Если выполняется условие !'б.б4) и множество Х— выпуклый наклав, то бесконечнаяпоследовательность (х»)» е, порожденная алгоритмом 1', сходится к решению задачи 1 со сверхлинейной скоростью, т. е. имеет место оценка (б.бб), причем р» -» 1 при й -» со. В. Метод тапа Ньютава прв валвчвв ее»пуп»еввя 3 а д а ч а 2. Найти аги пйп ге (х) для заданной функции «ЯХ 1»: В" — » Л' и заданного множества Х. Предположения 2. (1) — множество Х вЂ” замкнутое и выпуклое; (Й) — функция !е (х) дважды непрерывно дифференцируема на множестве Х.
На й-й итерации алгоритма 2 функция 1» (х) — 1» (х') в точке х» аппроксимяруется квадратичным функционалом )»(х) = — (А,(х — х'), х — х»)+(й", х — х"), (зла) ! где А» — приближение для Ч' Ге (х»); Ь» — приближение для Ч1» (х'); в качестве х'+' выбирается точка, для которой прибли- с женно выполняется условие минимума 1» (х) на множестве Х для всех хЕ Х. Алгоритм 2 Н а ч а л о. 1. Выбрать произвольное начальное приближение х'Е Х. !!* 1А» — Ч»»/» (х») ) ( сд; 3й~ Ч/» (х Н!(с !1~ — х + Ц (о1)— (ой)— и» .с»'1х» — х»+д~, т,= с„с»=с,+с,+с,: (ойд)— д/ юа и + ге»)х х» д/2 (тд с») ( 1 (3 — с»/(тд с») (дх)— р,:д г, ~ !! х' — х' 1/(1 — о), то судцеспдвует точка минимума х» Е Х, и последовательность (х")» в, порожденная алгоритмом 2, такова, что (х» — х*(( где», '(х» — х» ( = О (()»); 2) если выполняются условия (х)— (А, — Ч'„/» (х») 1( с, (х» — х"+' ~; (х()— $$Ь» — Ч/ (х»)$$(с Цх» — х»+'Ц', (хй)— о» ( с, ( х» — х»+' (», т, ) с, !) х' — х» !), с, = с, + с, + с,; (хдй)— д /~ (с» + у/2) ) хд — х» 'у(тд — с»1хд — х' 1) ( 1; (хд'о)— р >(дх' — 'ЙИ»(ч) П Положить й О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
