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

Назначение сервиса. Онлайн-калькулятор предназначен для нахождения минимума функции методом Бройдена-Флетчера-Шенно (BFGS).
f(x1,x2) =
Начиная из точки ( ; ). Точность ξ = .
Решение оформляется в формате Word.

Правила ввода функции

Примеры
x1^2/(x2+2)
Например, x12+x1x2x1^2+x1*x2
x1+(x2-1)^(2/3)

Квазиньютоновские методы также основаны на свойствах квадратичных функций. Данные методы обладают положительными чертами метода Ньютона, однако используют только первые производные.
Итерационный поиск по методу Ньютона осуществлялся по формуле (обобщенный случай с λ):
. (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.
Задать вопрос или оставить комментарий Помощь в решении Поиск Поддержать проект