Формула Дэвидона – Флетчера – Пауэлла - Davidon–Fletcher–Powell formula

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

Учитывая функцию ${displaystyle f(x)}$, это градиент (${displaystyle abla f}$), и положительно определенный Матрица Гессе ${displaystyle B}$, то Серия Тейлор является

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

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

${displaystyle abla f(x_{k}+s_{k})=abla 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}=abla f(x_{k}+s_{k})-abla 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 довольно эффективна, но вскоре ее заменила Формула Бройдена – Флетчера – Гольдфарба – Шенно, что является его двойной (меняя ролями у и s).^[1]

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

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

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

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

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

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