6.2. МЕТОДЫ переМЕННОй МЕТРИки
Для применения метода Ньютона необходимо знать матрицу Гессе и вычислить обратную к ней матрицу 
. Однако во многих случаях может оказатся так, что матрица 
неизвестна, либо ее вычисление связано с большими трудностями. Кроме того, как известно, в общем случае число операций умножения при обращении матрицы порядка 
пропорционально n3, что требует больших вычислительных затрат даже при небольших n. В связи с этим разработана группа методов, в которых матрица строится постепенно в процессе спуска. Эти методы получили название методов переменной метрики , или квазиньютоновских методов [50].
При использовании методов переменной метрики новый вектор 
вычисляется согласно уравнению
(6.2.1)
где матрица 
, которую называют матрицей направлений, представляет собой аппроксимацию матрицы 
. Для оценки воспользуемся следующим полезным соотношением, связывающим 
и для случая квадратичной целевой функции:
(6.2.2)
Умножая обе части (6.2.2) на , получим
(6.2.3)
Если при этом 
- квадратичная функция, то 
. Уравнения (6.2.3) можно рассматривать как систему из 
линейных уравнений, содержащих неизвестных параметров, которые нужно оценить для того, чтобы аппроксимировать при заданных значениях 
. Для решения этой системы могут быть применены различные методы, каждый из которых приводит к различным методам переменной метрики.
В довольно большой группе методов аппроксимируется с помощью информации, полученной на 
-м шаге следующим образом:
(6.2.4)
где 
- матрица, аппроксимирующая ; 
- вычисляется на -м шаге для уточнения аппроксимации; 
- масштабный коэффициент (множитель). Выбор по существу определяет метод переменной метрики. Для обеспечения сходимости 
должна быть положительно определенной и удовлетворять уравнению (6.2.4) будучи подставленной вместо . Поскольку на 
-м шаге нам известны 
, вычислим 
так, чтобы удовлетворялось соотношение
(6.2.5)
Пусть 
. Тогда уравнение
(6.2.6)
нужно разрешить относительно .
Непосредственной подстановкой в (6.2.6) можно проверить, что уравнение (6.2.6) имеет решение
(6.2.7)
где 
и 
произвольные векторы размерности 
. Если выбрать 
, то получим алгоритм Бройдена, если же в (6.2.7) положить 
, а 
, то получим алгоритм Дэвидона-Флэтчера-Пауэлла [50].
Алгоритм Бройдена
Рассматривая методы решения систем уравнений вида (6.2.3), Бройден показал, что если 
оказывается симметричной матрицей ранга 1 и должно удовлетворяться соотношение 
, то единственно возможным выбором является
(6.2.8)
где 
В простейшем варианте алгоритма Бройдена минимизация начинается с выбора начальной точки 
и некоторого 
. Затем последовательно применяют уравнения (6.2.1), (6.2.4)-(6.2.8) до тех пор, пока при некотором не получат 
.
В частном случае, когда целевая функция 
переменных квадратична, так что 
, матрица вычисляется из (6.2.5), (6.2.8), вычисляется из уравнения (6.2.1), а переменные 
являются независимыми направлениями, то можно показать, что спустя шагов 
[50]. В случае, когда не является квадратичной, применение уравнений (6.2.8) может привести к следующим нежелательным явлениям.
Матрица может перестать быть положительно определенной. В этом случае необходимо обеспечить положительную определенность с помощью одного из специальных методов.
Вычисляемая величина может стать неограниченной вследствие ошибок округления.
Если 
случайно совпадает с направлением предыдущего шага, то матрица 
становится вырожденной, или неопределенной.
В алгоритме Бройдена это будет иметь место в случае, если в процессе определения направления поиска по уравнению (6.2.1) уравнение 
или уравнение 
приведет к результату 
.
Как было показано в [50], одно из условий сходимости к стационарной точке заключается в том, что норма матрицы должна быть ограничена сверху и снизу. Для этого вводятся два ограничивающих условия:
(6.2.9)
где 
- некоторые константы.
Метод Дэвидона-Флетчера-Пауэлла
В варианте метода переменной метрики, предложенном Дэвидоном, Флетчером и Пауэллом, для нахождения матрицы 
используется матрица 
, имеющая ранг, равный 2. Матрица направлений 
перевычисляется таким образом, чтобы для квадратичной целевой функции после шагов выполнялось .
Исходная матрица обычно выбирается в виде единичной матрицы 
так, что начальное направление минимизации - это направление наискорейшего спуска.
Оценка элементов 
в точке екстремума 
тем точнее, чем лучше мы выберем по сравнению с матрицей 
исходную матрицу 
. В процессе оптимизации имеет место постепенный переход от градиентного направления движения к ньютоновскому, при этом используются преимущества каждого из этих методов на соответствующем этапе.
Алгоритм Дэвидона-Флетчера-Пауэлла получим, если в уравнении (6.2.5) положить 
. Тогда
(6.2.10)
Заметим, что так как матрицы 
и 
- симметричные, то если симметричная, то и будет симметричной.
Роль матрицы состоит в обеспечении выполнения условия 
при 
, тогда как должна обеспечить положительную определенность при всех и исключение влияния выбора начальной матрицы . Используя (6.2.10) многократно, при условии, что , через итераций получим
В случае квадратичной функции 
при 
должна равняться , а 
должна быть равна . Заметим, что в случае квадратичной целевой функции в данном алгоритме используются сопряженные направления.
В большинстве вариантов алгоритма функция минимизируется в каждом выбранном направлении поиска. Для определения минимума по 
в данном направлении можно применить любую эффективную процедуру одномерного поиска. При этом важно, чтобы эта процедура была эффективной, поскольку значительная часть всего времени вычислений приходится на одномерный поиск.
Практика показала, что в некоторых задачах невозможно достичь минимума с помощью методов переменной метрики, если степень точности одномерного поиска недостаточна. Поэтому рекомендуется выбирать точность одномерного поиска по крайней мере эквивалентной точности, требуемой для окончания основного алгоритма.
В качестве критерия останова работы алгоритма авторами было предложено использовать одно из следующих правил [50].
Каждая из составляющих векторов 
и 
меньше некоторой наперед заданной величины.
Вычисленная норма каждого из этих векторов в точке остановки меньше наперед заданной величины.
На рис.6.6 приведена траектория движения по алгоритму Дэвидона-Флетчера-Пауэлла при начальной длине шага 
. (Цифры на траектории обозначают номера соответствующих итераций).
На практике оказалось, что в данном методе и в других методах переменной метрики могут иногда встречаться шаги в противоположном (относительно направления точки минимума) направлении, либо эти методы могут оканчиваться в нестационарной точке.
Как выяснилось, это является следствием вырождения матрицы . Если матрица становится почти сингулярной, то направления поиска могут оказаться такими, как при неправильном выборе масштаба по осям координат. Вырождения матрицы можно избежать либо путем увеличения числа значащих цифр, либо соответствующим выбором масштаба компонент вектора с тем, чтобы сделать порядок диагональных элементов матрицы 
близким к 1.
Если же эти операции выполнить нельзя, то матрицу можно перезадать в виде диагональной матрицы, у которой 
, где 
-я компонента вектора
соответственно.
