МЕТОД БРОЙДЕНА-ФЛЕТЧЕРА-ШЕННО

Метод обладает слабой по сравнению с ДФП чувствительностью к погрешности одномерного поиска.

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Разложим градиент исходной функции в ряд Тейлора в окрестности точки очередного приближения по степеням следующего шага алгоритма :

Тогда оценка матрицы Гессе должна удовлетворять равенству:

,

где

это условие называют квазиньютоновским.

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

,

где — матрица, характеризующая поправку, вносимую на очередном шаге.

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

Поправка единичного ранга[править | править исходный текст]

Один шаг алгоритма даёт информацию о кривизне вдоль одного направления, поэтому ранг матрицы полагают малым, и даже единичным:

где и некоторые вектора.

Тогда, квазиньютоновское условие примет вид:

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

Из соображений симметричности матрицы Гессе, вектор берут коллинеарным :

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

Поправки ранга два[править | править исходный текст]

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

После чего её симметризуют:

Однако полученная матрица больше не удовлетворяет квазиньютоновскому условию. Чтобы это исправить, процедуру повторяют. В результате на -м шаге:

Предел этой последовательности равен:

При выборе различных (не ортогональных ) получаются различные формулы пересчёта матрицы :

· приводит к симметричной формуле ранга один;

· приводит к симметричной формуле Пауэлла — Бройдена (PSB);

· приводит к симметричной формуле Девидона — Флетчера — Пауэлла (DFP):

,

где

Нетрудно проверить, что ортогонален . Таким образом добавление слагаемого не нарушит ни квазиньютоновского условия, ни условия симметричности. Поэтому проводился ряд теоретических исследований, подвергавших последнее слагаемое масштабированию на предмет получения наилучшего приближения. В результате была принята точка зрения, что наилучшим вариантом является отвечающий полному отсутствию последнего слагаемого. Этот вариант пересчёта известен под именем формулы Бройдена — Флетчера — Гольдфарба — Шанно (BFGS):

Литература[править | править исходный текст]

· Гилл Ф., Мюррей У., Райт М. Практическая оптимизация = practical optimization.

[скрыть]

СВОЙСТВА СХОДИМОСТИ МЕТОДОВ

Определение.

Метод называется сходящимся, если неравенство

Выполняется на каждой итерации, где e^(k) = x^(k)-x^*.

Определение.

Алгоритм обладает сходимостью порядка r, если отношение

выполняется (конечно). Если r=1, то алгоритм обладает линейной скоростью сходимости. Если ещё при этом C=0, то алгоритм обладает суперлинейной скоростью сходимости. Если r=2, то скорость квадратичная.