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

В методах с переменной метрикой заложена идея метода Ньютона, а именно в них итерационным способом находится матрица, обратная матрице вторых производных, т.е. G^-1 ~ H_k, где H_k - матрица порядка n´n, которая носит название метрики. Поисковое направление определяется по формуле:

(1.5.7)

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

D X =G^-1×D g (1.5.8)

Для аппроксимации матрицы, обратной матрице Гессе, воспользуемся следующим рекуррентным соотношением:

H_k+1=H_k+E_k, (1.5.9)

где E_k - корректирующая матрица.

Исходя из важного свойства квадратичной функции (1.5.8), можно потребовать, чтобы новое приближение H_k+1 удовлетворяло соотношению:

H_k+1× y _k= s _k, (1.5.10)

где y _k= g _k+1- g _k, s _k= X _k+1- X _k.

Выражение (1.5.10) можно переписать в виде:

H_k× y _k+E_k× y _k= s _k. (1.5.11)

Решение уравнения (1.5.11) для корректирующей матрицы E_k является не однозначным и может иметь следующий вид:

Здесь v _k и w _k - произвольные вектора, т.е. формула (1.5.12) определяет некоторое семейство решений. Если положить

v _k= s _k и w _k =H_k× y _k, (1.5.13)

то получим формулу, реализующую известный и широко применяемый метод Давидона-Флетчера-Пауэлла [16 ]:

(1.5.14)

Можно показать, что формула (1.5.14) сохраняет свойства симметрии и положительной определенности матрицы H_k. Поэтому, если H₀ - симметрическая и положительно определенная матрица, то матрицы H₁, H₂,... также будут симметричными и положительно определенными при отсутствии ошибок округления; обычно полагают H₀=I, где I - единичная диагональная матрица.

Первая вариация J(X) равна

DJ(X)=g_k^T×D X.

Используя формулы (1.5.7) и (1.1.1), получим

DJ(X)=-a_k× g _k^T×H_k× g _k.

Из (1.5.16) видно, что неравенство J(X _k+1)<J(X _k) выполняется при

любых значениях a_k>0, если H_k - положительно определенная матрица. Таким образом, алгоритм обеспечивает убывание целевой функции при переходе от итерации к итерации.

В силу того, что существует определенный произвол в выборе векторов v и w в (1.5.12), то можно учесть какие-то дополнительные условия, улучшающие работу методов с переменной метрикой. Например, в методе Гольдфарба [19] накладывается дополнительное требование минимальности нормы корректирующей матрицы:

(1.5.17)

где Q _i={0,0,..,0,1_i,0,..,0}^T. Это приводит к повышению устойчивости метода к ошибкам вычислений значений целевой функции, градиента и минимума в поисковом направлении. Так практически на тестовых примерах и задачах оптимизации процессов в электронных приборах было установлено, что алгоритм Гольдфарба оказался существенно более устойчивым к ошибкам вычислений, чем алгоритм Давидона-Флетчера-Пауэлла. Корректирующая матрица алгоритма Гольдфарба рассчитывается по формуле:

(1.5.18)

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

Алгоритм методов с переменной метрикой следующий.

{{{ Начало алгоритма.

1 0....0)

1) Полагаем k=1, X _k= X _init,

Рассчитываем J(X _k), g _k=P_xJ(X _k).

2) Определяем поисковое направление

P _k= - H_k× g _k и находим минимум в этом направлении:

a_k: min_a(J(X _k+a_k× P _k)

Новое приближение вектора поисковых параметров находится как

X_k+1= X _k+a_k× P _k.

3) Если |a_k× P _k|<e, то процесс оптимизации окончен, иначе переходим к следующему пункту.

4) Рассчитываем в новой точке J(X _k+1) и g _k+1.

Пересчитываем метрику H_k+1=H_k+E_k по одной из формул приложения 1, увеличиваем k на единицу k=k+1 и переходим опять к пункту 2).

}}} Конец алгоритма.

Работа метода с переменной метрикой показана на рис.1.5.2

Методы с переменной метрикой, как и ожидалось, хорошо себя показали на только на функциях близких к квадратичным, но и на сложных более высокого порядка функциях. Это можно объяснить тем, что в методах с переменной метрикой на каждой итерации находится очередное приближение обратной матрицы Гессе, которая дает квадратичную аппроксимацию целевой функции около текущей поисковой точки. В процессе оптимизации это приближение меняется в соответствии с изменением рельефа целевой функции, при этом рассчитываются только первые производные, что существенно проще и быстрее сделать, чем рассчитывать вторые производные, как в методе Ньютона. Пересчет матрицы H_k на каждой итерации приводит к адаптации метода к текущему рельефу целевой функции, что и позволяет ему успешно работать на функциях далеких от квадратичных. Как показали тестовые испытания методы с переменной метрикой оказались более быстродействующими даже по сравнению с методом Ньютона-Рафсона при численном расчете производных.

Рис.1.5.2

Поиск минимума методом с переменной метрикой

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

Следует отметить также, что методы с переменной метрикой позволяют получить, как побочный результат, квадратичную аппроксимацию целевой функции вблизи точки минимума:

J(X)=J(X_min)+ g ^T(X_min)×(X - X_min)+(X - X_min)^T×G×(X - X_min)/2. (1.5.19)

Дата добавления: 2015-11-14