И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 63
Текст из файла (страница 63)
Замечание 6. Если существует конструктивный способ вычисления почти градиента функции !о в каждой точке х, то на шаге 1Ч алгоритма 5 следует вычислить д (х«) — почти градиент функции /о в точке х«, и на шаге ЧП вектор г'+' вычислять по формуле г'»с = г«+ а«(д(х«) — г»). 6. Авалег метода лввеарваации в отохаетичееввх еадачах миввмиаацвв почта диффереицируемых фуивций 3 ада ч а 6. Найти ага ппп Кго (х, со) для заданной функции кох г"о: Х м й -о В' и заданного множества Х с: В (Вго (х, о») ~1 Ь ) го (х, со) р (с(о»); мера р может быть неизвестной). Предположения 6.
(») — функция го (х, со) в некоторой области Х'~ Х удовлетворяет по х условию Липшица с константой у (со); (И) — Х вЂ” выпуклое, ограниченное и замкнутое мсожество, образованное неравенствами !/(х)(0, !=1, ..., т, где !с с В"-» В', / = 1, ..., т — выпуклые функции. Алгоритм 6 Н а ч ало. 1. Задать: начальные приближения х'Е Х, г'~ ~ В"„начальные значения шатовых множителей р, (0), р, (0) и величину смещения б„удовлетворяющие условиям теоремы 6. П. Положить й = О.
Основной цикл. П1. Вычислитьхс,»=1,...,п — независимые случайные величины, равномерно распределенные на отрезках х« — — х«+ — 1 с* 1 ... и. 6« 6,1 с 2 ' с з~' 1Ч. Вычислить вектор « $(хь, й) = -6 — ~ [Рс (х~ ° °, х~ + 3 ° ° х ы )— где гс' — независимые по й наблюдения параметра ы, Ф вЂ” 1-й орт. Ч. Вычислить вектор у' Е Х, удовлетворяющий условию (г", у') = ппп(г", х). «ЯХ Ч1. Вычислить вектор хе+' = хл — р, (й) (хс — ус). Ч11.
Вычислить вектор е'+' = г" + р,(й) ($(х', й) — г'). ЧП1. Вычислить значения шаговых множителей р, (й + 1), р, (й + 1) и смещение бььь удовлетворяющие условиям теоремы 6. 1Х. Положить й = й + 1 и перейти к шагу П1. Теорема б. Пусть выполнены предположения б и, кроме того, имеют место условия Ву'(тс) < ж 0«р,(й) ~1, бт) 0 при й = О, 1, ...; ° О ~, р,(й) = оо, р,(й)/рт(й)6,-~0 при й-~-оо; ь-с Х (р (й)А)'<, Е,р',(й)<ж !бс — бл+~(/р (й)-~0 и бс-э 0 при й-«оо.
Тогда с вероятностью 1 предельные точки последовательности (хь)Г=с, порожденной алгоритмом б, принадлежат множеству Хс решений задачи б и последовательность (1с (х'))с=с почти наверное сходится. ?. Стсллстлчсслвй метод лмлссриэацли 3 а д а ч а 7. Найти аги ппп 1с (х), 1с: В"-«В', Х с: В". «ех Предположения 7.
(1) — функция 1с — непрерывно дифференцнруемая; (И) — множество Х ~ В" — ограничено и замкнуто. Если множество Х имеет не простой вид (например, Х не является п-мерным параллелепипедом), то решение задачи 7 с использованием операции проектирования на область Х требует эффективных способов решения задачи минимизации суммы квадратов прн наличии ограничений, что не всегда возможно, 337 В стохастическом методе линеаризации обычная операция йроектнровання на множество Х заменяется операцией (иногда более простой, чем проектирование) минимизации на Х линейной функции (г", х), определяемой некоторым вспомогательным вентором г".
Обозначим через л выпуклое, ограниченное и замкнутое множество, для которого Е ~ ( Ч1, (х) ~ х с Хо), где Хо — множество решений задачи 7. Алгоритм 7 Н а ч а л о. 1. Выбрать произвольные начальные точки х' ~ ЕХ.и гонг. П. Задать правила построения последовательностей шаговых множителей (р»)Г» и (6»)Г». П1. Положить й О. О с н о в н о й ц и к л. 1Ч.
Вычислить вектор х», удовлезворяющий условию (г", х") ш1п(г", х). »ЯХ Ч. Вычислить вектор х»+' хо + р» (х» — х'). Ч1. Найти случайный вектор $о, условное математическое ожидание которого Е($»/(хо, г'), ..., (х», г»)) = Ч1»(х»)+ 6», где Ь» — вектор, измеримый относительно о-алгебры, индуцированной величинами (х', го), ..., (х", г"). Способы построения вектора $» приведены в примерах к й 6.28. ЧП. Вычислить вектор г'+' - пг(г" + 6»(Р— з")).
ЧП1. Положить й * й+ 1 и перейти к шагу 1Ч. Теорема 7. Пусть имеют место предположения 7 и пусть, кроме того, Ч1, (х) удовлетворяет локальному условию Лиаоиио(а. Тогда, если вьсоолнены условия Щ+(Ч1»( )1+16" 1<с„,< р ~0, 6 ~0, р»/6»-о 0 при й-»оо; ~ 6, -, ~; р„~Ь»!< о-о »=о » о 2 Е(р»+6») <-, »-о 338 то последовательность (х»)»=с, порожденная алгоритмом 7, такова, что (7» (х»))»~ сходится и. и и каждая предельная точка (х»)»=с принадлежит множеству Х' = (х*(ппп(Ч1,(хе), х — х*) = О). «ех Библиографические укеазяия. Пункты 1, 2, 3, 4 написаны на основании работ 1320, 315, 2931, пункгы 5, 6 — на результатах работы 11551, пункт 7 — на основании работ 1153, 99, 2141.
5.12. Методы линеаризации в предельных экстремальных задачах 1. Детерынннрованнь»й случай 3 а д а ч а 1. Найти ага ппп 7е (х), где !е (х) Ь 1! гп Щ (х); !е: В" -+ «ех » е -ь Л', й = О, 1, ... — заданные функции, Х с: Л". Предположения !. (1) — функции !о, й = О, 1, ..., имеют непрерывные производные; (11) — Х вЂ” выпуклое, ограниченное, замкнутое множество. Сущность метода состоит в том, что для минимизации функции уе в я-й итерации используется вектор Чуе (х») — градиент функции !ео, причем операция проектирования на множество Х заменена задачей минимизации линейного функционала (Ч~~ (х»), х) пох на множестве Х. Особенность данного метода состоит в том, что сама минимизируемая функция !е может и не иметь непрерывных производных.
Определение!. Множеством решений задачи 1 называется множество Х*, элементы которого обладают следующим свойством: ху б Х', если существует последовательность точек у» — ехе при я — ~- оо такая, что ш!п(Ч!», (у'), х — у')- О при А-»-оо. «ях Если функция 7е выпуклая вниз и последовательность выпуклых вниз функций !е удовлетворяет соотношению 1о (х) е ге (х) для каждой точки х ~ Х, то множество Х', определенное выше, состоит из точек минимума функции уе ( ). Алгоритм ! Н а ч а л о. 1.
Найти произвольную точку х', принадлежащую множеству Х. П. Задать р,. П1. Положить я = О. Ос но в но й цикл. 1Ч. Найти вектор х»~ Х вЂ” решение задачи минимизации линейной функции (Ч!е (х"), х) на множестве 339 Х, т. е (Ч/»»(х»), х») = ппп(Ч/»» (х"), х). «ях Н. Вычислить вектор х" ~' = х» — р» (х» — х'). Н1. Вычислить шаговый множитель р»+ь удовлетворяющий условиям теоремы 1.
НП. Положить й = й+ 1 и перейти к шагу 1Н. Теорема 1. Пусть выполнены предположения 1 и, кроме того, имеют место условия: (1) — последовательность функций /»»и й =* = О, 1, ..., сходится к функции /» равномерно в области Х', (й)— (ф+' (х) — /ь» (х) ( < а,о», где а» = сопз1, о»-«+О при й- оо, хЕХ; (И1)— !Ч/»» (х) — Ч/ь» (у) ((» а» ((х — у )(/Ь», гдв а,= сопз1, Ь» -«+О при й -«оо, х, у Е Х.
Тогда, если шаговые множители р», й = О, 1, ..., выбирать такими, что р» -«+ О, о»/р»-«О, р»/Л» -«О при й -«оо «« и ~„'р» = оо, то каждая предельная точка последовшпельности »-о (х»)» ~, порожденной алгоритмом 1, принадлежит множеству решений Х* задачи 1 и последовательность (/» (х»))»=л сходится. Теорема 1'. Пусть выполнены предположения 1, условия (1), (11) теоремы 1 и, кроме того, имеют место условия: (»') — функция /» — непрерывно дифференцируема; (1У)— ПЧ»» (х) — ~Ч," (уИ» Р» Р— у Ь где константы и», й = О, 1, ..., ограничены в совокупности; х, у й ЕХ. Тогда, если ии»говые множители р», й = О, 1, ..., выбирать такими, что р» — «+ О, о»/р»-«О прн й-«оо; Х р»- »-о то каждая предельная точка последовательности (х»)ь.ь, порожденной алгоритмом 1, принадлежит множеству решений Х* задачи 1 и последовательность (/» (х»))ь=ь сходится.
340 Замечание 1. Для выпуклых в ограниченной области Х функций !о 1о, й = О, 1, ..., теорема 1 и теорема 1' остаются в силе и в том случае, когда последовательность функций (о (х) -»- 1» (х) при й -»- оо поточечно. а. Стохаотвчоокяй олучай 3 а д а ч а 2. Найти агнппп1ппЕР»(х, о») «ох» о для заданной последовательности функций (Р»)»=о, Р»: Х х Х»1 -» Е» и заданного множества Х с: Е", Предположения 2. (») — функции го (х) Й ЕР» (х, о»), й = О, 1, ...— непрерывно дифференцируемы; (!1) — Х вЂ” выпуклое, огра- ниченное, замкнутое множество.
Сущность метода заключается в том, что для минимизации функ- ции го (х) Е~ 1пп ф (х) на я-й итерации используются стохастические квазиградненты функций го, т. е. векторы К условное математи- ческое ожидание которых Е Д~(Й») = Чо» (х») + Ь», где Ь» — векторы, измеримые относительно а-подалгебры Й» (в частности, можно положить а» = Ч,Р»(х», «о)). В данном методе операция проектирования на множество Х заме- нена задачей минимизации линейной функции (г», х) по х б Х, где векторы г» «близки» к градиенту минимизируемой функции. Алгоритм 2 Н а ч а л о. 1. Найти х', го — произвольные точки выпуклого, ограниченного, замкнутого множества Х.
П. Задать начальные значения шаговых множителей р, (О) и р, (О). П1. Положить й = О. О с н о в н о й ц и к л. 1У. Найти вектор х» б Х вЂ” решение задачи минимизации линейной функции (г', х) на множестве Х, т. е. (г», х») = ппп (г», х). «ях Ч. Вычислить вектор х»+' = х» — р, (я) (х» — х»). Ч1, Найти одну реализацию $» случайного вектора а», условное математическое ожидание которого Е$'lхо, го, ..., х", г') Ч~о(х")+Ь', 34! где случайный вектор Ь" предполагается измеримым относительно о-подалгебры, индуцированной величинами (х', гь, ..., х", г").
ЧП. Найти вектор г + = г — рг (А) (г — ь"). ЧП1. Найти шаговые множители р, (й + 1) и р, (й + 1), уловлетворяющие условиям теоремы 2. 1Х. Положить й = й + 1 и перейти к шагу 17. Теорема 2. Пусть выполнены предположения 2 и, кроме того, имеют место условия: (1) — последовательность функций 1о (х) сходится к функции 1ь (х) равномерно в области Х; (11) —.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
