Метод наискорейшего спуска. Метод дробления шага

Рассматривается следующая многомерная задача локальной безусловной оптимизации: найти минимум критерия оптимальности

(

), определенного в

-мерном евклидовом пространстве

(1)

Положим, что функция

(

) всюду дифференцируема в

-мерном евклидовом пространстве

Направление спуска в градиентных методах оптимизации совпадает с направлением антиградиента минимизируемой функции

(

). Итерационная формула градиентных методов оптимизации имеет вид

(2)

Здесь

- длина шага на

-ой итерации в направлении

, где

(3)

единичный вектор направления антиградиента функции

(

) в точке

- некоторая векторная норма, например, евклидова. Напомним, что градиент функции

(

) в точке

есть значение вектора частных производных этой функции в точке

Различные градиентные методы оптимизации отличаются между собой правилами выбора длины шага

Градиентный метод наискорейшего спуска.

Градиентный метод наискорейшего спуска в качестве длины шага

использует величину, при которой достигается минимум функции

(

) в направлении

(4)

Задача (2) есть одномерная задача локальной безусловной оптимизации, которая может быть решена рассмотренными в главе 4 методами, например, методом Паулла (см. параграф 4.7).

Схема метода:

Задаем начальную точку и полагаем счетчик числа итераций =0.
По формуле (3) вычисляем компоненты вектора .
Каким-либо методом решаем одномерную задачу безусловной оптимизации (4) – определяем точку .
Вычисляем величину () - значение функции () в точке .
Проверяем условие окончания поиска (см. ниже). Если условие окончания поиска выполнено, то полагаем и завершаем итерации. Иначе – полагаем , переходим к п. 2

В качестве критерия окончания поиска можно использоваться одно из стандартных условий окончания итераций

(5)

(6)

В качестве критерия окончания поиска можно использоваться также условие

(7)

где

- константа, определяющая требуемую точность решения по градиенту функции

(

Градиентный метод наискорейшего спуска иллюстрирует рис. 1, на котором показан фрагмент линий уровня функции Химмельблау.

Рис. 1. Траектория поиска минимума функции Химмельблау градиентным методом наискорейшего спуска.

Градиентный метод с дроблением шага

В градиентном методе с дроблением шага точка

определяется по формуле

(8)

где величина шага

находится из условия

(9)

Схема метода:

Задаем начальную точку , начальную величину шага и коэффициент дробления шага . Полагаем счетчик числа итераций =0.
По формуле (8) вычисляем компоненты вектора .
Вычисляем величину () - значение функции () в точке .
Если условие (9) выполнено, то переходим к следующему пункту. Иначе – переходим к пункту 6.
Полагаем = и переходим к пункту 2.
Проверяем условие окончания поиска (см. ниже). Если условие окончания поиска выполнено, то полагаем , и завершаем итерации. Иначе – полагаем =+1 переходим к п. 2

В качестве критерия окончания поиска можно использоваться условия (5) – (7).

Градиентный метод дробления шага иллюстрирует рис. 2, на котором показан фрагмент линий уровня функции Химмельблау.

Рис. 2. Траектория поиска минимума функции Химмельблау градиентным методом дробления шага.

Пример 1

1. Постановка задачи.

Выполнить несколько итераций (не менее двух) решения двумерной задачи локальной безусловной оптимизации

(10)

(11)

градиентным методом с дроблением шага, исходя из точки

Принять

, в качестве нормы вектора градиента использовать евклидову норму.

Траекторию поиска изобразить на рис. 3, на котором приведены линии уровня квадратичной функции (11), полученные с помощью MATLAB-программы, приведенной в параграфе 6.1.

Рис. 3. К примеру 1. Фрагмент (три итерации) траектории поиска минимума функции (11) градиентным методом с дроблением шага, исходя из точки X⁰=(x⁰,y⁰)=(-2.0,1.0).

2. Итерационная формула.

Итерация градиентного метода с дроблением шага для задачи (10), (11) имеет вид