И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 27
Текст из файла (страница 27)
Дополнительные сведения о методе самонастраиваюпгихся программ и его моди. фикациях можно получить иа рабат [381, 382, 383!. 131 2.12. Общий метод епуеиа Задача 1. Найти агйш(п~о(х) для заданной функции Но (о ° В Предположение 1. (г) — функция 1о выпукла н непрерывно днфференцируема в В", Алгоритм 1 Н а ч а л о. 1. Выбрать произвольное начальное приближение кое В" П. Положить й О. О с н о в н о й ц и к л. П [. Найти вектор й', удовлетворяющий условию (Ч~о( ), йо)~:О. 1Ч. Вычислить шаговый множитель ро) О нз условия 1о (хо — рой«) ш(п 1о (х" — р«о). о~о Ч.
Положить х"+' = х' — ро(оо. Ч1. Положить я я+ 1 и перейти к шагу П1. Для бесконечной последовательности (хл)~.о, порожденной' алгоритмом 1, справедлива следующая теорема. Теорема 1. Если выполняется предполоасение 1 и условия: (В)— (ЧУо(х) — ЧУо(у)3(~у$х — у$, Ух, усВ", (у(оо); ((и) — множеспию Хо~ (х~Д (х) (/о(хо) к~В ) ограниченог (Ь) — хотя бы для одного номера «справедливо (~1о ("~) «о) ~ О )ч(,( )((1«'1 то имеет место оценка а — ! 1-~ ~. (") — 1. (") ~; Е (.)*~ ь-о где (о (хо) = гп!п (о (х), с,) Π— константа.
«ен" Если, кроме того, (о(х) — сильновыпуклая функция, т. е. су« ществует б ) О такое, что ), (1х + (1 — Х) у) ( 34, (х) + (1 — 1) 1, (у) — 1 (1 — Ц 1 1 х — у Р, ч «с(О, 1), х, ус В", то имеют место оценки 1»(" ) 1»(х ) ~ ~(1о(х ) 1»(х*)) ехр 1 х — хо Г ( — (1о (хо) — 1» (хо)) ехр с и — ! (к, («») т о 2т и-1 ~~ («») 2т Библиографические раиания. Параграф осноеон но работе (1921. 2.13.
Методы случайного поиска 1. Алгоритм елучейпого пенсне и оыпунлыл ееялчен мпннмноеппн Задача 1. Найти агя пип1,(х) для заданной функции »ее»о 1о ° В Предположения 1. (о) — функция 1, выпукла в В"; (В) — функция 1, непрерывно дифференцируема в В" и ее градиент удовлетворяет условкю Липшица в В", т. е. 171»(х) — Ч1»(У)~~(т~х — У~, У( со, Чх, УРВ".
В методе случайного поиска иа Ьй итерации по известному приближению х' вычисляется следукнцее приближение х"+' как точка, в некотором смысле близкая к точке минимума функции 1» на прямой х» — рй», р р ( — оо, оо), где й» независимая реализация единичного случайного вектора равномерно распределенного на единичной сфере с центром в начале координат.
Для выпуклой функции алгоритм генерирует последовательность (х»)~.р, для которой 1»(" ) 1»(х ) = О( 1») где х* — решение задачи 1, О (1) — величина порядка 1, а для сильновыпуклой функции 1, справедливо х» -~ х* и 1» (х») -+ 1, (хо) при й -о. со со скоростью сходимости геометрической прогрессии. Алгоритм 1 Н а ч а л о. 1.
Выбрать произвольное начальное приближение хо Е В'. 11. Положить й = О. Основной цикл. 111. Если Ч1» (х») = О, то положить л~= х» и прекратить вычисления; иначе перейти к шагу 1Ч. 1Ч. Найти независимую реализацию й» единичного случайного вектора $, равномерно распределенного на единичной и-мерной сфере с центром в начале координат. Ч. Вычислить шаговый множитель р», удовлетворяющий неравенству 1»(х» — Р»И~) ~~(1 2») 1о(х») + )"»Р» йп291 133 где Х» — произвольная точка фиксированного отрезка Х ( ь»(»1 (», — произвольная константа из полуинтервала (О, П), т» = = ш1п' 1» (х' — р/»"). оя( ~,м) Ч1 Вычислить следующее приближение х»+' = х» =- р»Л».
ЧП. Положить й = й+ 1 и перейти к шагу И1. Теорема 1. Пусть выполняется предположение! и пусть множе- ство Х«Ь (х(1, (х) ( 1, (х'), хЕ В") ограничено. Тогда, если по- следовательность (х")~о, порожденная алгоритмом 1, такова, чта Цо (х») ~ О, й = О, 1, ..., и что существует номер т„для коп»враго с«. ~ О, где и»л(Ч1о( '), Ь")/(Ч1о( )~, то для всех т ~ то+ 1 выполняется неравенопво Гт — ! 1 1 1,(х ) — 1,(х*)(с,~ ~, («о»)о~ где с, — положительная постоянная.
Теорема 1'. Пусть выполняются все предположения теоремы ! и функция 1, (х) сильновыпукла. Тогда для последовательности (х )» о, порожденной алгоритмом 1, выполняются неравенства е-1 ьо-~-ы~~~о.ьо — оо'о о(-+ Е~ >). т=1, 2, ...; т-1 ~ х~ — х')о » (—, (1о (хо) — 1» (х*)) ехр — р Х («оо)' 2т с о т 1, 2, ..., здесь ч — параметр сильновыпуклой функции.
Замечание !. При выполнении предположений теоремы 1 алго- ритм 1 порождает последовательность (х )~ о, для которой с ве- роятностью, равной единице, осуществляется событие «для всякого е, удовлетворяющего неравенствам О ( е ( 1/и, найдется такое число ! (е), что неравенства 1о (х») — 1» (хо) » (2УЧ'и/Ф (1 — па)) справедливы для всех целых й ~ ! (е)ы Отсюда, в частности, следует, что с.вероятностью равной едини- це для любого числа () > 2уцопlь найдется число ! (р) такое, что не- равенства 1о (х») — 1о (х*) ( р/й справедливы для всех целых й ~» ! (р).
!34 Замечание Т. При выполнении предположений теоремы 1' алгоритм 1 порождает последовательность (х»)„о, для которой с вероятностью, равной единице, х» -» хо и 1с (хо) -» 1с (хо) при к -» -» оо со скоростью сходимости геометрической прогрессии. а. Алаптпапыа алгоритм слтчайпого попела Зада ча 2. Найти агя ппп 1с(х) для заданной функции ««а« гс ° «««« .
В данном адаптивном алгоритме случайного поиска величина шагового множителя изменяется в зависимости от результата, полученного на предыдущей итерации. Вектор в», определяющий направление движения в й-й итерации к следующему приближению х"+', является независимой реализацией случайного вектора К распределенного по единичной сфере с плотностью р«(у) 1ь(у)де= »1с, Чу~О. ~Ж-1 м,д>>с Алгоритм 2 Н а ч а л о. 1.
Выбрать произвольное начальное приближение хср В", произвольное начальное значение шагового множителя р, и константы уг) 1, О ( у,( 1; положить й = О. Ос но в и о й ц и к л. 11. Найти независимую реализацию в» случайного вектора $, распределенного по единичной сфере с плотностью рг (у), удовлетворяющей условию (2.21) (в частности 13491, этому требованию удовлетворяют случайный вектор $, равномерно распределенный на сфере, а также проекция на единичную сферу вектора, равномерно распределенного в кубе или на его поверхности).
Ш. Если 1» (х» + РД») ( гс (х»), то положить й» = л»; иначе положить и" = О. 1Ч. Вычислить следующее приближение х"+' = х' + й'. Ч. Вычислить следующее значение шагового множителя согласно условий (у рм ес и Ь (х'+')(1о(") Р'"'' = 1!У«Р», если 1»(х»+') в/с(х'). Ч1. Положить й = й + ! и перейти к шагу 11. Теорема 2. Если выполнены условия: (1) — функция Дс ограничена снизу; (Й) — функция ! непрерывно дифференцируема; (111)— х* — единственная точка минимума функции ~; (1о) — Ч!о (х) ча О при х чь хо' (о) — множество (х ~ 1« (х) ( с») огРаничено длЯ всех а ( 1» (хс)' (о1) — у,у, ) 1, то последовательность (х )» ~.
!Зо порожденная алгоритмом 2, сходится с вероятностью 1 к точке минимума хе. Библиогрифичесчие уланшил. При написании параграфа использовались ра. боты 1193, 349, 847, 6, 418, 57, 328, 224, 283, 2841. Глава 3 МЕТОДЫ ОПТИМИЗАЦИИ НЕДИФФЕРЕНЦИРУЕМЫХ ФУНКЦИИ И МЕТОДЫ ОТЫСКАНИЯ СЕДЛОЕЫХ ТОЧЕК 3.1. Методы обобщенного градиентного спуска 3 а д а ч а О. Найти агд ппп 1» (х) для заданной выпуклой функ«чя" цни ~е: В" -ь К'. Предположение О. Множество решений Х* непусто.
1. Алгоритм с иостоннвым шаговым мвожнтовем В алгоритме 1 в й-й итерации за вектор движения Ь» к следующему приближению х"+' выбирается единичный вектор обобщенного градиента функции 1е в точке х». Шаговый множитель р является постоянной величиной, При заданном 6 ) О можно указать такое р = р (6), что порожденная алгоритмом 1 последовательность (х»)» о попадает в область, где минимизируемая функция 1» отличаетсЯ от своего минимУма на величинУ 6. ' Алгоритм 1 Н а ч а л о. 1. Выбрать: произвольное начальное приближение хор В", постоянный шаговый множитель р ) О; положить й = О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
