Симметричный ранг один - Symmetric rank-one

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

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

Дважды непрерывно дифференцируемая функция ${displaystyle xmapsto f(x)}$ имеет градиент (${displaystyle abla f}$) и Матрица Гессе ${displaystyle B}$: Функция ${displaystyle f}$ имеет расширение как Серия Тейлор в ${displaystyle x_{0}}$, который можно усечь

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

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

${displaystyle abla f(x_{0}+Delta x)approx abla f(x_{0})+BDelta x}$,

который используется для обновления ${displaystyle B}$. Вышеупомянутое уравнение секущей не обязательно должно иметь единственное решение. ${displaystyle B}$.Формула SR1 вычисляет (путем обновления классифицировать 1) симметричное решение, наиболее близкое к текущему приближенному значению ${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}=abla f(x_{k}+Delta x_{k})-abla 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}|}$,

куда ${displaystyle rin (0,1)}$ это небольшое число, например ${displaystyle 10^{-8}}$.^[4]

Смотрите также

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

Рекомендации

1. Conn, A.R .; Гулд, Н. И. М .; Toint, Ph. L. (март 1991 г.). «Сходимость квазиньютоновских матриц, порожденных симметричным обновлением ранга один». Математическое программирование. Springer Berlin / Heidelberg. 50 (1): 177–195. Дои:10.1007 / BF01594934. ISSN  0025-5610.
2. Халфан, Х. Файез; и другие. (1993). «Теоретическое и экспериментальное исследование симметричного обновления первого ранга». SIAM Journal по оптимизации. 3 (1): 1–24. Дои:10.1137/0803001.
3. Берд, Ричард Х .; и другие. (1996). «Анализ метода симметричной области доверия первого ранга». SIAM Journal по оптимизации. 6 (4): 1025–1039. Дои:10.1137 / S1052623493252985.
4. Нокедаль, Хорхе; Райт, Стивен Дж. (1999). Численная оптимизация. Springer. ISBN  0-387-98793-2.