И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 77
Текст из файла (страница 77)
Если выполнены предположения 1 и условия р»~О, й = О, 1, ...; ~р„= оо; р»-».О при й- оо, то при любом начальном приближении х' ~ В" найдется подпосле- довательность (х»4)» ~ последовательности (х») ~~ь, порожденной алгоритмом 1, такая,.что 1ип 14 (х"») пип 1» (х). » кс.х Если, кроме того, 14 — строго выпуклая функ»(ия, то 1пп х» = х*, »»а» где 14(х*) = ш)п14(х), х'ЕХ. *ех Алгоритм 1' Н а ч а л о. 1, Выбрать произвольное начальное приближение х' е 11". П. Выбрать произвольное натуральное число 1. П1. Положить й = О.
Ос н о в н о й ци к л. 1Ч. Вычислить шаговый множитель рл и параметры 6», я», удовлетворяющие условиям теоремы 1'. Ч. Если выполняется неравенство шах1 (х")(О, 1<гав то положить»» — — О и перейти к шагу ЧП; иначе перейти к шагу Ч1,. 418 Ч1. Вычислить индекс (Е(1: т), удовлетворяющий условию 1,(х") = шах 1,(х»), !<пал положить ч» = 1 и перейти к шагу УП.
ЧП. Вычислить реализацию х» случайной точки, равномерно распределенной в и-мерном кубе с центром в точке х» и стороной а». ЧП1. Вычислить вектор -«1«» (» + ~»е ) 1«» (»») а» Э 1 ! где е', 1 = 1, ..., и — 1-й орт. 1Х. Если й» 1, то вычислить вектор й»= Х й' и перейти к шагу Х; иначе вычислить вектор й» по формуле 1» ~~ 9' О и перейти к шагу Х. Х. Вычислить следующее приближение х»+' = пх, (х» — р„й»). Х1.
Положить й = й + 1 и перейти к шагу 1Ч. Теорема 1'. Если выполнены предположения 1 и условия ° Ф р» ~ О, й = О, 1, ..., ~ р» — †, ~« р~~ ( ао; »=о »-о с»»,аО, й = О, 1, ...; б»1а» 0 при й-»-оо, а»-»О при А- оо, то с вероятностью 1 существует подпоследовательность (х»),. » последовательности (х»)» ь, порожденной алгоритмом 1, такая, что 1!гп!»(х О ппп~»(х). «ех Если, кроме того, !» — строго выпуклая функция, то с вероят. пастью 1 1ппх» = х*, где ~,(х') = пп(пГ»(х), х'ЕХ. «ях 14» 419 2. Стохаатячаааая аааача Задача 2. Найти агдгп!п КР,(х, в) (КГ,(х, в)~~ Р,(х, в)р(5(в)) ках Я для заданной функции Ра ~ Х х й -~ В' и заданного множества Х с В'.
предположения 2. (1) — функция га — непрерывно дифференцируема и выпукла вниз в области Х; (И) — Х вЂ” выпуклое и замкнутое множество. В приводимом непоисковом алгоритме адаптивного управления на й-й (А ~ р,) итерации делается только одно измерение (вычисление) функции Р,. Лля вычисления направления движения р к следующему приближению ха+' используется известная информация из р, (р,л 1) предыдущих итераций Р= ~ —,' (Р,('+Л,В', ') — Р,(х '+Л,в ',в-'))О*, 5 а — р„+~ 5 где Ь„) О; (О*) а, — серия независимых наблюдений случайного вектора 0 с независимыми и равномерно распределенными на ! — 1, 11 компонентами.
Алгориаам 2 Н а ч а л о. 1. Выбрать начальное значение параметра р„удовлетворяющее условиям теоремы 2. П. Найти1 начальные точки ха, й = О, 1, ..., р„принадлежащие множеству Х; векторы 0", й = О, 1, ..., р, — серию независимых наблюдений случайного вектора 0 с независимыми и равномерно распределенными на отрезке 1 — 1, 11 компонентами; реализации ва, й = О, 1,, ра случайного события в.
111. Задать смещения Л„А = О, 1, ..., р„удовлетворяющие условиям теоремы 2. 1Ч. Положить й = р,. Ос н о в н о й ци к л. Ч. Вычислить параметр р„и вектор Р = ', —,' (Р,(х'+ Л50', в') — Ра(х'-'+ Л,,В'-', в-')) В'. 5 А — о .5-~ Ч1. Вычислить шаговый множитель р» н нормирующий множитель ум удовлетворяющие условиям теоремы 2.
Ч11. Вычислить следующее приближение х'+' = пх( ' — ркуар). Ч111. Найти независимое наблюдение ва Ы случайного вектора 0 с независимыми и равномерно распределенными на отрезке 1 — 1, 11 компонентами. 1Х. Найти реализацию в'+' случайного события в, 420 Х. Найти смещение Л»+ь удовлетворяющее условиям теоремы 2. Х1. Положить я = й + 1 и перейти к шагу Ч.
Теорема 2. Пусть выполнены предположения 2 и имеют место условия: (!) — градиент функции 1» удовлетворяет глобальному условию Лапши»[а, т. е. при х, у ~ Е" ))71»(т) — т)з(У)))~(сс,)Х вЂ” У)), а,(оо; (П) — известна величина р» такая, что Е( ~„'ЦР,( +й»О', ')— 1,~-» — к»+1 — Е„(х'-'+Л,,Е'-', '-'))О'))'1х '+', ..., )<К<0()< при )) х*)) (т( со, з й — р», ..., я; (»и) — нормирующий множитель у» удовлетворяет условию 0(7 < т»()х»))+ ия») у < '! ([о) — величина й», р» и р» такие, что 1(р»(сс <оо, я — р» ВО, р» ВО, Ь»)0; р»~0, Ь»-эО при й — «оо; кк л' Р»й» вЂ” и -»1(оо 1 (Р»1»»)'< оо. »~Ра » » о Тогда последовательность случайных точек '(х» (сь))» е, порожденная алгоритмом 2, является случайной квазифейеровской относительна множества решений Хе задачи 2.
Если, кроме того, выполняется условие (о) — ~; р»= оо, то почти » о для каждого св последовшпельность (х» (со))~ е сходится к решению задачи 2. Библиографические укпзанил. Пункт ! написан нз ссноввнии работ [96, 97, 308, 309, 379, 380[, пункт 2 основан нз результатах работы [53!. 5.31. Примой метод решения задач етокаетичесиого программирования 3 ада ча 1. Найти агдтп[п Ео[е (х, со) для заданной функции кех 1»: Е" Х й -ь Е' и заданного множества Х = (х)Е„1;(х, св)(0, ! = 1, ..., т, х~Х'), где Х' — некоторое множество пространства В". Предположения 1. (з) — Х' — выпуклое, замкнутое н ограниченное множество; (й) — Е„); (х, со), 1 = О, 1, ..., т — непрерывные, 'выпуклые вниз функции. Алеоритл» ! Н а ч а л о.
1. Выбрать произвольное начальное приближение хор Е"; произвольные числа г~в, 1 = 1, ..., т; достаточно большую константу 6 ) О. П. Положить я = О. Ос н о в ной ци кл. П1. Найти шаговый множитель р» и множитель а», удовлетворяющие условиям теоремы 1. 1Ч. Если выполняется условие шах г,'.(О, ~<!<а ' то положить ! = О и перейти к шагу Ч1; иначе перейти к шагу Ч. Ч. Найти индекс /Е [1: т), удовлетворяющий условию г'= шах г'. ~чаи~ Ч1.
Вычислить реализацию Р случайного вектора 3», для которого Ее (Р/х», г», ..., х", ") = Чф~ (х»), где Чф, (х') — обобщенный градиент функции ф/ (х) Й Е4/ (х, ь») в точке х = х'. ЧП. Вычислить следующее приближение »+' = (х» — рД'). ЧП1. Найти случайные величины 0»и 1 1, ..., т, для которых Е(0»/х», г», ..., х», г») = Ео/,(х~, о»), 1 ~ 1, ..., т. 1Х.
Положить 1 1. Х. Если выполняется неравенство !г»,+а»(0» — г») !(6, то положить г»+' = г» + а„(0» — г») и перейти к шагу Х1; иначе положить г",+' = (бг,'. + 6а, (О,'. — г»»))/) г,'. + а, (О,' — ф ( и перейти к шагу Х1. Х1. Если 1 ( т, то положить 1 = 1+ 1 и перейти к шагу Х; иначе перейти к шагу ХП. ХП.
Положить й = я + 1 и перейти к шагу П1. Теорема !. Если выполнены предположения 1 и, кроме того: (111) — область )', определяемая ограничениями Щ,(х, а)(О, 1=* 1, ..., т, удовлетворяет условию Слейтера/ (1о)— Р СО ~ р» = оо, ~ р'(оо, р»/а»-»-О при й-~со; »=О ь (е)— Е(О!)<б(оо, 1= 1, ..., т, при И = О, 1, ...; (о()— Е(9»!»(б<со при И=О, 1, ..., то с вероятностью 1 одна из предельных точек последовательности (х»)»..о, порожденной алгоритмом 1, принадлежит множеству решений задачи 1. Если Ега (х, со) — строго выпуклая вниз функция, то с вероятностью 1 !пп х' *= х', где х* — решение задачи 1. Замечание 1. Если функции 1, (х, в), ! = О, 1, ..., т, при каж- дом в выпуклые вниз, то на шаге Ч! алгоритма 1 можно взять $»= ч1;(х», в"), а на шаге ЧН!— Е =~,(х», в»), 1=1, ..., т, где 7~~(х', в') — обобщенный градиент функции 11(х, в) по х; в" — независимые наблюдения состояния природы.
Библисгри4>ические указания. Прн написании параграфа использовались ра боты [92, 97!. 5.32. Метод случайного поиска в выпуклых задачах минимизации 3 а д а ч а 1. Найти агд ппп 1а (х) для заданной функции авк 1» . Е" -ь 3Р и заданного множества Х ~ Е". Предположения 1. (а) — функция 1» (х) — выпукла и непрерывно дифференцируема на множестве Х; (٠— градиент функции 1а (х) удовлетворяет на Х условию Липшица е константой О ( у ( <оо, т.
е. 0Ч!а(х) — ЧР»(у)((у(х — у$$, Ух, усХ; (!11) — множество Х вЂ” выпукло и замкнуто. В методе случайного поиска на И-й итерации по известному приближению х» Е Х вычисляется следующее приближение х»-~', как точка в некотором смысле близкая к точке минимума функции 1 ( ) на отрезке прямой х» — рИ» (р ~ ( — оо, оо)), принадлежащем множеству Х, где И" — независимая реализация единичного случайного вектора, равномерно распределенного на единичной сфере с центром в начале координат. Для вычисления шагового множителя р» необходимо применять конечное число итераций какого-нибудь алгоритма одномерной оптимизации, 423 Алгоритм 1 Н а,ч а л о. 1.
Выбрать произвольное начальное приближение «ач Х П. Положить й = О. Ос но в н о й п,и к л. П1. Если т1)о (х") = О, то положить «о= х" и прекратить вычисления; иначе перейти к шагу 1Ч, 1Ч. Найти независимую реализацию )та единичного случайного вектора 9, равномерно распределенного на единичной и-мерной сфе- ре с центром в начале координат. Ч. Если множество 1. (р~х — р7о«ЕХ, рб( —, )), содержит хотя бы одну точку р ~ О, то перейти к шагу Ч1; иначе положить х"+' = х' и перейти к шагу ЧШ. Ч1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
