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

Формула Дэвидона -Флетчера-Пауэлла (или 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 с ограниченной памятью
• Симметричная формула первого ранга
• Метод Нелдера-Мида

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

1. Авриэль, Мордехай (1976). Нелинейное программирование: анализ и методы . Прентис-Холл. стр. 352–353. ISBN 0-13-623603-0.

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

• Дэвидон, 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.