И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 82
Текст из файла (страница 82)
Поскольку константу а, обеспечивающую выполне- 448 ние условия (Ь) теоремы 1, выбрать заранее довольно трудно, то в [280, 320] рекомендуется выбирать а = 2 2 ]31(ха) 1ЗУ« всякий раз, когда (зо) не выполняется. Замечание 1'. Достоинством приведенного в этом параграфе метода является его сходимость с любого начального приближения ха, принадлежащего достаточно малой окрестности множества Х. В то же время метод требует на каждой итерации решать вспомогательную задачу (6.2), для которой не существует в общем случае эффективных алгоритмов. Библио«райна«спи« уииеаииа. Параграф написан на основании работы 12ЗО]. 6.4. Сеточный метод последовательных приблинсений решении непрерывных минимаиеных задач 3 а д а ч а 1. Найти агд т!и гпах ф (х, у) для заданных функции крх еиу ф: В" х В -~ В', ограниченного замкнутого множества ]к с: В, выпуклого замкнутого множества Х ~ В .
Предположение 1. Функция ф (х, у) непрерывна вместе с Ч„ф (х, у) по совокупности переменных в Х'1С ]к, где Х' — произвольное открытое множество, содержащее Х. Ниже описывается метод вычисления стационарных точек функции шах ф (х, у) на множестве Х, т.
е. точек х', для которых еку ]п] гпах (Ч,ф (х', у), х — х*) = О, «ЕХ ЕЕЯ1«Ч где Х(х) = [у[ф(х, у) =гпахф(х, у), у~У). езу Алгоривзм 1 Н а ч а л о. 1. Выбрать начальное приближение ха Е Х. П. Положить й = О. Основной ци к л. П1. Построить сетку ]'н, = [у'!16 [0: Ма] у'6]к), удовлетворякицую условиям теоремы 1. 1Ч. Определить функции ф;: В"-~ В', 1 Е [О: Ма], по правилу фз (х) 1зф (х, у'), (6 [0:Уа]. Ч. Используя алгоритмы 9 6.1, найти хотя бы одну стационарную точку ха ~ Х функции шах ф, (х) на множестве Х.
зз1о:на1 'т11. Положить й = и + 1 и перейти к шагу П1. 449 16 з-зи Теорема 1. Пусть выполнено предположение 1 и, кроме того: (1) =множество У ограничено и замкнуто; (й) — множество Х выпукло и замкнуто; (ей) — последовательность сеток ( Ун ) ь~ а всюду плотна на множестве У, т. е. для произвольного е ) 0 можно указшпь яшкой индекс й„что для всех й ) яа расстояние между произвольной точкой у р У и ближайшей к у точкой сетки 1'на будет меньше е. Тогда любая предельная точка последовательности (ха) ь~, порожденной алгоритмом 1, является стационарнои точкой функции шах ~р (х, у) на множестве Х.
«И Библиографические указания. Прн написании параграфа использованы работы [238; 239, 127!. 6.5. Метод штраФа в задаче поиска максимнна 3 а д а ч а 1. Найти х*= агд гпах ппп аз (х, у) для заданной *ах «с« функции ф: Н ~с В" — В' и заданных компактных множеств Х и У. Предположение 1. Функция ер непрерывна на произведении компактов Х и У. В методе штрафа вычисление вектора ха и величины максимина и'=шах ш!п<р(х, у), «сх «яу сводится к решению последовательности задач условной максими- зации по (х, и) функций д,(х, и, аа) =и — се„) )ппп(0, ер(х, у) — и))'4«(у), т)0, У .где т) 0 — произвольный параметр; аа) О, !пп а« = оо; [з— мера на множестве Г. Если (х* (аа), и* (аа)) — решение задачи максимизации у, на множестве Х х У (здесь У вЂ” любой отрезок, содержащий точку и'), то предельные точки последовательности (х* (аа), и' (а«))Го являются решением задачи 1.
При т > 1 функция д, всегда вогнута по и; если, кроме того, нз (х, у) вогнута по х при каждом у ~ У', то функция д, (х, и, аа) вогнута по (х, и). Если д (х, у) дифференцируема по х, то при т ) 1 функция у, (х, и, иа) дифференцируема по (х, и): — вл й,(х, и, аа) = таа ~) пип (О, р(х, у) — и) )' ' х д р(х' у) ~р(у)' д д,(х, и, аа) = 1 — таа) ) ппп(О, ер(х, у) — и) )' ~ йр(у). Алгоритм 1 Н а ч а л о. 1. Выбрать последовательность [а«]>=д коэф- фициентов штрафа такую, что а« ~ О, с = О, 1, 2, ...; 1пп а> = оо. «-ккк И.
Задать меру р в пространстве, содержащем ]к, такую, что любое непустое пересечение Р' с любым открытым множеством имеет положительную меру. 111. Выбрать параметр т ) О. 1Ч. Задать отрезок У, содержащий внутри себя значение и* = >пах ш!и «р (х, у). кех УЯУ В качестве У можно, например, выбрать отрезок [ппп «р (х, у) — 1, шах «р (х, у) + 1]. «к,д>ВХХ У «к,г>аХХ У Если выбрано т ~ 1, то можно положить У = ( — оо, оо). Ч. Положить й = 0 О с н о в н о й ц и к л. Ч1. Определить функцию д,(х, и, а,) и — ад~[ш[п(0, «р(х, у) — и) ['«(р(у). Ч11. Вычислить точкУ (хк (ад), и* (ад)) Р Х Х У, Удовлетво- ряющую условию у,(х*(ад), ик(ад), ад) = шах у,(х, и, ад).
«, >еххо для нахождения точки (х* (ад), ик (а„)) решается задачамак- симизации по (х, и) функции ук (х, и, ад) на множестве Х х У, причем решение этой задачи на (й — 1)-й итерации принимается за начальное приближение задачи максимизации в /с-й итерации. Ч!11.
Положить й = /с + 1 и перейти к шагу Ч1. Теорема 1. Пусть выполняется предположение 1. Тогда шобая предельная точка (х', и*) последовательности (хк (ад), и' (ад)]» о, порожденной алгорипсмом 1, является решением задачи 1, т. е. и' = шах ппп«р(х, у) = ппп «р(х*, у), ках КЬУ УЧУ причем при всех й = О, 1, ..., т ) 0 справедливы неравенства >п!п«р(хк(ад), у)<ик(дк(хк(а»), и*(сс»), ссд)(и'(ад). кьУ Теорема 1'. Если У' — параллелепипед т-мерного пространства В, >с — мера Лебега, а функция «р (х, у) удовлс«п>воряет условию Липшица по у равномерно относительно х, т.
е. ] «р (х, у) — «р (х, у) [ ~ (у [[ у — у ], Ч у, у р ]', х Е Х, то для достаточно больших а„справедлива оценка 0< ик(ад) — и*< р(т, т) [у /ад]~л'~ еде р (т, т) — константа, не зависящая от ад и у. 1зк 451 Если У = [у', ..., у'] — конечное множество, ут(х, и, а„) = и — ае ~ [пйп [О, <р(х, у) — и) [', !=1 то (акт[) ' '(и*(ае) — ие((яат) 7а ~ при т) 1; ие(аа) = ие при т = 1, а,) 1. Замечание 1.
Если задана точность в определения величины максимина, то в алгоритме 1 вычисления следует проводить до тех пор, пока не будет выполнено неравенство и'(а,) — ппп ф(хе(яа), у) (в лет (для этого необходимо оценить глобальный минимум функции ~р (х* (а„), у) по у Е У). Замечание 1', Для ускорения поиска максимина с заданной точностью, сокращения обьема вычислений, преодоления трудностей, связанных с «овражным» характером параметризованной задачи, в [372) рекомендуется последовательность а,, й = О, 1, ..., выбирать по правилу аа(а»+1(а»+~(т, т, у)а!"+ аит-', [«=О, 1, ..., где р (т, т, у) ) Π— константа, не зависящая от коэффициента штрафа я„; у — константа Липшица функции ~р (х, у) по у; а, следует брать не слишком большим, чтобы уменьшить время поиска (хе (яе), ие (ссе)) Библиографические укняткия.
Параграф написан на основании работ [67, 368, 3721. Дополнительные сведения о методе штрафов для решения задач максимина можно найти в работах [369, 370, 661. 6.6. Методы стохастического квазиградкента в задаче поиска макскмкка 3 ада ч а О. Найти х*= агд шах ппп у (х, у) для заданной «ех ает функции ~р: В" х В"-'-» В', компактного множества У пространства В и множества Х [х!Рс(х)~вО, 1= 1, ..., т, х~В"). (6.3! Предположения О. ($) — функция ~р (х, у) — ограничена и непрерывно дифференцируема по х на В" х [«; (й) — функции ~, (х), [ = 1, ..., т — непрерывно дифференцируемы и ограничены снизу на В". Задача вычисления вектора х* и величины максимина и' = шах ппп <р(х, у) «ех уьг 452 сводится к максимизации по (х, и) ~ Х Х (/ функции д,о,,(х, и, а) = и — а )-1 гпш (О, !р (х, у) — и) (" !/р (у)— У вЂ” ~; р!(ш(п (О, /!(х)) ('*, ! ! где т„т,~О; р; ~ О; ~„р!= 1; а — коэффициент штрафа; р— ! 1 некоторая мера на множестве 1', (/ — любой отрезок, содержащий точку и*.
Функцию учл! (х, и, а) можно рассматривать как математическое ожидание Ег,!!/,„„(х, и, а/у, !) функции !/,„,, (х, и, а/у, !) = и — а ~ ш1 п (О, <р (х, у) — и) ("— — а(ппп (О, /!(х)) 1'* от двух независимых случайных величин у, !, причем у распределена на компакте г' в соответствии с мерой р, а !' принимает значения из множества й = (1, ..., т) с вероятностями р„р„..., р . Для решения задачи максимизации применяется метод стохастического градиента. В алгоритмах с ростом итераций коэффициент штрафа а стремится к бесконечности и в отличие от алгоритма 1 (см.
$ 6.5) на каждой итерации нет необходимости решать задачи максимизации и вычислять многомерные интегралы. 1. Основной алгоритм Алгоритм 1 Н а ч а л о, 1. Выбрать произвольное начальное приближение (х', и') Е Й" Х В!. !1. Задать меру р в пространстве, содержащем У', такую, что любое непустое пересечение !' с любым открытым множеством имеет положительную меру. 1П. Выбрать параметрыт!) 2,т,~э 2и константуа, ) О (обычно выбирают: т,= 2, х,= 2, а,~ П, 1ОЧ).
1У, Задать числа р!, ! = 1, ..., т (р, ) О, ! = 1, ..., т, х~'„р, = ! ! = 1), которые, соответственно, характеризуют требуемую относительную точность выполнения ограничений (6.3) в задаче О (обычно Рс=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}
