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

Метод Гаусса в различных его вариантах, несомненно, является наилучшим для тех задач, которые можно решить этим методом. Если же функция цели имеет вид, не совпадающий ни с одним из выражений, приведенных в табл. 5.1, этот метод может оказаться неприменимым. В таких случаях рекомендуется применять один из так называемых методов переменной метрики. Эти методы были так названы Дэвидоном [54]. Они объединяют процедуры, в которых матрица систематически корректируется от итерации к итерации

таким образом, чтобы приблизить ее к матрице Эти методы можно рассматривать как приближенные конечно-разностные процедур для вычисления вторых производных Процедура, предложенная Дэвидоном, была несколько модифицирована Флетчером и Пауэллом [81] и получила широкое распространение именно в этом варианте, который имеет репутацию наиболее общего и эффективного метода оптимизации без ограничений. Этот частный вариант является, по общему мнению, неустойчивым, поэтому в последующих работах появились другие варианты, например в работах Бройдена [42], Гринштадта [94], Фиакко и Мак-Кормика [75], Дэвидона [55], Пирсона [153], Барда [13] и Флетчера [80]. После такого общего введения к этим методам опишем детально варианты — методы КРЕ и ОКРЕ, которые, как показал опыт [13], оказались несколько более эффективными, чем другие. Это описание последует за кратким изложением метода Дэвидона — Флетчера — Пауэлла, который хорошо описан в литературе.

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

Поэтому с точностью до анпроксимации первого порядка имеем

где Это значит, что

Пусть перед итерацией мы имеем матрицу являющуюся аппроксимацией Мы хотим добавить к матрице некоторую поправку так, чтобы суммарная матрица удовлетворяла если заменить ею матрицу Это значит, что для матрицы

мы требуем, чтобы

Следовательно,

где

Уравнение определяет матрицу не единственным образом, ибо оно содержит лишь I условий для определения независимых элементов симметричной матрицы

Простейшей возможной матрицей будет матрица ранга единица, т. е. матрица вида

где некоторый вектор. Подставляя получим

или

где неизвестная константа. Подставляя получим

Поэтому

И окончательно имеем

Уравнение определяет метод коррекции ранга единица (КРЕ). Бройден [42], Дэвидон [55] и Фиакко и Мак-Кормик [751 доказали следующую теорему.

Теорема. Пусть функция квадратична с постоянной невырожденной матрицей Гессе Пусть последовательность точек, такая, что векторы линейно-независимы. Пусть произвольная симметричная матрица, определяются рекуррентно согласно (5.12-4) и (5.12-13). Тогда, если для имеем

Теорема гласит, что если квадратична, то метод КРЕ дает точное обращение матрицы Гессе за I шагов. Коль скоро известна обратная матрица от матрицы Гессе, для нахождения минимума нужно сделать единственный шаг по процедуре Ньютона. Если неквадратична, то следует ожидать, что представляет собой аппроксимацию оцененную на последних I итерациях. Это должно быть особенно справедливо в окрестности точки минимума, где последовательные итерации находятся близко друг к другу. Мы ожидаем, что матрицы сойдутся к матрице в точке минимума. Хотя до сих пор и не было найдено строгое доказательство этого предположения, ряд численных примеров подтвердил его справедливость.

Хотя принципиально утверждение теоремы справедливо для произвольной матрицы для устойчивости численной процедуры (см. [12]) необходимо, чтобы элементы имели подходящий порядок. Хорошим будет выбор в качестве диагональной матрицы с элементами

Так как является приближением матрицы желательно в качестве взять А. Однако нет гарантии, что положительно определена. Этот недостаток можно преодолеть, если использовать

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

Воспользуемся выражением для шкалированного разложения или

Введем

где соответственно малая и большая константы. Тогда матрица

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

Для того чтобы сделать матрицу А положительно-определенной, можно было бы, в принципе, использовать поправки к диагональным элементам типа поправок Марквардта. Этот тип коррекции, видимо, будет работать недостаточно хорошо применительно к аппроксимации матрицы, обратной матрице Гессе, а не ее самой. Однако процедуру, совершенно аналогичную процедуре метода КРЕ, можно употребить для построения аппроксимации непосредственно матрицы Гессе. Мы называем этот метод методом обратной коррекции ранга единица (ОКРЕ) [13]. В этом случае должно выполняться условие (см. что приводит к следующему соотношению:

В качестве начального приближения используем матрицу обратную по отношению к матрице, определяемой выражением Последовательность матриц сходится к в квадратическом случае. В силу того что есть аппроксимация для эффективного вычисления мы можем применить разложение Холецкого совместно с методом Марквардта, как это делается в разделе 5.8.

В методе Дэвидона — Флетчера — Пауэлла (ДФП) [54], [81] матрица имеет ранг, равный двум, а не единице. Простейшей матрицей такого типа, удовлетворяющей является следующая:

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