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

Формула Дэвидона–Флетчера–Пауэлла (или 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]

Компактное представление

Развернув матричную рекуррентность для , формулу DFP можно выразить как компактное матричное представление . В частности, определяя ${\displaystyle B_{k}}$

$${\displaystyle S_{k}={\begin{bmatrix}s_{0}&s_{1}&\ldots &s_{k-1}\end{bmatrix}},}$$ $${\displaystyle Y_{k}={\begin{bmatrix}y_{0}&y_{1}&\ldots &y_{k-1}\end{bmatrix}},}$$

и верхние треугольные и диагональные матрицы

$${\displaystyle {\big (}R_{k}{\big )}_{ij}:={\big (}R_{k}^{\text{SY}}{\big )}_{ij}=s_{i-1}^{T}y_{j-1},\quad {\big (}R_{k}^{\text{YS}}{\big )}_{ij}=y_{i-1}^{T}s_{j-1},\quad (D_{k})_{ii}:={\big (}D_{k}^{\text{SY}}{\big )}_{ii}=s_{i-1}^{T}y_{i-1}\quad \quad {\text{ for }}1\leq i\leq j\leq k}$$

матрица DFP имеет эквивалентную формулу

$${\displaystyle B_{k}=B_{0}+J_{k}N_{k}^{-1}J_{k}^{T},}$$

$${\displaystyle J_{k}={\begin{bmatrix}Y_{k}&Y_{k}-B_{0}S_{k}\end{bmatrix}}}$$

$${\displaystyle N_{k}={\begin{bmatrix}0_{k\times k}&R_{k}^{\text{YS}}\\{\big (}R_{k}^{\text{YS}}{\big )}^{T}&R_{k}+R_{k}^{T}-(D_{k}+S_{k}^{T}B_{0}S_{k})\end{bmatrix}}}$$

Обратное компактное представление можно найти, применив обратное представление Шермана-Моррисона-Вудбери к . Компактное представление особенно полезно для задач с ограниченной памятью и ограничениями. ^[2] ${\displaystyle B_{k}}$

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

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

Ссылки

1. Avriel, Mordecai (1976). Нелинейное программирование: анализ и методы . Prentice-Hall. стр. 352–353. ISBN 0-13-623603-0.
2. Бруст, Дж. Дж. (2024). «Полезные компактные представления для подгонки данных». arXiv : 2403.12206 [math.OC].

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

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