И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 78
Текст из файла (страница 78)
Вычислить шаговый множитель р, ~ 7.„, удовлетворяющий условию го (ха Йlт ) ~ ~(1 Ко) 7о (» ) + )сатоь где )«а — произвольная точка фиксированного отрезка [)«, П; К— произвольная константа из полуинтервала (О, 1): тоо = пп'п ~,(х' — р)га). оало ЧП. Вычислить следующее приближение хо+' = х" — р„Л". ЧП1. Положить я = й + 1 и перейти к шагу 1П. Теорелоа 7. Пусть выполняются предположения 7 и (оо) — мно. жество Х регулярно, т.
е. в й" существует сфера радиуса К, «еликом принадлежащая множеству Х; (о) — для любого елемента х'~ Х множество Х. = (»~~о(х)(1о(хо) »ЕХ) ограничено. Тогда бесконечная последовательность (хо)а о, порожденная алгоритмом 7, такова, что РУ,Ф)-1,(.*), й- )=1. Библпоерафичеатие укоаппиа. Параграф написан на сснованнн работы П93!. 5.33. Методы решения задач оптимизации с бесконечным числом ограничений 3 а д а ч а О. Найти ага ппп го (х) для заданной функции «еи 7о ~ 77"-э Иа и заданного компактного множества Х ~ 77" при дополнительных ограничениях 1,(х, у)(О для всех ус)«, где 7,: 77" х 77'"-о 77', )«с: 77 . Многие задачи оптимизации могут быть представлены в форме задачн О. Например, если в мнннмаксной задаче вида о' = ш!и !пах Ч>(х, у) кцх деу положить о! (оо, оо оо н Х,= (о„оо), то ее можно пРедставить в форме задачи 0 как ппп х, прн ограничении ~р (х, у) — хо(0 и> мех>хх для всех у Е )к; другие примеры можно найти в (435).
Предположения О, (о) — функции 1„1, являются непрерывнымн на множествах Х н Х х г', соответственно; (й) — Х н )к — не- пустые компактные множества. На й-й итерации находят приближение х» как решение аппрокснмнрующей задачи: найти агяш(п1»(х), кое» где б„= (х(1 (х„у)(0 для всех уЕ к'», хЕХ).
Конечные множества )'» аппрокснмнруют множество )' н нх находят с помощью решения задачи максимизации по у Е )к функции 1о (х', у). 1. Общий алгоритм Алгормиом 1 Н а ч а л о. 1. Выбрать произвольное конечное подмножество )коС у. )!. Положить й = О. Основной цн кл. П1. Найти допустимое множество О» Й-й аппрокснмнрующей задачи по правилу О„= (х(1,(х, у)(0 для всех уЕ)'„хЕХ).
Ж. Найти решение х» Е б» следующей й-й аппроксимирующей задачи: найти агя ппп 1,(х). кто» (Отметнм, что выполняются включения О с ° с б»+~ с О, с ° ° ° с б„ (5.,!04) где б ~~ (х(1, (х, у) (О для всех у Е)к, хЕ Х), н справедливы неравенства 1» (хо) ~ (1» (х') ~ ~(1о (х") ~( ~( 1о(х*)> (5 !зз) где х* — решение задачи 0). Ч. Найти решение у"+' ~ )' следующей Ьй вспомогательной задачи:. найти агя шах 1, (хо„у). Оог Ч[. Если выполняется неравенство 1»(х', у»+')з О, то положить х*= х" и прекратить вычисления (решение задачи 0 находится в этом случае за конечное число итераций); иначе положить У»41 = Уа [) (уь+') и перейти к шагу ЧП. ЧП, Положить й = [з + 1 и перейти к шагу П1. Теорема 1.
Пусть выполняется предположение О. Если хе есть предельная точка бесконечной последовательности (ха)~, порожденной алгоритмом 1, то х* является решением задачи О. Теорема 1'. Пусть выполняются предположения О и (!аа) — функция !».(х, у) — выпукла ло у при всех х с Х; (»о) — множество У является многоугольником. Тогда алгоритм 1 сходится к решению х* задачи О за конечное числа итераций. 2. Оелабаеиими алгоритм В ослабленном алгоритме на каждой итерации отбрасываются все несвязные ограничения. Сходимость ослабленного алгоритма имеет место при некоторых дополнительных предположениях. Алгоритм 2 1 — Ч (шаги 1 — Ч такие, как и в алгоритме 1). Если выполняются только предположения О, то соотношения (5.104) и (5.105) для алгоритма 2 в общем не имеют места. Ч1.
Если выполняется неравенство 1» (ха, у"+') О, то положить х*= х' и прекратить вычисления (в этом случае реше- ние х' задачи 0 находят за конечное число итераций); иначе перейти к шагу ЧП. ЧП. Положить 2а — — (У[1,(х», У) ~0, УСУ»), ЧП1. Положить ~'а+ = У, () (у'+ Г~2,. ! Х. Положить й = й + 1 и перейти к шагу П1. Теорема 2. Пусть выполняются предположения О.
Тогда» 1) если бесконечная последовательность (ха)» с, порожденная алгоритмом 2, сходится к некоторой точке х*, то хе является решением задачи О; 2) если функции 1о (х) и 1» (х, у) выпуклы ло х ('при каждом у Е Е )'), а Х вЂ” вьтуклое множество, то последовательность (1е (х»))ь е монотонно не убывает» 3) если функция [е (х) строго выпукла, каждая из функций 1» (х, у) выпукла по х для у Е У, Х вЂ” выпуклое множество, то по- следовательность (х")»..с сходится к решению хе задачи О. Библиографиееапм указания. При иаписаиии параграфа использовалась работа [4351, 6.34. Методы решения задач квадратичного программировании В этом параграфе приводятся некоторые методы решения задачи квадратичного программирования, которая является вспомогательной задачей для многих алгоритмов.
Задачей квадратичного программирования называют задачу минимизации квадратичной функции при линейных ограничениях. 1. Метод еопрямеввыя традвентов дяя мипвмивацвв пвадратвчной фуввции на подпроотраветве Задача 1. Найти агй ш)п~ — (Сх, х)+ (г(, х)~, Г 1 зх" ~ где Х = (х ) (аг, х) — Ь; = О, 1 Е О); С вЂ” симметричная положительно определенная матрица размера и Х и; о(ЕВ", а РВ", (ЕГг', оà — конечное множество индек- сов; Ь, ЕВ', ГЕ О.
Предположения 1. (о) — С вЂ” симметричная положительно опре- деленная матрица размера л х и, т. е. (Сх, х) в О для всех х6 Е В"; (й) — векторы а', г ~ 'эГ,— линейно-независимы. Алгоритм 1 Н а ч а л о. 1. Найти начальное приближение хо~ Х. 11. Вычислить л х и-матрицу Н по формуле Н = Аг(ААт) — 'А где А — матрица, строками которой являются и-мерные вектор- строки (а'), (Е й. П1. Вычислить градиент минимизируемой функции Г (х)1",) — (Сх, х)+ (А, х) в точке х хо по формуле Ч1~(хо) = Схо+ г(, 1Ч.
Вычислить л-мерный вектор Ь = — (1 — Н) Ч~о(хо), где 1 — единичная л Х и-матрица. Если Ь' = О, то прекратить вычисления, иначе перейти к шагу Чо Ч. Вычислить шаговый множитель Рг = (Чго(хо) и )г(л Си ). Ч1. Положить х' = хо + ргй'. Ч11. Положить й = 1, йо = Ь'. Основной цн кл. Ч1П. Вычислить п-мерный вектор Ио = (1 — Н) Ч1о(х"), где ЧГо (х') = Сх'+ г(. Если д" = О, то прекратить вычисления; иначе перейти к ша- гу 1Х, 1Х. Вычислить и-мерный вектор 1г«1« Ьь 1га 11' Х. Вычислить шаговый множитель р,+,- — (Ч1,( ), Ьг+)1(Ь+, СЬг+). Х1. Положить ха+' = х'+ Рь«Ф+'. .Х11. Положить й = Ь + 1 и перейти к шагу Ч111.
'Теорема 1. Если выполнены предположения 1, то алгоритм 1 решает'задачу 1 за конечное число итераций, не превышаянцее и. При етом, если минимизируемая функция /е (х) (~ у (Сх, х) + (й х) 1 имеет на множестве Х конечный минимум, то последовательность (ха), порожденная алгоритмом 1, сходится к точке минимума х" задачи 1 за конечное число итераций й ( и.
Если функция Го (х) не- ограничена (снизу) на множестве Х, то при некотором Ь «~ и бу- дет выполняться равенство (Ь"+', СЬ+') = О, апо влечет рь+~ * — оо. В. Метод еопрвщеивых градвевтов двв общей аадачв ваадратичиого програмиироваиив 3 а да ч а 2. Найти агд ппп1-б- (Сх, х) + (й, х)~, Г 1 «ЯХ где Х11(х((а', х) — Ь,(0, 1ЕЬ1; (а', х) — Ь, О, ГаР); С вЂ” симметричная положительно определенная матрица размера и х и; й Е В"; вГ и Р— конечные множества индексов; а' Е В", 1РОо() ф Ь,~В' (Е~о и 6' Предположения 2. (1) — С вЂ” симметричная положительно опре- деленная матрица; (Ы) — выполнено следующее условие невырож- денности: при любом х й В" векторы а', 1 Е о (х) — линейно-неза- висимы, где В(х)1~(1)(а', х) — Ь, .
О, 1сО () В'е). (б.1об) Алгоритм 2 Н а ч а л о. 1. Найти начальное приближение хе ЕХ. 11. Найти множество индексов О (хе) и положить Ое= ьГ (х') (здесь множество У (х) определяется по (5.106)). 1П. Вычислить и ~с и-матрнцу и =Ат (4 Аг) 'А где Ар — матрица, строками которой являются и-мерные вектор- стРоки (а')г, ГЕ ое. 428,. 1Ч. Вычислить вектор ио (А~ А~~ ) Аэ„Ч~ь (хо) где ~Чо (х) = Сх+ й. Ч. Вычислить а-мерный вектор но = (1 — НУ,) Ч1о(хо) =* Ч1о(хо) + Ах и'.
(злот) Если йо= О, то перейти к шагу Ч1; иначе перейти к шагу ХХП. (В случае, когдаао = О, точка хо является точкой минимума Функции )о (») Й о (Сх~ х) + (о(, х) на грани, определяемой систе- 1 мой УРавнений (а', х) — 6, = О, (Е Ио). Ч1. Определить компоненты вектора и', которые в равенствах (5.107) умножаются на векторы а', (Р й Д Уо. Пусть они будут о о о и „ и , ..., и ЧП. Если йп .
О, ..., и; ) О, то положить хо= »о и прекратить вычисления (в этом случае х* — решение задачи 2); иначе перейти к шагу ЧП1. ЧП1. Найти индекс 1 Е (1о ..., 1„), длЯ котоРого выполниетса неравенство й ~ О. 1Х. Найти индекс 1' Е ао П й такой, что вектор а' в (5.107) умножается на компоненту и~ о Х. Образовать новое индексное множество Уо, которое получается из множества ао отбрасыванием индекса 1'. Х1. Образовать матрицу А~' строками которой являются пмерные вектор-строки (а~), 1 р йо. ХП. Вычислить и:с и-матрицу ХП1.
Вычислить вектор Ь1 = — (7 — Н ) Ч10(хо). ~о Х1Ч. Положить й 0 и перейти к шагу ХЧП. Основной ци кл. ХЧ. Вычислить вектор (7 — Н )м то 'с Ч Го (х ). Если (1 — Н ) Ч1о(х") = О, то положить хо = х" и перейти то к шагу П; иначе перейти к шагу ХЧ1.
ХЧ1. Вычислить вектор 1д — Н )У).(")1о (1 Н ') Но(» ) + то ' 11~ — Н ОЧ)о("-') Р Хо ХЧП, Вычислить рь+> — (Ч! (хч), Ьх+>)l(йл+>, Сйл+<). ХЧ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}
