И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 73
Текст из файла (страница 73)
Здесь через Я ((а)ч ) обозначено диагональную т Х т-матрицу, у которой диагональные элементы равны (а,)ч*, ( = 1, ..., т, а = =(а„..., а). Библиографические «хпягния. При написании параграфа была использована работа [ 1391. Другие сведения о сходимости методов, оценках скорости сходимостн, рекомендации по практическому использованию методов, результаты зкспериментального апробирования методов можно найти в работах [134, 136, 137, 138, 1391.
5.25. Методы фейеровских приблилоений решения задач выпуклого программирования с негладкими ограничениями «. Общий олтчой Определение 1. Отображение ф . В" -«. 2" называется фейеровскнм, если Х (ф) Ь (х ) х ~ ф (х)) чь )3; Р— У1(~х — у~, ЧгЕф(х), Уу~Х(ф), ЧхЕХ(ф). Класс фейерозскнх отображений обозначим через Ф н выделим подкласс Ф, класса Ф условием Фо= («р!хЕ«г(х) соф(х) =х; фсФ). Определение 1'. Отображение ф . В" -~ 2" называется замкнутым, если нз соотношений )ппх" = х'; у" = ф (х"), й = 1, 2, ...; 1ппу« = у' ».«с« следует у' е «р(х'). 3 а д а ч а !. Найти агд гпах (с, х) для заданного вектора с ~ В" «ях!и н заданного фейеровского отображения ф ~ Ф,.
Алгоритм 1 Н а ч а л о. 1. Задать фейеровское отображение «р Е Ф„. П. Выбрать пронзвольное начальное приближение х'. ~ В". П1. Положить й = О. Ос н о в н о й цн к л. !Ч. Вычислить шаговый множитель р», удовлетворяющий условиям теоремы 1. Ч. Вычислить следующее приближение х»+' с ф (х« + р„с).
Ч1. Положить й = й + 1 н перейти к шагу 1Ч. Теорема 1. Пусть выполняются условия: (о) — фейеровское отображение ф ~ Ф, — замкнуто; (В) — множество Х ~ Х (ф)— ограничено; (Ио) — для некоторого б, ) О существует ео ~ О таксе, что пй и !( х — г ) — ш!и ~ у — г !) ~ е„Ч х Е Хо„Ч у Е ф (х); «ЕК «ЕХ (Ы)— р«)О, й=О, 1, ...; !!гпр =О; ~ р»= оо. «м «=о Тогда предельные точки последовательности (х«)» о, порожденной алгоритмом 1, принадлежат множеству решений задачи 1.
Явв Здесь Хе обозначает 6-окрестность множества Х. Замечание 1. Если для задачи найти агитах(с, х), ссВ . (9.89) «ах Х = (хЦ!(х)(0, 1= 1, ..., т, хсВ ) (з 99) с выпуклыми функциями 1 (х), 1 = 1, ..., гп, и ограниченным множеством Х фейеровское отображение ф определить по правилу !р(х)(~(х — Лр(х, й)[ЬЕб(х)), (Э.э!) где параметр Л ~ (О, 2); О, если 1(х)(0 ([(хЯ Це) Ь, если 1 (х) ) 0; 1(х) = тах 1((х) или 1(х) = ~„шах(0, 1((х)): !в(вк (=! 6 (х) — множество обобщенных градиентов выпуклой функции 1 ( ) в точке х, то условия (1), (й), (ей) теоремы 1 будут выполняться. Таким образом, решение задачи (5.89) — (5.90) можно получить с помощью алгоритма 1, в котором фейеровское отображение ф определяется по (5.91). 2. Случай кусочно лввейвых ограввчеввй 3 а д а ч а 2.
Найти агц ппп (с, х) при ограничениях «ах ! Х: х~ ~, 'тах[(с!', х) — а!!) — 6,(0, 1=1,...,т, х~В"), [ !=! !е.у! где с ЕВ"; с(! ЕВ" прн 1'6 [1: т), 16 (15(!; ад, (6 [1: т), 16 5 (1Г«!, 'Ьп 1 5 П: т[ — действительные числа; 1 В 1 — нату! ральное число; й! — множества индексов. Предположение 2.
Множество решений Х* задачи 2 непусто. Алгоритм 2 Н а ч а л о. 1. Выбрать произвольное начальное приближение хе~ В". П. Выбрать' произвольный параметр Л ~ (О, 2) и произвольные константы а!) О, 1 1, ..., т. П1. Положить й = О. О с н о в н о й ц и к л. !Ч. При каждом 1 ~ [1: т] вычислить индексы гл = пцп(е[тах [(с(!, х") — а!![ = (сн, хе) — а!ч, аЕО!), !еу! !=1, ..., 1, 1=1, "., т. Ч. При каждом 1 5 П: т) вычислить а-мерный вектор 1г!(хе) = ~', с!г«!! ! ! Ч1. Найти Х-разделяющую пару (й (хь), [1 (хь)) по правилам ' й(х') = ~ а]й](х"); у=! й(х") = 2„,' а! < ~, гпах [(с]], х") — а]!) — Ь! +. ! ! [г=! ]е,т! Пара (й (хь), [1 (х")) является Х-разделяющей, если для любого фиксированного х»Я Х полупространстзо, отвечающее неравенству (й(хь), х — х") + р(х")(О, 1» = агя гпах ( ~; шах [(с", х") — ау[ — Ь, +, хь ]с Х, КП»н] [ ! — ! ]в.у! где [о)+= шах (О, и).
Ч11. Вычислить значение р„, удовлетворяющее условиям теоремы 2. ЧП1. Вычислить вектор х" — )» 3[ ] й(х"), р( ')>О, .„'+' = 1» (~ь) 1' хь, ~(хь)(0. 1Х. Вычислить следующее приближение х+ =х+ — р,с. Ф+! -ь+! Х. Положить й = й [- 1 и перейти к шагу 1Ч. Теорема 2. Если выполняется предположение 2 и последовательность (рь[~". о удовлетворяет условиям й-'оо] Е Рь=со» ь=о рь)О; рь-» 0 при то последовательность (хл)Г~ сходится к влементу хе~ Хе. порожденная алгоритмом 2, Библиоелаб]ические Вготтанпл, Пункт 1 написан на основании работы [145], при написании пункта 2 испольвоввлнсь работы [140, 142, 143, 144, 1461. 397 содержит множество Х.
Х-разделяющую пару (й (хь), р (х")) можно также вычислить по формулам г Р(хь) = шах ~ ~' гпах [(с!', х') — а;г[ — Ь! + ге[ген] ! ! ]в,т! й(х') = й'ь(хь), б.26. Двойственные методы 1. Првалшкеивый двейетвеииый мевед решеиил аадач выпуклого программпреваииа 3 ада ч а 1. Найти агя !пах ге(х) для заданной функции «ох уе ! В" -» В' и множества Х=(х/~!(х)~0, !'=1, ..., т, хЕ!е), где Я вЂ” выпуклое множество в В"; 1! . В"-» В', ! = 1, ..., т. Предположения 1, (1) — функции ~! (х), 1 = О, 1, ..., т — выпуклые вверх на выпуклом множестве (1.
Двойственной к задаче 1 является следующая задача Г: найти агдш)пяе(у), где уе(у) 1йзпр !р (х, у), !р(х, у) — функ«до «яч ция Лагранжа задачи 1. В приводимом ниже методе вводится модифицированная функция Лагранжа ф (х, у) в виде Р(х у) = цр Ре(х)+ ХК(х) — г) у! — Е !Й(х) — г;), (з.'-'з) «де 1 Г=! 1=1 где у (у! " у ), г = (г„..., г ), г, ($) — дважды непрерывно дифференпнруемая функция вещественной переменной $ такова, что На Ьй итерации алгоритма вычисляется точка хе, являющаяся приближенным решением некоторой вспомогательной задачи условной максимизации (точность решения вспомогательной задачи задается некоторой управляющей последовательностью), а точка уам вычисляется в направлении антиградиента модифицированной функции Лагранжа, вычисленного в точке (х", у").
При определенных условиях получаемая последовательность двойственных переменных (уа)Г е будет сходиться к непустому множеству 1«е решений двойственной задачи, а (х")»" » будет являться обобщенным решением задачи 1, т. е. 11ш~!(х') вО, 1=1, ..., т, 11ш~е(ха) = зпр1е(х).
Ь~м «ех Алгоритм л Н а ч а л о. 1, Выбрать произвольное начальное приближение двойственной переменной уе~ В . П. Выбрать дважды непрерывно дифференцируемые функции г, ($), 1 = 1, ..., и, вещественной переменной $ такие, что г,(0) = — "=О, — ",";~ву)0, 1=1, ..., т. (з.вз) 398 1П. Определить модифицированную функцию Лагранжа Ф(х, у) =шах11,(х)+ ~',(гс(х) — е,)у,— ~;гс(сс(х) — г,), аэь 1 с с где е = (г„..., х' ); у = (у„..., у ). 1Ч. Положить й = О. Основной ц и к л.
Ч. Найти шаговый множитель р„и элемент б„управляющей последовательности, удовлетворяющие условиям теоремы 3. Ч1. Вычислить точку хь Е Я, удовлетворяющую условию ~ь(х", у')~кпрф(х, у') — 6„. «ео ЧП. Вычислить вектор Чих", уь) (градиент функции чс (х, у) по переменной у в точке (хь, у )) по правилу = ш!п (1с (хь), 1, (у,')), 1 = 1, ..., т, х", асс) Ус где 1с(тс), 1 =- 1, ..., т — функция, обратная функции сьс Ф 'Ч111. Вычислить следующее приближение у~+с = у~ — рлЧея(хь, уь).
1Х. Положить й = й + 1 и перейти к шагу Ч. Теорема 1. Пусть выполняется предположение 1 и пусть (11)— множество У* решений двойственной задачи 1 непусто; (111) — управляющая последовательность (6„)», такова, что 6, ~ О, А = О, 1, ..., ~, '(6„) '* < оо; ~о ((о) — последовательность шаговых множителей (рь) ь.о удовлв. творяет условию 0<р<р <р<2у, 6=0, 1, ..., где у — число, фигурирующее в неравенствах (6.93).
Тогда при произвольном начальном приближении уь Е В последовательноапи (хь)ь.ь (уь)Г ь, порожденные алгоритмом 1, обладают свойствами 1пп уь = у* ~ 'г'ь, ь~ юю (х")Г=ь — решение обобщенной задачи, соответствующей мдаче 1, т. е. 1ип~с(х') ИО, с =1, ..., т, 1пп~о(хь) =о ь-~~ ь м еде о — зкстремальное значение обобщенной задачи. 399 Замечание 1. Если дополнительно выполняется соотношение двойственности, т. е. о = о, где о — экстремальное значение двойственной задачи Г, то последовательность (х")ь" ь, порожденная алгоритмом 1, является обобщенным решением задачи 1, т. е. !!ш1»(хь) ВО, 1= 1, ..., т; !!ш~ (хь) =о.
ь- ~ Здесь о — экстремальное значение задачи 1. Определение обобщенной задачи. Последовательность (х")г=ь, хь Р Я (обозначим ее через ш) является обобщенным решением задачи 1, если: а) существует конечный или бесконечный предел 1пп (, (х") (обозначим этот предел через ), (и)); б) 11ш ), (хь) ) О, 1 = 1, ..., т. Множество обобщенных решений задачи 1 обозначим через (ч".
Задачу максимизации функции 1, (и») на множестве обобщенных решений Я7 называют обобщенной задачей 1. Экстремальное значение о обобщенной задачи 1 определяется по формуле гор )'о (ш) если %' Ф 8, о»~ем — оо, если Я7 О. Глубже с понятием и свойствами обобщенной задачи можно ознакомиться в работах (80, 81!.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
