9.1.2. Алгоритмы квазиградиентного типа.

Предположим, что область допустимых значений параметров Г совпадает со всем евклидовым пространством ( — число неизвестных параметров, т. е. размерность вектора ).

Наибольшее распространение в настоящее время получили алгоритмы итерационного типа

где s — номер итерации; — вектор, определяющий направление движения на итерации; — длина шага.

Идея, лежащая в основе этих алгоритмов, очень проста: на каждом шаге двигаться в направлении минимума функции . Различные алгоритмы отличаются способом выбора этого направления и правилами выбора длины шага. В данной главе обсуждаются лишь алгоритмы, движение в которых осуществляется в направлении под острым углом к антиградиенту - ) функции (или некоторой ее аппроксимации).

Такие алгоритмы будут называться в дальнейшем алгоритмами квазиградиентного типа-Напомним, что антиградиент — это направление, противоположное градиенту, а градиент в точке перпендикулярен к линии постоянного значения функции проходящей через эту точку (рис. 9.1). Полезно иметь в виду, что градиент определяется часто следующим образом:

где .

Рис. 9.1. Определение направления градиента

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

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

где

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

Для алгоритмов квазиградиентного типа соотношение (9.4) принимает вид:

Вектор либо совпадает с градиентом подсчитанным в точке либо представляет из себя его некоторую аппроксимацию. Матрица — положительно полуопределенная матрица, т. е. что и гарантирует движение под острым углом к антиградиенту.

В табл. 9.1 представлены выражения для наиболее распространенных алгоритмов безусловной минимизации

Таблица 9.1