Симметричный ранг один

Метод симметричного ранга 1 ( SR1 ) - это квазиньютоновский метод обновления второй производной (гессиана) на основе производных (градиентов), вычисленных в двух точках. Это обобщение метода секущих для многомерной задачи. Это обновление поддерживает симметрию матрицы, но не гарантирует, что обновление будет положительно определенным .

Последовательность приближений Гессе, генерируемая методом SR1, теоретически сходится к истинному гессиану при мягких условиях; На практике приближенные гессианы, полученные с помощью метода SR1, показывают более быстрый прогресс в направлении истинного гессиана, чем популярные альтернативы ( BFGS или DFP ) в предварительных численных экспериментах. ^{[1] [2]} Метод SR1 имеет вычислительные преимущества для разреженных или частично разделимых задач. ^[3]

Дважды непрерывно дифференцируемая функция имеет градиент ( ) и матрицу Гессе : функция имеет разложение в виде ряда Тейлора в точке , которая может быть усечена${\ Displaystyle х \ mapsto f (x)}$${\ displaystyle \ nabla f}$ ${\ displaystyle B}$${\ displaystyle f}$${\ displaystyle x_ {0}}$

${\ displaystyle f (x_ {0} + \ Delta x) \ приблизительно f (x_ {0}) + \ nabla f (x_ {0}) ^ {T} \ Delta x + {\ frac {1} {2}} \ Delta x ^ {T} {B} \ Delta x}$;

его градиент также имеет приближение ряда Тейлора.

${\ displaystyle \ nabla f (x_ {0} + \ Delta x) \ приблизительно \ nabla f (x_ {0}) + B \ Delta x}$,

который используется для обновления . Вышеупомянутое уравнение секущей не обязательно должно иметь единственное решение . Формула SR1 вычисляет (посредством обновления ранга 1) симметричное решение, которое наиболее близко к текущему приближенному значению :${\ displaystyle B}$${\ displaystyle B}$${\ displaystyle B_ {k}}$

${\ displaystyle B_ {k + 1} = B_ {k} + {\ frac {(y_ {k} -B_ {k} \ Delta x_ {k}) (y_ {k} -B_ {k} \ Delta x_ { k}) ^ {T}} {(y_ {k} -B_ {k} \ Delta x_ {k}) ^ {T} \ Delta x_ {k}}}}$,

куда

${\displaystyle y_{k}=\nabla f(x_{k}+\Delta x_{k})-\nabla f(x_{k})}$.

Соответствующее обновление приближенного обратного гессиана :${\displaystyle H_{k}=B_{k}^{-1}}$

${\displaystyle H_{k+1}=H_{k}+{\frac {(\Delta x_{k}-H_{k}y_{k})(\Delta x_{k}-H_{k}y_{k})^{T}}{(\Delta x_{k}-H_{k}y_{k})^{T}y_{k}}}}$.

Формула SR1 неоднократно открывалась заново. Недостатком является то, что знаменатель может исчезнуть. Некоторые авторы предлагают применять обновление только в том случае, если

${\displaystyle |\Delta x_{k}^{T}(y_{k}-B_{k}\Delta x_{k})|\geq r\|\Delta x_{k}\|\cdot \|y_{k}-B_{k}\Delta x_{k}\|}$,

где - небольшое число, например . ^[4]${\displaystyle r\in (0,1)}$${\displaystyle 10^{-8}}$

См. Также [ править ]

• Квазиньютоновский метод
• Метод Бройдена
• Метод Ньютона в оптимизации
• Метод Бройдена-Флетчера-Гольдфарба-Шанно (BFGS)
• L-BFGS метод

Ссылки [ править ]