И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 80
Текст из файла (страница 80)
Если для всех 1~ (1, ..., и)',Я выполняется неравенство (а~, и)+ (дс, Я~у — с)~ О, то вычислить оптимальное решение х'= (хь ..., х„) задачи 5 /уи если 1сп, (О, если 1Я О, и прекратить вычисления; иначе положить| = Г1 и перейти к шс» гу 1Ч. 1Ч. Найти индекс й Е (1, ..., п)~~ й', для которого выполняется неравенство (а~, и)+(д», ~ту — с) О. Ч. Положить О = й [[ (й).
Ч1. Найти вектор у, координаты которого ур 1 ~ Р, вычисляются по правилу у; = у, при всех 1Ев'; д,=о и перейти к шагу Х1. ЧП. Вычислить максимальное значение Х ~ [О, 1), при котором )д+(1 — Л)д>О, и положить г~ —— Ху;+(1 — Цуи 1ед. ЧШ. Положить И = Э. 1Х. Найти множество Ф, состоящее из тех индексов й е 0', для которых г, = О и положить И = В" й. Х.
Вычислить вектор у, координаты которого находятся по правилу У! = хи 1 с и > и перейти к шагу Х1. Х1. В соответствии с множеством а составить подматрицу Вд матрицы А и подматрицу Ят матрицы 6. ХП. Найти решение (у, и) системы линейных уравнений В,д=Ь; В~и+ Я~~9ту = Я~с и перейти к шагу П. /1~ найти агдш(п ( — Ь)А)~ ) о,х) х (5.116) при ограничениях 1=1, (1, х)~0, (6.117) Если выполняется неравенство ( — Ь1А) ~ О, то задача 5 не имеет допустимого решения; если ( — Ь1А) „= О, то х* удовлетворяет условиям х'~ 0 и Ахь= Ь.
$ Если х"рь О, то множество столбцов аг, для которых х) ) О линейно-независимо и вместе с соответствующими столбцами д1 образует начальную матрицу 11л ) алгоритма 5. ~ь| Отметим, что для решения задачи (5.116) — (5.117) можно использовать алгоритм 5 с начальной матрицей ~~ /, равной! Ь).
Замечание б'. Для решения систем линейных уравнений (5.114) и (5.115) в [524) предлагается следующий способ. Пусть ~ ) имеет размер (т + 1) х г. Тогда у и и определяются 437 Теорема б. Пусть существует множество индексов Р с= (1, ... (В '1 ..., и) та е, что матрица ~ ) имеет полный столбцовый ранг ~ь1 и система (5.1И) имеет решение (у, и), для которого у ) О, и пусть каждая матрица Вт, получающаяся в результате применения алгоритма, имеет полный строчный ранг.
Тогда за конечное число итераций алгоритма б вычисляется оптимальное решение х* задачи б. )'в ') Замечание б. Для получения начальной матрицы ~, ~,опнсан~ь,) ной на шаге 1 алгоритма 5, необходимо предварительно получить решение (1Р, х") следующей задачи квадратичного программирования: с помощью решения треугольных линейных систем о(Ь вЂ” и)=й; [ту=г[ для (ь — и) и у, где с[ = Русто -[- Уй й = ~ ть — ~тРУото; [[ув = л5; л — т х т-матрица с ортогональными столбцами и о— т (В ~ верхняя треугольная невырожденная т Х т.матрица, ~О~[ =йр[т, йт— у/ — (т + 1) К т-матрица с ортогональными столбцами, [т — верхняя г 1ув1 треугольная невырожденная т Х т-матрица, йт = 1[у ), йтв — имеет т строк, [[70 — имеет [ строк.
Библиоера»»ические ркаюиия. Прн написании параграфа использовались ра. боты [209, 320, 523, 5241. Дополнительные сведения о методах решения задач квадратичного программирования можно найти в работах [35, 310, 311, 437, 461, 467, 473, 507, 5461. Глава 6 СПЕЦИАЛЬНЬШ МЕТОДЫ РЕШЕНИЯ МИНИМАКСНЫХ ЗАДАЧ И МЕТОДЫ ОТЫСКАНИЯ СЕДЛОЕЫХ ТОЧЕК 6.1.
Методы последовательных приближений решении дискретных минимаксных задач 1. Микимаксиаа аадача с ограничениями простой структурм Зада ч а 1. Найти зги ппп гпах гр; (х) для заданных функ«ех гау ций ~р,: В" — В', 1~ й, заданного множества индексов й и заданного множества ограничений Х ~ В". Предположения 1.
(4) — функции фо 1 ~ й — непрерывно дифференцируемы; (й) — множество Х вЂ” выпукло и замкнуто. Алгоритм 1 Н а ч а л о. 1. Выбрать начальное приближение х' ц Х. П. Выбрать константы а, ) О и ае ) О. П1. Положить й О. О с н о в н о й ц и к л. [Ч. Найти множество точек Х» = (х [$ х — х» ~[, ( 1, х Е Х), где [[у[[, = шах [уг[. гтн:«1 Ч. Вычислить множество индексов Оье(х") = (1)<р,(х») = шахтер;(х»), Рь,й).
геу 433 Ч1. Вычислить »Р(х») = пйп шах (Ч«о, (х»), х — х»). «в» ~вас«~» ~ ЧП. Если ф(х») = О, то положить х»= х» и прекратить вычисления, если ф (х') ( О, то перейти к шагу ЧШ. ЧП1. Положить 1' = О. 1Х. Положить з = е/. Х. Вычислить множество индексов Я» (х") = (1) шах ф; (х») — »р, (х») ~( е, ! Е О). сет Х1. Вычислить ф«(х») = ш)п шах (Чф;(х»), х — х»). «сх»»ея »<«»> ХП. Если выполняется неравенство ф, (х») ( — а»е/е„то перейти к шагу ХШ; иначе положить е/~.~ = ег/2, 1 = /+ 1 и перейти к шагу 1Х.
(выход из цикла, определяемого шагами 1Х вЂ” ХП, будет осуществляться за конечное число итераций при каждом й = О, 1, ...). ХП1. Вычислить точку у', удовлетворяющую условию ф«(х») = шах (Ч~й (х»), у» — х»). ~еуге<«»ъ Х1Ч. Вычислить шаговый множитель р» из условия гпах»р, (х»+ р»(у» — х»)) = ш)п шах»р, (х»+ р(у» — х»)) »е.у »ааи»е~ ХЧ. Вычислить следующее приближение х»+' = х» + р» (у» — х»). ХЧ1.
Положить й = й + 1 и перейти к шагу 1Ч. Теорема 1. Если выполнены предполт»гения 1 и начальное приблиаеение х' в алгоритме 1 таково, что множеппво Х(х') = (х) шахтер,(х)(шах»р,(х»), хРХ) %.т»иу' ограничено, то любая предельная точка х* бесконечной последовательности (х»)» о, порожденной алгоритмом 1. является стационарной точкой функции шах ~р, (х) на множеспые Х. «еу Замечание 1. Основная трудность в применении алгоритма 1 связана с вычислением значения»р, (х") на шаге Х1. В П271 показано, что если Х» — строго выпуклое множество и начало координат не принадлежит выпуклой оболочке 1., (х»), натянутой на векторы Чф; (х»), 1 ~ Ж, (х»), то задача вычисления ф» (х») сводится к более простой задаче максимизации на /.» (х») непрерывно дифференцнруемой функции О(г) Ьпп1п(г, о — х»), »сх градиент которой 70(г) = о(г) — х", где о (г) Е Х" удовлетворяет условию 0 (г) = (г, о (г) — хл).
2. Первый метод последовательных приалимеввй решении мивпмаиеной еадачи е отравпчевввмв типа веравевета 3 а д а ч а 2. Найти агн ппп гпах фг (х) для заданных функций тях гое ~рг: В -~ лгг, г ~ И, заданного множества индексов гг и множества ХЬ(х!Рг(х)~(О, (бды хбгг ! Предположения 2. (1) — функции гро (ŠΠ— непрерывно дифференцируемы; (й) — функции!и ! ~ О,— выпуклы и непрерывно дифференцируемы; ((м) — выполняется условие Слейтера 1п1 гпах !, (х) ( О. *зн" 'Ж В пунктах 2 — 4 приводятся методы последовательных приближений для нахождения стационарных точек х* функции игах ~р, (х) гця на множестве Х.
Точка х' Е Х называется стационарной точкой функции игах гр, (х) на множестве Х, если многогранник Е (х') содержит нагну чало координат (здесь Е(хе) = са Н (х*), Н" (хе) = Н (х") () Н, (хе); Н(х*) = (7гр,(х'), гЕЯе(х*)); Н,(х') = (7Р,(х*), !6Яе(хе)); Яе(хе)= ((/пгах<р,(хе) = <р,(хе), (ЕО); кет Яе (х') = (! ! Рг ( ') = О, ! Е гг,)). Если игах гр, (х) выпукла на Х, то стационарная точка х' является гне точкой минимума. Алгоривтле 2 Н а ч а л о. 1.
Выбрать начальное приближение х' б Х. 11. Выбрать константы е,) О, р,) О, ае) О. П1. Положить й = О. Основ но й ци кл. 17. Найти множества индексов оьо(х") = (1!гпах~р,(х') =<рг(х"), ЕЕИ)1 з.т Яе (х') = (! ! Рг (х') = О, ! Е О,!. Ч. Вычислить множество векторов Н,(х') = Н,(х') () Но(х'), где Но(х') = (7<р, (х'), ! Е Жо(х")); Нз(х') = (7/~(х'), /ЕД,(х')). Ч1. Используя алгоритм !' (см. з 3.!2), определить, принадлежит ли начало координат многограннику /.00 (»"), который является выпуклой оболочкой, натянутой на множество векторов Н„(»»). Если начало координат принадлежит многограннику 1.„(»»), то положить х" = х» и прекратить вычисления; иначе перейти к шагу ЧП.
Ч!1. Положить з = О. ЧП1. Положить е = в„р = р„а = а,. 1Х. Найти множества индексов Я. (х') = (! ! шах ср, (х') — ~р, (х') ( з, ! Е г/); азу ! !в (х ) = (!! — р ~ (/! (х") (~ О, ! Е пд). Х. Вычислить множество векторов Й „= Н, (хь) (! Ня (хз), где множества Н,(х») = (Чц,(хз), !ЕЯ,(хь)); Н„(х") = (ЧР!(х ), !'Ей(х')), Х1. Используя алгоритм 1" (см. % 3.12), вычислить точку г, ближайшую к началу координат точку многогранника /., (х»), который янляется выпуклой оболочкой, натянутой на множество векторов Неа (» ) ° ХП.
Если выполняется неравенство ~!г„, ~! в и, то перейти к шагу Х1П; иначе положить з,.!.~ = е,/2, р,+~ = р,/2, а,.!~ = = я,/2, з = з+ ! и перейти к шагу Ч(П. ХП1. Вычислить вектор Ьц, (х") — направление (е, р)-квазина- искорейшего спуска функции шах ~р,(х) в точке х~ по формуле сну Лая(х ) = (!4!зея1!)зер. Х1Ч. Вычислить шаговый множитель р», удовлетворяющий условиям так ~р! (х" + р„йэя (х»)) = пип шах <р, (х" + рй.а (х')); ге,т р>0 ~ну + Радея (хь) Е Х. ХЧ. Вычислить следующее приближение хе+' = х" + р,п„в(х"). ХЧ1. Положить й = й + 1 и перейти к шагу 1Ч.
Творема2. Если выполнены предположения 2 и начальное приближение хе б Х таково, что множество Хеьь(хашах ф,(х)(шахф,(х'), хЕХ) ьту 16у ограничено, то любая предельная точка бесконечной последовапыльности (хе)е с, порожденной алгоритмом 2, ягляется стационарной точкой функции гпах ф, (х) на множестве Х. 'еу 3. Второй метод иоследовательиьтл ираблвмеввй решевиа минамансной вадачн с отравачевалми тина неравенств Алгоритм Я Н а ч а л о. 1.
Выбрать начальное приближение хс Е Х. П. Выбрать константы е) О, р, ) О П1. Положить й = О. Основной ц и к л. !Ч. Найти множества индексов нее (хе) = (1 ~ |пах ф, (хе) — ф; (хе) ( е, 1 Р О); 'ВУ Яе (х") = (1'! р ~ ~Ру (х ) » <О 1 Е ~ь). Ч. Вычислить множество векторов Осв = Ос(» ) () ~(а(х )ю где множества Не(хе) = (Чр,(х'), (6 Же(х')); Н„(хе) =~Ч1!(х"). 169с(х')). Ч1. Используя алгоритм 1' (см.