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

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

. Для функции $f\; (x)\; \{\backslash \; displaystyle\; f\; (x)\}$ее gradient ($\nabla \; f\; \{\backslash \; displaystyle\; \backslash \; nabla\; f\}$) и positive-definite матрица Гессе $B\; \{\backslash \; displaystyle\; B\}$, ряд Тейлора равен

$f\; (xk\; +\; sk)\; =\; f\; (xk)\; +\; \nabla \; f\; (xk)\; T\; sk\; +\; 1\; 2\; sk\; TB\; sk\; +\dots ,\; \{\backslash \; displaystyle\; f\; (x\_\; \{k\}\; +\; s\_\; \{k\})\; =\; f\; (x\_\; \{k\})\; +\; \backslash \; nabla\; f\; (x\_\; \{k\})\; ^\; \{T\}\; s\_\; \{k\}\; +\; \{\backslash \; frac\; \{1\}\; \{2\}\}\; s\_\; \{k\}\; ^\; \{T\}\; \{B\}\; s\_\; \{k\}\; +\; \backslash \; dots,\}$

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

$\nabla \; f\; (xk\; +\; sk)\; Знак\; равно\; \nabla \; е\; (xk)\; +\; B\; sk\; +\dots \; \{\backslash \; displaystyle\; \backslash \; nabla\; f\; (x\_\; \{k\}\; +\; s\_\; \{k\})\; =\; \backslash \; nabla\; f\; (x\_\; \{k\})\; +\; Bs\_\; \{k\}\; +\; \backslash \; dots\}$

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

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

$В\; К\; +\; 1\; знак\; равно\; (I\; -\; \gamma \; kyksk\; T)\; B\; k\; (I\; -\; \gamma \; kskyk\; T)\; +\; \gamma \; kykyk\; T,\; \{\backslash \; displaystyle\; B\_\; \{k\; +\; 1\}\; =\; (I-\; \backslash \; gamma\; \_\; \{k\}\; y\_\; \{k\}\; s\_\; \{k\}\; ^\; \{T\})\; B\_\; \{k\}\; (I-\; \backslash \; gamma\; \_\; \{k\}\; s\_\; \{k\}\; y\_\; \{k\}\; ^\; \{T\})\; +\; \backslash \; gamma\; \_\; \{k\}\; y\_\; \{k\}\; y\_\; \{k\}\; ^\; \{T\},\}$

где

$yk\; =\; \nabla \; f\; (xk\; +\; sk)\; -\; \nabla \; f\; (xk),\; \{\backslash \; displaystyle\; y\_\; \{k\}\; =\; \backslash \; nabla\; f\; (x\_\; \{k\}\; +\; s\_\; \{k\})\; -\; \backslash \; nabla\; f\; (x\_\; \{k\}),\}$

$\gamma \; k\; =\; 1\; yk\; T\; sk,\; \{\backslash \; displaystyle\; \backslash \; gamma\; \_\; \{\; k\}\; =\; \{\backslash \; frac\; \{1\}\; \{y\_\; \{k\}\; ^\; \{T\}\; s\_\; \{k\}\}\},\}$

и $B\; k\; \{\backslash \; displaystyle\; B\_\; \{k\}\}$симметричная и положительно определенная матрица.

Соответствующее обновление обратного приближения Гессе $H\; k\; =\; B\; k\; -\; 1\; \{\backslash \; displaystyle\; H\_\; \{k\}\; =\; B\_\; \{k\}\; ^\; \{-\; 1\}\}$определяется как

$H\; k\; +\; 1\; =\; H\; k\; -\; H\; kykyk\; TH\; kyk\; TH\; kyk\; +\; sksk\; T\; yk\; T\; sk.\; \{\backslash \; displaystyle\; H\_\; \{k\; +\; 1\}\; =\; H\_\; \{k\}\; -\; \{\backslash \; frac\; \{H\_\; \{k\}\; y\_\; \{k\}\; y\_\; \{k\}\; ^\; \{T\}\; H\_\; \{k\}\}\; \{y\_\; \{k\}\; ^\; \{T\}\; H\_\; \{k\}\; y\_\; \{k\}\}\}\; +\; \{\backslash \; frac\; \{s\_\; \{k\}\; s\_\; \{k\}\; ^\; \{T\}\}\; \{y\_\; \{k\}\; ^\; \{T\}\; s\_\; \{k\}\}\}.\}$

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

$sk\; T\; yk\; =\; sk\; TB\; sk>0.\; \{\backslash \; displaystyle\; s\_\; \{k\}\; ^\; \{T\}\; y\_\; \{k\}\; =\; s\_\; \{k\}\; ^\; \{T\}\; Bs\_\; \{k\}>0.\}$

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

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

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