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

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

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

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

$f(x_{0}+\Delta x)\approx f(x_{0})+\nabla f(x_{0})^{T}\Delta x+{\frac {1}{2}}\Delta x^{T}{B}\Delta x$;

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

$\nabla f(x_{0}+\Delta x)\approx \nabla f(x_{0})+B\Delta x$,

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

$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}}}$,

где

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

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

$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}}}$.

Можно задаться вопросом, почему не сохраняется положительная определенность — в конце концов, обновление ранга 1 формы $B_{k+1}=B_{k}+vv^{T}$ положительно определен, если $B_{k}$ является. Объяснение состоит в том, что обновление может иметь форму $B_{k+1}=B_{k}-vv^{T}$ вместо этого потому, что знаменатель может быть отрицательным, и в этом случае нет никаких гарантий положительной определенности.

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

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

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

См. также

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