Метод наискорейшего подъема

Рассмотренный нами градиентный метод предполагает, что величина шага задается. При этом она не обязательно должна быть постоянной на протяжении всей процедуры поиска экстремума. Например, для увеличения точности и сокращения количества итераций величину можно уменьшать по мере приближения к максимуму. Однако градиентный метод не позволяет получить каких либо рекомендации относительно выбора величины .

Метод наискорейшего подъёма ( в случае поиска минимума его называют методом наискорейшего спуска) это разновидность градиентного метода, в котором на каждом шаге выбирается оптимальное значение длины шага , именно такое, при котором приращение целевой функции на данном шаге максимально. Для этого на каждом этапе ищется приращение функции , которое зависит и от величины шага:

(11.1)

Так как приращение зависит от шага , который является аргументом функции то определение величины при которой эта функция принимает максимальное значение производится стандартными методами. А именно, ищется аналитическое выражение для

приращения в зависимости от и находится производная от по .

Далее производная приравнивается к нулю и находится оптимальное значение .,

при котором приращение функции на данном шаге будет наибольшим.

Таким образом длина шага в данном методе определяется из условия

(11.2)

Проиллюстрируем эффективность применения этого метода для решения уже рассмотренной нами задачи ( 10.9 ):

У=50-(х₁-4)²-(х₂-6)²max (11.3)

Найдем выражение для приращения функции как разность между значениями функции в точке и .

(11.4)

Так, как =0, и =0,

(11.5)

Теперь следует определить значение . Для этого, сначала требуется найти и , для чего воспользуемся формулами ( 10.16 ) и (10.1 ):

(11.6)

Подставим эти выражения для и в :

(11.7)

После алгебраических преобразований формула ( 11.7 ) приобретает вид:

(11.8)

Теперь можно найти и выражение для приращения функции:

(11.9)

Как видим, величина приращения зависит от шага .

Найдем производную :

(11.10)

И приравняем полученное выражение к «0»

(11.11)

Решив это уравнение относительно , получаем оптимальную величину

для первого шага: =0,5.

Воспользуемся еще раз выражениями ( 10.17) и (10.18) и определим координаты точки

Как видим, это координаты точки максимума функции ( ). Таким образом, в отличие от градиентного, метод наискорейшего подъема позволил (для рассматриваемого примера) определить оптимальное решение за один шаг.