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

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

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

${\displaystyle 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 ,}$

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

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

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

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

${\displaystyle 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},}$

где

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

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

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

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

${\displaystyle 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}}}.}$

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

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

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

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

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

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

Дальнейшее чтение [ править ]

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