И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 33
Текст из файла (страница 33)
Тогда существует подпоследовательность (х» ( -ю последовательности (х»(~ о, порожденной алгоритмом 2, стремящаяся к точке хее Хе~ (х" ( 0 Е О (х»Ц. Био«ивера(»ические даиания. При написании параграфа испольаованы работы 193, 97, 102, 100, 1011. Дополнительные сведения о мииимнввцин функций, удовлетворяющих усло. вию Лившица, можно найти в работе 14331.
8.9. Метод усреднения направлений спуска для минимизации функций, удовлетворяюшик условию Липшица Задача 1. Найти агйш(пуе(х) для заданной функции «сн" 1е ° и Предположение 1. Функция (е удовлетворяет локальному усло- вию Липшица. Алгоритм 1 Н а ч а л о. 1. Выбрать произвольное начальное приближение хе Я 11". П. Выбрать произвольное натуральное число 1.
П1. Положить й = О. Основной цикл. 1Ч. Найти шаговый множитель р», параметры а, и б„, удовлетворяющие условиям теоремы 1. Ч. Вычислить реализацию х» случайной точки, равномерно распределенной в и-мерном кубе с центром в точке х» и стороной а». Ч1. Вычислить вектор 8» по формуле о Ъ' )о (л'+ 6Ф) — 1« («") 6 е, ь1 » где е', 1 = 1, ..., и, !-й орт. Ч11. Если й ~ 1, то вычислить следуюшее приближение х"+' = х» — р» ~„'8' у»-4 и перейти к шагу ЧЦ1; иначе вычислить следующее приближение х'+' по формуле х"+' = ха — рь 1', О/ га и перейти к шагу Ч111.
ЧП1. Положить й = й -!- 1 и перейти к шагу 1Ч. Теорема 1. Если функция /а удовлетворяет локальному условию Липитица и выполняются условия . р,~о, „~О, й=О, 1, ...,; 00 М ~ Р„= оо, ~ Раа(оо, 11ш(Ра/аь) = О; ь~ь а-о " ь- 1ппсс, = О, !пп(б„/аа) = О, !!ш(рь/ра» ~)(оо; ь м а-и а' 1пп ((ссь — аь~ы (/рь) = О, 1пп (аь» т/а ) = 1, а А а то все предельные точки последовательности (х")а о, порожденной алгоритмом 1, с вероятностью 1 принадлежат множеству Ха(х (ха ( О ~ 6 (х')), где 6 (х) — множество обоби(енных почти градиентов функции Дь в точке х, и, кроме того, последовательность Д (хь))Г о сходится почти наверное.
Библиографические указания. При иаписаиии параграфа испольаоаались работы [96, 97!. 3.10. Конечно-равностньтй метод мнннмнаацнн раврьтвньтх функций Задача 1. Найти аги ш(п /и (х) для разрывной функции кян т'о 11 ь аа ° Предположения 1. Функция /а.' (1) непрерывная и дифференцируемая почти всюду; (Щ ограничена в любой ограниченной области В"; (1И) полунепрерывная снизу, т. е.
если (ха)ь ь — произвольная последовательность точек, сходящихся к х, и предел последовательности (/а (х'))Г а существует, то !пп /а (х') ь Да (х). Определение 1. Точка ха является (квази) решением задачи 1, если ха~ Х*Ь (х ( О Е со 3 (х)), где Я (х) — множество предельных точек последовательности векторов, 1-я компонента которых здесь (х»)~ 2 — произвольная последовательность точек, сходя- щаяся к х, а (е»)Г=о — произвольная последовательность, схо- дящаяся к О. Основная идея метода состоит в том, что разрывная и негладкая функция /» ( ) приближается последовательностью непрерывных сглаженных функций / (, й), которые, за исключением точек раз- рыва, сходятся к/» ( ) при а -л- оо. За направление движения к сле- дующему приближению х»+' в /2-й итерации выбирается случай- ный вектор, который является статистической оценкой градиента сглаженной функции.
Функцию 7(, /2) можно определить как а» а» «,+— 2 «+ л 2 /(х,й)= — „'. ) ." ~ /(Н,й)Арм".,А., а» а» а» к,— 2 « л 2 где (а»)» о — последовательность положительных чисел, стремя- щихся к нулю; /(у, й) определяется по правилу а» а «+ — «+в 2 л 2 Ь, «)= — „'. ~ ". ~ /.(1„..., /.) и„..., ж„.
а» а» а, гл 2 У л 2 Алгоритм 1 Н а ч а л о. 1. Выбрать произвольное начальное приближение х' ~ Я", шаговый множитель р, и смещение и„удовлетворяющие условиям теоремы 1. П. Положить и = О. Основ ной ци кл. 1П. Вычислить реализации = 1, ..., л, независимых случайных величин то 1 = 1, ..., и, рав- номерно распределенных на отрезках ( — и»/2, а»/2). 1Ч. Вычислить » -»» Ь=Ь+лч, 1=1, ..., л, где $с, т2, 1 = 1, ..., л — соответственно реализации независи- мых случайных величин Ко то ! = 1, ..., л, равномерно распреде- ленных на отрезках [ — а»/2, а»/2). Ч. Вычислить следующее приближение х»+1 — л» о» ~. (/ х» + ~» х» + т» + 2 ' '''' " ~// где г', 1 = 1, ...', и — '!-й орт.
!66 Ч1. Вычислить значение шагового множителя ра+~ и значение смещения аа+„удовлетворяющие условиям теоремы 1. ЧП. Положить й = й + 1 и перейти к шагу П1. Теорема 1, Пусть выполнены предположеиия 1 и, кроме того, имгют место условия Е Ра = °, Х (Р.7а',)'( К1 а-о (аа — аь+, 1 "+ -«О, а -»О при й-» оо. аара Тогда с вероятностью 1 существует подпоследовательность (ха )„о последовательности (ха)~-о, порожденной алгоритмом 1, стремящаяся к точке х«~ Ха, для которой 1!шЧ7'(х~а, й ) = О. а о« Библиографические укиэокиа.
При написании параграфа испольаоааиы работы 1103, 971. 3.11. Метод линеарнзации решении дискретных мииимаксных задач 3 а д а ч а 1. Найти агд ш!п )а (х), где «яаа га (х) ~ шах ~, (х), ми< здесь ~, (х) — заданные непрерывно дифференцируемые функции. Обозначим через б1ь(х) множество (1( 1 ( ! ~; т, 7, (х) ~~в ~ (х) — б), б ~ О. Алгоригвм 1 Н а ч а л о.
!. Выбрать произвольное начальное приближение ха ~ В" и константы е Е ('/„1), б ) 0 (рекомендуется выбирать б достаточно малым; е = ", ); положить й = О. Основной цикл. П. Положить х=х". 111. Найти р (х) и б (х) — решение следующей задачи выпукло- го программирования: найти агд ш(п ~ и + — ( р (( а) при ограничениях (~Ч~(х) р) + Рс (х) — Р(0, й Е й (х). !Ч. Если р (х) = О, то положить х'= х и прекратить вычисле- ния; иначе перейти к шагу Ч. Ч. Положить т = О. Ч1. Положить аа = (Ча)ч. Ч11.
Если выполняется неравенство 1е(х+ ааР(х)) (~а(х) — аае(Р(х) 1«, 167 то перейти к шагу ЧП1; иначе положить т = т + ! и перейти к шагу Ч1. ЧП1. Положить х"+! = х+ аор (х), положить й й+ ! и перейти к шагу 11. ТеоРема 1. ПУсть1! (х), 1 = 1, ..., т, непрерывно дифференцируемые функции; область Хо ~! (х ( 1о (х) к 1о (хо)) ограничена и 7 1, (х), 1 1, ..., т, удовлетворяют в Х, условию Липшица с константой у ( оо. Тогда любая предельная точка х бесконечной последовательности (хо)Г о, порожденной алгоритмом 1, удовлетворяет необходимым условиям минимума 1, (х) при хЕВ". Если, кроме того, 1, (х), 1 ~ 1, т — выпуклы, то х* — решение задачи 1.
Необходимым условием минимума 1, (х) а точке х' является существование чисел и„! 1, ..., т, таких, что 1; и, 71, (хо) - 0; ( ! ис(1,(хо) — 1о(х*)) =О, 1Е1, т; 1'й! = 1, й»~0, 1= 1, ..., т. с=! Следующая теорема дает локальную оценку сходимости алгоритма 1. Теорема 1'. Пусть х* — точка минимума 1, (х), функции 1, (х), 1 Е Оо (хо) — дважды непРеРывно диффеРенциРУемы. КРоме того, пусть ерадиенты Ч1, (хо), ! е г»'о (хо), где ~о(х')Й(о!161, т» 1о(х*)-1о(х*)). таковы, что разности Ч1! (хо) — Ч1!,(хо), 1Ф 1о, 1ое й!о(х*), линейно-независимы и множители й! строго больше нуля для 1С Е Оо (хо), а (У, 7' <Р (х', и) У) ) О длЯ всех У ~ О, здесь Ч(х и)= ЕиА(х) ! ! а 7;,»р (х, и) — матрица вторых производных относительно х.
Тогда при достаточно малом б ) 0 и а ) 0 суоцеспвует такая окрестность точки х*, что алгоритм 1 оходится с любого начального приближения хо из втой окрестности и '!хо — хо((су', 0 < д < 1. Теорема 1". Пусть выполнены все условия теоремы 1', и, кроме того, число индексов в множестве с!о (хо) равно п + 1. !68 В етом слрчог при достаточно л«алом 6 ) О алгоритм 1 в окрестности х* сходится при постоянном аа~ ! с квадратичноа скоростью к точке х*.
Бнблн«прафиесскчл улов«лил. Параграф написан на основании работы 1320! 3.12. Методы последовательных приблинсений длл решении дискретных минимаксных задач 3 а да ч а О. Найти ага гп1п гпах «р«(х) для заданных функций еса» «ед «р,: В" — ~ В', (р ч' и заданного множества ч'. Предположение О. (а) — функции «р„« ~ г««,— непрерывно дифференцируемы в Л". В данном параграфе описываются методы, в которых на й-й итерации в качестве направления движения к следующему приближению хл+' выбирается вектор и" (е), удовлетворяющий условию тах (7«р«(ха), йа(е)) = гп!и тах (7«р«(ха), Ь). «Е»»ге«е"> «»'" ««зяе«" > где Же(ха) Е~ (!(шах«р«(хе) — «р«(ха)(з, !чд).
Вектор йа (е) при и ~ О называют направлением е-наискорейшего спуска. 1. Первый метод посиедоввсельиыв приближений Алгоритм 1. Н а ч а л о. 1. Выбрать произвольное начальное приближение хо ~ !!» 11. Выбрать константы и„) О и а,) О. П1. Положить й = О. Ос нонна й ц и кл.
1Ч. Положить а= О и перейти к шагу Ч!1. Ч. Положить ! = О. Ч1. Положить з = ер Ч11. Найти множество индексов Я, (ха) = (1 ! тах «р«(х') — «р, (х") ( е, ! Е о«). (зло) «сУ Ч1П. Найти многогранник 1е (х'), который является выпуклой оболочкой, натянутой на множество точек (Ч«р;(ха), ! сЖ»(ха)).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
