Первая лаба в виде буклетика

В обоих рассматриваемых методах в отличие от метода градиентного спуска шаг Ь( ) в направлении поиска экстремума выби(й) раем оптимальным на каждой итерация Й, т.е. Ь Ф сопз$. Рассмотрим два способа определения оптимального шага. 1. Точный аналитический способ На каждой итерации Й получаем выражение для ~~Х ~ в (й+ () 1 виде функции от Ь( ): з(й(~) )= у(Х( + ) ~= ~~Х()+ Ь()б()) . Для нахождения оптимального шага Ь в направлении по- (Й) иска экстремума решаем задачу одномернои (так как Ь вЂ” ска(й) ляр) оптимизации: ех(г з(Ь()), з »й) (1ЛЗ) ";„, ~й(")~= О и достаточном условии минимума (2](й(й) ~ $ (2) ( Ь (й) ) < О н максимума '"'(Ь~') — р~ю я Р ш фу ц (й) точке Ь( ). Если г (2) ~Ь 00 ) = О, то исследуются производные более высокого порядка, Достаточным условием экстремума будет четный порядок с (о= 4,6, ...

)первой встречающейся (наиболее низкого порядка) производной з ~") '( Ь ( ~), не равной нулю, и при з (~) '( Ь~ ~) > 0 достигается минимум з в точке Ь, а при з ) ~й ) < 0 — мак(й) симум. причем в качестве экстремума будет минимум функции г(Ь( (ь) 1 при поиске минимума функции )"(Х) и максимум з( Ь ~ — при (ь) ~ максимуме у (Х ) .

Для решения задачи (1ЛЗ) используется классический метод, основанный на необходимом условии экстремума: Я. Приближенный способ Это способ нахождения оптимального шага Ь() путем одно(й) или многократного деления или умножения шага Ь( ) на дробное положительное число, в частности, способ половинного деления или умножения шага.

Алгоритм определения на каждой Й-й итерации значений Ь и Х при поиске минимума)(Х) состоит в следующем. (Й) (ь+ 4) 1. Принимаем Ь(~) = Ь(~ 2. Вычисляем Х= Х + Ь» ~я~ ) и определяем )"(Х). (ь) 3. Если )'(Х)> )".(Х(")~, то Ь()= ай(), где О< а< 1 (для способа половинного деления или умножения шага принимаем а= 0,5). Пп. 2 и 3 алгоритма повторяем до тех пор, пока не будет выполнено условие ~(Х) < ~(Х() ~.

Тогда примем Х(~~~)= Х и (й) ~ переходим на и. 5. (Слишком большой шаг приводит к расходящемуся процессу при поиске экстремума, поэтому шаг уменьшают до того значения, при котором обеспечивается сходимость процесса поиска минимума). ,з,, „, Ь(Й) 4. Если ( (Х) < 1'(Х ( ) ), то Ь ( ) = — . Запоминаем предыдущее а значение Х: Х = Х.

Вычисляем новое значение Х= Х()+ Ь( )б() . пх). П. 4 повторяется до тех пор, пока не выполнится условие )'(Х)> у(Х ~, тогда в качестве Х берем предыдущее зна> ( (ь) ') (Й+ () чениж Х = Х . (Слишком маленький шаг приводит к недо(й+ () статочной скорости сходимостн процесса поиска экстремума (большому числу итераций), поэтому шаг увеличивают до тех пор, пока процесс поиска минимума остается сходящимся). 5. Конец алгоритма. Рассмотрим геометрическую интерпретацию метода наискорейшего спуска. Из точки Х идем в направлении антиградиента в случае по(й) иска минимума )(Х) или,градиента прн максимуме до точки Х, в которои достигается минимальное значение функции в (Й+ О данном направлении.

Зто направление + Ч~~Х ) перпендикуляр(е) х 17 Ряс. 1.3 Методы наискорейшего спуска и сопряженных градиентов Рзс. $.4 но касательной к поверхности (линии при и= 2) постоянного уровня функции в точке Х, а также оно само является каса- (Й) тельной к поверхности (линии) постоянного уровня функции „('(Х) в точке Х . Поэтому перпендикуляр к касательной из точки Х проводим до тех нор, пока он сам не станет касатель- (Й) ной к другой линии уровня (в точке Х~~+~) ). Геометрическая интерпретация метода наискорейшего спуска представлена на рис. 1.4, где изображены линии постоянного уровня функции,)'(л(,л2)= с» (и= 1, 2, 3, 34, 4, 5, б,причем с(> е2> сз> сз4> с4> с5> сэ) и полученные в соответствии с данным методом точки Х ~Й= 1,3) при поиске минимума ,)'(Х).

Для наглядности сравнекия градиентных методов на рис, 1.4 показаны также полученные по методу градиентного спуска точки Х( ) '( Й = 1, 3 ~. Кроме того, на рис. 1.4 представлена геометрическая интерпретация метода сопряженных градиентов. В данном методе по 1,8 иске минимума 1'(Х).

При этом точки Х ) и Х( ) расположены на расстоянии Й ~ ~ 7~(Х~"~) ~ ~ друг от друга. Расчетная формула для направления я поиска экстремума (Й) в методе наискорейшего спуска имеет тот же вид (1.8) — (1.9), что н в методе градиентного спуска; ® ( (Й)) где «+» используют при поиске максимума, «-» при минимуме. В методе сопряженных градиентов при вычислении направления 4 учитьгвается предыстория поиска экстремума: (Й) !! '"' 11' р®= Й ЧУ~Х(Й))+ — й("-'), (1.12) ~;~~(Х(Й-$)~~~ 2 где а = О. Отметим, что при Й= О (1.12) совпадает с формулой (- 1) для я в методе наискорейшего спуска.

Сходимость метода сопряженных градиентов по сравнению с методом наискорейшего спуска лучше, однако сложность выполнения действий на каждой итерации выше. 1 Ь> — процесс расходится (рис. 1.2, б); при Ь< — — сходится с( а (рис. 1.2, в). В связи с малостью шага Ь данный метод не обеспечивает быстроту сходимости, требуется больше итераций, чем при применении метода Ньютона и метода наискорейшего спуска. Отметим, что так как в данном методе градиент вычисляется на каждой итерации, то при слишком громоздком выражении для градиента его значение находят по приближенной формуле: ,)'(х (, ..., х;+ ~, ..., х „) — У(х (, ..., х;, ..., х „) где с,< Ь.

Рассмотрим геометрический смысл метода градиентного спуска. Направление градиента и антиградиента функции )(Х) в любой точке перпендикулярно касательной к поверхности (при и = 2 к линии) постоянного уровня функции в этой точке. Такой поверхностью (линией) называется поверхность (линия), на которой значение функции постоянно. На рис. 1,3 изображены линии постоянного уровня функции)(х(,х2)= с (и= 1,4, причем с(> с2> сз> с ), выбранная начальная точка Х( ) и полученные в соответствии с мето- (о) дом градиентного спуска первые три точки Х ~Й= 1,3 ) при по- (4 сравнению с методом наискорейшего спуска траектория поиска экстремума, проходящая последовательно через точки Х (Ь= О, " (ь) 1, 2, ...), сглаживается. Точка Х" находится между Х и " (2) (2) Х( ).

Отметим, что в связи с выражением Х(() = Х(~)+ Ь(~)д(~), выбором одной и той же начальной точки для трех градиентных методов Х()= Х()= Х() и совпадением формул для у() и Ь() при Ь= О в методах наискорейшего спуска и сопряженных градиентов, получаем совпадение в обоих методах точек на первой итерации Х( ) = Х( ) Ф Х( ) . Методы случайного поиска Если целевая функция такова, что затруднено или невозможно нахождение ее производных, или они имеют' слишком громоздкий вид, то применяют методы случайного поиска. В этом случае потребуется большее число итераций, но сама итерация будет проще: без вычисления производных. Данные методы являются итерационными, и укрупненный алгоритм решения задач безусловной оптимизации в соответствии с ними приведен на с.

12. В методах случайного поиска шаг Ь(~) обычно задается постоянным. Однако возможны модификации методов, в которых используется приближенный способ нахождения оптимального шага Ь() на каждой итерации, описанный при рассмотрении методов наискорейшего спуска и сопряженных градиентов. Направление я поиска экстремума является полностью или частично случайным. Существует много методов случайного поиска, отличаюгцихся тем, как выбирается направление у(~). Рассмотрим особенности нахождения Х( ) и Х( ) в трех ос(а) (Й+ () новных методах случайного поиска.

1. Метод с возвратом на неудачном шаге Алгоритм нахождения у и Х на каждой итерации й состоит в следующем. 1. Генерируем случайное направление Л( ) в а-мерном пространстве, т,е, случайный вектор Л ( ) = ( г (( ), ..., г ( ) ~, где г ( — случайная величина с известным законом распределения (для простоты часто используют равномерное распределение на отрезке [-1, Ц). 2. Примем у( ) = Л( ) и вычислим Х= Х( )+ Ь( )д( ) .

3. Если «(Х) > «(Х( ) ) в случае поиска минимума «(Х) (или «(Х)с «(Х(й)) при максимуме), то переходим к п. 1, иначе Х(й+ В 4. Конец алгоритма. 2. Метод наилучшей пробы Алгоритм нахождения у и Х на каждои итерации Й (й) (й+ 1) состоит в следующем. 1. Генерируем г случайных направлений Л1, ..., Л,; нахо(й) (й), дим соответствующие им г значений векторов Х„= Х + Ь Л, (й) (й) (й) о= 1,е) и е значений «(Х ) функции«(Х) в этих точках Х 2.