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

• Ввод данных
• Инструкция
• Оформление Word

f(x₁,x₂) =

Начиная из точки ( ; ). Точность ξ = .

...load... Действия

• Загрузить предыдущие

Решение оформляется в формате Word.

Видеоинструкция

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

1. Все переменные выражаются через x1,x2

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

Скачать пример оформления

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

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

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

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

(20)

(21)

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