Метод Бройдена–Флетчера–Гольдфарба–Шанно

Назначение сервиса. Онлайн-калькулятор предназначен для нахождения минимума функции методом Бройдена-Флетчера-Шенно (BFGS).
f(x1,x2) =
Начиная из точки ( ; ). Точность ξ = .
Правила ввода функций:
  1. Все переменные выражаются через x1,x2
  2. Все математические операции выражаются через общепринятые символы (+,-,*,/,^). Например, x12+x1x2, записываем как x1^2+x1*x2.
Решение оформляется в формате Word.

Квазиньютоновские методы также основаны на свойствах квадратичных функций. Данные методы обладают положительными чертами метода Ньютона, однако используют только первые производные.
Итерационный поиск по методу Ньютона осуществлялся по формуле (обобщенный случай с λ):
. (1)
Трудность может возникнуть, когда матрица Гессе не является положительно определенной. В этом случае направление перемещения
(2)
может не быть направлением спуска и глобальная сходимость метода не будет обеспечена.
В таких ситуациях обратную матрицу Гессе заменяют положительно определенной матрицей Ak, дающей направление перемещения, исходя из градиента . Отсюда получаем итерационную формулу
, (3)
где λk выбирается так, чтобы минимизировать функцию в направлении .
Очевидно, что матрица Ak на каждой итерации модифицируется так, чтобы для каждой квадратичной функции вида

(с положительно определенной матрицей ) матрицы Ak сходились к обращению матрицы Гессе функции f(x).
Следовательно, на конечном этапе сходимости мы вновь придем к методу Ньютона.
Если метод применяется к произвольной функции, то Ak может рассматриваться на каждом шаге как аппроксимация (положительно определенная) обращения матрицы Гессе функции f(x).
Для аппроксимации матрицы Hf-1 пользуются следующим рекуррентным соотношением:
Ak+1 = Ak + Ack, (4)
где Ack - корректирующая матрица.
Матрица Ak будет использоваться в формулах (1), (2), (3). Задача заключается в том, чтобы построить матрицу Ak таким образом, чтобы последовательность A0,A1,A2,...,Ak+1 давала приближение к . При этом для получения решения x* требуется один дополнительный поиск вдоль прямой, если f(x) - квадратичная функция. Данный подход приводит к успеху при решении задач с нелинейными ЦФ общего вида.
Еще раз напомним свойства квадратичных функций

Изменение градиента при переходе из точки x0 в x1 выражается соотношением

или
. (5)
Предположим, что матрица аппроксимируется по формуле
,
где β - скалярная величина. Наиболее предпочтительным является приближение, удовлетворяющее соотношению (5), то есть
Δxk=AkΔgk
Однако построить такую аппроксимацию невозможно, т.к. для того чтобы найти Δgk, необходимо знать матрицу Ak. Здесь используются следующие обозначения:
, .
С другой стороны, можно потребовать, чтобы новое приближение удовлетворяло также формуле (5) с учетом свойств квадратичных функций:
, . (6)
Подставляя (4) в (6), получим:
.
Выразим отсюда :
. (7)
С помощью непосредственной подстановки можно убедиться, что матрица
(8)
является решением этого уравнения (7). (Для этого надо (8) умножить справа на Δgk, и мы получим выражение (7)).
Здесь y и z - произвольные векторы, т.е. (8) определяет некоторое семейство решений.
Другой способ получения матрицы Ack.
В зависимости от того, имеет матрица Ack ранг 1 или ранг 2, будем говорить о коррекции ранга 1 или ранга 2.
Рассмотрим коррекцию ранга 1:
, (9)
где βk - скаляр, uk - вектор, выбранные так, чтобы выполнялось соотношение:
. (10)
Обозначим .
Покажем, как определить βk и uk, чтобы . Используя ранее введенное выражение (4) Ak+1=k+Ack, перепишем (10) с учетом (9):
. (11)
Умножим скалярно обе части выражения (11) на γk, получим:
. (12)
Отсюда
. (13)
Используем тождество
(14)
и, осуществив замену
на (см. (11));
на (см. (13)),
получим формулу коррекции (ранга 1):
. (15)
Далее доказывается теорема о том, что для квадратичной функции f(x) с положительно определенной матрицей A последовательность матриц Ak сходится не более чем за n этапов к обращению матрицы A-1 гессиана функции f(x).
В формуле (8) положим
и .
Тогда получим:
(16)
Перепишем формулу (16) в виде:
. (17)
Матрица Ak+1 удовлетворяет соотношению:
. (18)
Если переставить местами δk и γk в (17) и рассмотреть последовательность матриц
, (19)
то полученные матрицы будут удовлетворять соотношению, обратному (17):
. (20)
Таким образом, выражение (19) позволяет построить аппроксимацию самого гессиана (а не его обращения).
Получим формулу для аппроксимации обращения гессиана из (19). После несложных выкладок можно получить выражение:
(20)
Заменяя (Gk)-1 на Ak, получим:
(21)
или
. (22)
Полученное уравнение называется симметричной формулой ранга один.
Достоинства: не всегда обязателен возврат к начальной итерации алгоритма и относительно слабая зависимость от точности вычислений одномерного поиска.

Алгоритм Бройдена–Флетчера–Гольдфарба–Шанно (БФГШ)

1. Выбрать начальную точку x0. Положить Н = I, где I- единичная матрица; K = 0.
2. На K-й итерации dK = – HKf(xK).
Найти такое λ > 0, чтобы f(xK+ λKdK) = min{f(xK + λdK)}. Положить xK+1 = xK + λKdK; sK = xK+1xK; gK = ▽f(xK+1) – ▽f(xK),
.
3. Тест на остановку: если выполнен, то конец. Иначе: выполнить k¬k+1 и возвратиться к 2.
загрузка...