Метод градиента.

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

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

В том случае, если функция зависит от нескольких переменных, т. е. градиент определяют по всем переменным:

После определения направления градиента осуществляют переход в новое положение по каждой координате в зависимости от максимальной величины и направления градиента.

В методе градиента используют свойство уменьшения величины градиента по мере приближения к экстремуму. Это легко проследить на рис. 11.6, наблюдая за изменением наклона касательных к кривой

Рис. 11.6

Координаты каждого последующего положения определяют таким образом:

Следовательно, в методе градиента процесс поиска разделяется на два этапа. Вначале делают пробный шаг для определения величины и направления градиента в соответствии с алгоритмом

где — координата вектора начального состояния; — координата вектора пробного состояния; — величина пробного шага; — единичный вектор отклонения по заданной координате.

Затем осуществляют одновременное рабочее смещение в направлении градиента всех координат в соответствии с уравнением

Рис. 11.7

Рис. 11.8

где х — вектор нового рабочего состояния; а — величина рабочего шага.

Иногда для ускорения поиска пробные и рабочие шаги совмещают, т. е. каждый рабочий шаг становится пробным шагом для последующего состояния.

На рис. 11.7 показаны траектории движения из начальных точек А, В, С к экстремуму по направлению градиента. Кривые движения нормальны к линиям постоянных значений функции качества Нетрудно видеть, что при наличии у функции качества так называемых «оврагов» или «гребней» движение по градиенту может стать очень извилистым, кроме того, направление градиента зависит от выбранных масштабов изменения координат по каждой оси, т. е. при неблагоприятных масштабах по осям поиск может значительно затянуться.