И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 74
Текст из файла (страница 74)
Теорема 1'. Пусть выполняется предположение 1, условия (11), (1о) теоремы 1 и пусть, кроме того, (о) — множество )'» — ограничено; (о() — управляющая последовательность (6ь) г е такова, что бь)0, А=О, 1, ..., 11шбь=О. ь»» Тогда для произвольного у' Е В последовательности (х")г о, (у")Г о, порожденные алгоритмом 1, таковы, что ш!и!! уь — у*))-»-О, А — ~- оо; е" ег" )пп ~; (х') ~ О, 1 = 1, ..., т; !пи 1,(х") = о, й~» где о — экстремальное значение задачи 1. воо Для выполнения условий (В), (о) теоремы достаточно, чтобы выполнялось условие Слейтера для задачи !. Зилгечаиия.
В работе (549! частичные случаи приведенных выше теорем получены для модифицированной функции Лагранжа при г; ($) = (у/2) $т. 2. Даойетаоаный алгоритм поромоивой мотрикм 3 а д а ч а 2. Найти агд ппп Уо (х) для заданной функции «Ех уо: В" о- В' и множества Х=(х)ду(х)о О, у=1, ..., гп, у;(х)=0, 1=1, ..., у, хЕВ ) гдеду.В"- В', 1=1, ..., пт;у;:В"-оВ', 1=1, ..., у, В дальнейшем будем обозначать д(х) = (и, (х), ..., и (х)), у (х) = (у, (х), ..., у, (х)). Предположение 2. (г) — существует тройка Куна — Таккера хо = (х*, и*, о*) задачи 2; (В) — функции У; (х), 1 = 1, ..., 1 и и; (х), у = 1, ...,гп, имеют непрерывные по Липшицу вторые производные в окрестности точки х*. Определение 2.
Тройка Куна — Таккера хо= (хо, и*, о*)задачи 2 удовлетворяет условиям единственности якобиана, если выполня ются одновременно следующие условия: а) и;)О, если уЕИЬ(у(д;(хо)=0); б) векторы Чду (х'), у Е И, Чу, (х'), у = 1, ..., 1 — линейно- независимы; в) для каждого ненулевого вектора у, удовлетворяющего равенствам ргЧй;(х*) = О, Чу СО; угу,(хо)=0, 1=1, ..., У, выполнено р Ч««Ч(ео)р)0, где Ч~„~р (хо) — матрица вторых производных по х функции Лаг- ранжа ~р (е) = уо (х) + игуг (х) + игу (х), е = (х, и, о), вычисленная в точке е*= (х*, и*, о*). Алгоритм 2 Н а ч а л о.
1. Выбрать начальное приближение го= (хо, ио оо) Е В"~~~ для тройки Куна — Таккера е' = (хо, и*, о') задачи 2. 11. Выбрать начальное приближение Ао для матрицы, обратной к гессиану функции Лагранжа задачи 2, вычисленному в точке хо, 401 1П. Положить й = О. Ос но в но й ц и к л. 1Ч. Найти ближайшую точку Куна— Таккера (и'+', о»-»)) для задачи квадратичного программирования ага ппп ~ — (Ч]»(х») + Чд(х») и+ Ч) (х») о) А»(Ч)»(х») + )»м ) + Чд(х') и+ Ч[(х') о) — игу (х") — от[(х»)1 (в.вв) при ограничении и) О. Ч. Вычислить вектор х"+' = х' — А, [Ч(» (х') + Чу (х') и"+' + Ч[' (х») о»+') и положить г»+' = (х"+', и"+', о"+'). Ч1. Вычислить матрицу А»+), положить й = й + 1 и перейти к шагу 1Ч. Теорема 2.
Пусть выполняются предположения 2 и ((и) — тройка Куна — Таккера г»= (х', и», о») удовлетворяет условию единственности якобиана; (и)) — матрица Ч~,~р (г») в)порых производных оо х функции Лагранжа задачи 2 неособенная. Тогда для любого а~ (О, 1) существуют два положительных числа е (а) и б (а) таких, ипо если [](х", и', о') — г'[[( е (а) и А» — симметричная и х п-матрица, удовлетворяюиу)я неравенству [[А» — [Ч',„)р (г')] '[[( й (а), пю существует решение (и'+', о»+') задачи (5.94] такое, что -ближайшая к (х", и", о») точка (х"+', и»+', о»+') удовлетворяет неравенству [(х~+), и"+', о"+') — г*[[ ( а[[(х», и", о') — г~[.
Теорема 2'. Пусть выполнены все предположения теоремы 2 и пусть [з»]»=» — последовательность положшпельных чисел, удов- летворяющая условшо з„( й, й = О, 1, ..., з».~) > з». Если в алгоритме 2 г) достаточно близко к г» и [ А, — [Ч»»ц)(г ')] [:~ ~[[», еде [[[»]ь=ь — последовательность неотрицательных чисел, огра- ниченная достаточно малым числом, то последовательность [г»]» ы порождаемая алгоршпмом 2, существует и сходится к г» по крайней мере с линейной скоростью.
Если, кроме того, з»-). ао и [1»-» О при й -~ оо, то (г»]» ь сходится к г* по крайней мере сверхлинейно. Теорема 2". Пусть вьаюлняются предположения 2 и начальная точка г' и начальная матрица А, достаточно близки к г» и Ч„',)р (г») соответственно. Тогда, если в алгоритме 2 матрицы А«+т, й = О, 1, ..., вычислять ло рекуррентной 4ормуле (й А «)Ьт-1-Л(й Л у)т ут(й А«у)ййт А«ф! = А«+ йт й« (Ь У)' й = О, 1, ..., Если дополнительно предполагать, что матрица Ч„'„ф (гз) положительно определенная, то теорема 2" справедлива для алгоритма 2, в котором матрицы А«+!, й = О, 1, ..., вычисляются по следующей рекуррентной формуле А А (Ь вЂ” А«У) У +У(Ь вЂ” А«У) У (й — А«У) УУ «+! = « [- У У (У~У) й = О, 1, .... Био«неера(йнзескне унлззннл.
Пункт ! оснозан на результатах работы [871, прн напнсанкн пункта 2 нспользоззлнсь работы [488, 4901. 6.27. Глобально сходящийся метод Найти агдш[п~з(х) для заданной функциза зех Задача 1. 1, ! В"~- В' и множества Х= (х[~((х)(0, ~ =1, ..., яз, хрВ"), где 7) . Вз -э В', 1' = 1, ..., лз. Предположения 1. («) — функция (з (х) ограничена снизу в В"; (И) — функции Г! (х), ( = О, 1, ..., и — непрерывнодифференцируемы в В"; (ззз) — функции Д! (х), 1 = 1, ..., т — выпуклы.
В приводимом здесь методе на Ьй итерации для определения направления движения к следующему приближению х"+' решается 403 где й = х«+' — х"; у = Ч„!р(х"+', и"+', о"+') — Ч,'ф(х«, и«+', о"+'), то последовательность (г«) «" з, генерируемая алгоритмом 2. суи(еппвует и сходится сверхлинейно к г' Замечание 2. В [490[ отмечается, что локальная сверхлинейнаи сходимость может быть достигнута также в случае, когда матрицы А«ф! вычислять по одной из следующих формул: А„„УТА Ьйт А«+! =А«т ' [- т у А«у йту А „(Ь вЂ” А«у) Ь + Ь (Ь вЂ” А«У) «+1 '!« + 2«т ! (5.95) 2« у А А (й — А«У) У +У(й — А«У) «+! — — «+ т 2У у некоторая вспомогательная задача квадратичного программирования, а для определения шагового множителя решается (приближенно) задача одномерной условной минимизации.
Алгоритм 1 Н а ч а л о. 1. Выбрать произвольное начальное приближение хл Е Л". П. Выбрать произвольную последовательность (е»]».л такую, что е,) О, й О, 1, ..., ~~„е» ( оо. »=о П1. Выбрать произвольные константы а ) 0 и б ) О. 1Ч. Определить функцию др (х) = 1о (х) + а Х ]11 (х)]+, 1 1 где (о]». = тах (О, о). Ч. Положить й = О. Ос но в н о й ц и к л.
Ч1. Найти матрицу Н„удовлетворяющую условию (гб) теоремы 1. ЧП. Вычислить решение й» следующей задачи квадратичного программирования: найти агйт1п ~(71»(х»), й) -]- 1 (Н,й, й)~ при ограничениях 1;(х»)+(Ч1 (х»), й)(0, 1= 1...,, т. Ч1П. Вычислить шаговый множитель р»Е (О, б], удовлетворяющий неравенству Ка (х +р»й ) ~( т1п уа (х» + рй») + е». скр<ь 1Х. Вычислить следующее приближение х»+' = х»+ р,й».
Х. Положить й = й + 1 и перейть к шагу Ч1. Теорема 1. Пусть выполняются предположения 1 и (1о) — множество Х компактно; (о) — множество ХР~(х]1;(х)(0, 1= 1, ..., т, ХЕВ") — непусто; (о1) — существуют положительныг числа ])1 и р» такие, что для каждого й ~ 0 и для любого х е Л" выполняется (),]]х]]' ((Н„х, х) ( р»]] х]-. Тогда для любого начального приближения х' Е В" существует положительное число а такое, что если в алгоритме 1 константу а выбрать из условия а ~ тах (а, 1), 404 то предельные точки последовательности (х»)»=о, порожденной алгоритмом 1, являются точками Куна — Таккера задачи 1. Библиографические указании Параграф написан на сено»анни работы [4891.
5.28. Стохастические квазиградиеитные методы 3 а да ч а О. Найти агд ппп 1» для заданной функции 1»: В" -~ «ЯХ ~ 1»! и заданного множества Х с: П". Предположения О, (а) — функция )а выпукла вниз; (П) — мно- жество Х выпукло и замкнуто. Стохастические квазиградиентные методы применяются для ре- шения задач оптимизации, в которых нет достаточно полной инфор- мации о функциях цели, функциях ограничений и их производных. Эти методы основаны на понятии стохастического квазиградиен- та — случайного вектора в», удовлетворяющего равенству Е ($»1ха, ..., х») = с»Я (х ) + [з», где ос» — неотрицательная случайная величина, Ь» — случайный вектор, измеримые относительно о-подалгебры, индуцированнойсе- мейством случайных величин (хо, ..., х"); 71» (х") — обобщенный градиент функции 1» в точке х». Приведем примеры вычисления стохастических квазиградиен- тов для функции 1».
Пример 1. Пусть функция 1» (х) имеет ограниченные вторые производные. Рассмотрим вектор 8 = (В„..., В„) с независимыми и равномерно распределенными на ( — 1, 11 компонентами. Тогда вектор стохастического квазиградиента в й-й итерации можно вы- числять по формуле чп 1«(«»+а»В~') 1»(«») н»л Ь» ! «1 (де В", з = 1, ..., з» вЂ” серия независимых наблюдений В й-й итерации, причем в»~ 1; Ь» О. Если случайные величины в», Ь» измеримы относительно о-подалгебры бВ„ индуцированной величинами ха, ..., х", то условное математическое ожидание такого вектора равно Е(Р1х') - '3 Ц,(х»)+ о"Л„, Г е о" — некоторый случайный вектор, измеримый относительно Ф, ~ о" ( ~ сопз1. Пример 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
