Формула Дэвидона – Флетчера – Пауэлла - 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} + точки,}$

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

${displaystyle abla f (x_ {k} + s_ {k}) = abla f (x_ {k}) + Bs_ {k} + точки}$

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

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

${displaystyle B_ {k + 1} = (I-гамма _ {k} y_ {k} s_ {k} ^ {T}) B_ {k} (I-гамма _ {k} s_ {k} y_ {k} ^ {T}) + гамма _ {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 с ограниченной памятью
• Симметричная формула ранга один
• Метод Нелдера – Мида

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

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

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