1. Методы переменной метрики

Методы переменной метрики называют также квазиньютоновскими или градиентными с большим шагом.

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

Очередное приближение в этих методах находится по формуле:

,                      (1)

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

.

Для квадратичной целевой функции (или квадратичной аппроксимации целевой функции) имеем:

,

где .

Если вместо подставить в формулу и продифференцировать, то получим

,

.

Умножив на , получаем

.                           (2)

При этом, если квадратичная функция, то – постоянная матрица.

Уравнение (2) можно рассматривать как систему линейных уравнений с неизвестными параметрами, которые необходимо оценить для того, чтобы аппроксимировать или при заданных значениях , и на более ранних этапах поиска.

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

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

,                               (3)

где – матрица, аппроксимирующая на предыдущем шаге. Вообще . В (3) представляет собой определяемую матрицу, а - масштабный (постоянный) множитель, в большинстве случаев равный единице.

Выбор по существу и определяет соответствующий метод переменной метрики.

Для обеспечения сходимости метода матрица должна быть положительно определенной и удовлетворять уравнению (2) в том случае, когда она заменяет .

На -м шаге мы знаем , , и и нам требуется вычислить так, чтобы удовлетворялось соотношение (2).

Из выражения (2) с учетом (3)

и

.                                                  (4)

Так как , то на основании (4) уравнение

                                   (5)

следует разрешить относительно .

Прямой подстановкой результата можно показать, что уравнение (5) имеет следующее решение:

,                                   (6)

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

Например, если для выбирается специальная линейная комбинация двух направлений и :

,

то получают метод Бройдена.

Если же берется

то матрицу строится в соответствии с алгоритмом Дэвидона-Флетчера-Пауэлла.

Так и – произвольные векторы, то оказываются допустимыми и другие возможности.

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