Формула Дэвидона – Флетчера – Пауэлла

Формула Дэвидона-Флетчера-Пауэлла (или DFP ; названа в честь Уильяма К. Дэвидона , Роджера Флетчера и Майкла Дж. Д. Пауэлла ) находит решение секущего уравнения, которое наиболее близко к текущей оценке и удовлетворяет условию кривизны. Это был первый квазиньютоновский метод , обобщивший метод секущих на многомерную задачу. Это обновление сохраняет симметрию и положительную определенность матрицы Гессе .

Дана функция $f(x)$, его градиент ( $\nabla f$) и положительно определённая матрица Гессе $B$, Тейлора ряд

$f(x_{k}+s_{k})=f(x_{k})+\nabla f(x_{k})^{T}s_{k}+{\frac {1}{2}}s_{k}^{T}{B}s_{k}+\dots ,$

и ряд Тейлора самого градиента (уравнение секущего)

$\nabla f(x_{k}+s_{k})=\nabla f(x_{k})+Bs_{k}+\dots$

используется для обновления $B$.

Формула DFP находит решение, которое является симметричным, положительно определенным и наиболее близким к текущему приблизительному значению $B_{k}$:

$B_{k+1}=(I-\gamma _{k}y_{k}s_{k}^{T})B_{k}(I-\gamma _{k}s_{k}y_{k}^{T})+\gamma _{k}y_{k}y_{k}^{T},$

где

$y_{k}=\nabla f(x_{k}+s_{k})-\nabla f(x_{k}),$

$\gamma _{k}={\frac {1}{y_{k}^{T}s_{k}}},$

и $B_{k}$ является симметричной и положительно определенной матрицей .

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

$H_{k+1}=H_{k}-{\frac {H_{k}y_{k}y_{k}^{T}H_{k}}{y_{k}^{T}H_{k}y_{k}}}+{\frac {s_{k}s_{k}^{T}}{y_{k}^{T}s_{k}}}.$

$B$ предполагается положительно определенным, а векторы $s_{k}^{T}$ и $y$ должно удовлетворять условию кривизны

$s_{k}^{T}y_{k}=s_{k}^{T}Bs_{k}>0.$

Формула DFP довольно эффективна, но вскоре она была заменена формулой Бройдена-Флетчера-Гольдфарба-Шенно , которая является ее двойственной (меняющей роли y и s ).

См. также

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

Дальнейшее чтение

• Дэвидон, WC (1959). «Метод переменной метрики для минимизации» . Отчет об исследованиях и разработках AEC ANL-5990 . дои : 10.2172/4252678 . hdl : 2027/mdp.39015078508226 .
• Флетчер, Роджер (1987). Практические методы оптимизации (2-е изд.). Нью-Йорк: Джон Уайли и сыновья. ISBN  978-0-471-91547-8 .
• Ковалик, Дж.; Осборн, MR (1968). Методы решения задач безусловной оптимизации . Нью-Йорк: Эльзевир. стр. 45–48 . ISBN  0-444-00041-0 .
• Носедаль, Хорхе; Райт, Стивен Дж. (1999). Численная оптимизация . Спрингер-Верлаг. ISBN  0-387-98793-2 .
• Уолш, Г. Р. (1975). Методы оптимизации . Лондон: Джон Уайли и сыновья. стр. 110–120. ISBN  0-471-91922-5 .