Этот метод имеет и другие названия - метод переменной метрики, квазиньютоновский метод, т.к. он использует оба эти подхода.
Метод Дэвидона-Флетчера-Пауэла (ДФП) основан на использовании ньютоновских направлений, но не требует вычисления обратного гессиана на каждом шаге. Направление поиска на шаге k является направлением , где H i - положительно определенная симметричная матрица, которая обновляется на каждом шаге и в пределе становится равной обратному гессиану. В качестве начальной матрицы H обычно выбирают единичную. Итерационная процедура ДФП может быть представлена следующим образом:
1. На шаге k имеются точка Xkи положительно определенная матрица Hk.
2. В качестве нового направления поиска выбирается
3. Одномерным поиском (обычно кубической интерполяцией) вдоль направления определяется lk, минимизирующее функцию .
4. Полагается .
5. Полагается .
6. Определяется и . Если |Vk| или достаточно малы, процедура завершается.
7. Полагается Uk = Ñf(Xk+1) - Ñf(Xk).
8. Матрица Hkобновляется по формуле
9. Увеличить k на единицу и вернуться на шаг 2.
Метод эффективен на практике, если ошибка вычислений градиента невелика и матрица Hkне становится плохо обусловленной.
Матрица Akобеспечивает сходимость Hkк G-1, матрица Bkобеспечивает положительную определенность Hk+1на всех этапах и в пределе исключает H0.
В случае квадратичной функции , т.е. алгоритм ДФП использует сопряженные направления.
Таким образом, метод ДФП использует как идеи ньютоновского подхода, так и свойства сопряженных направлений, и при минимизации квадратичной функции сходится не более чем за n итераций. Если оптимизируемая функция имеет вид, близкий к квадратичной функции, то метод ДФП эффективен за счет хорошей аппроксимации G-1(метод Ньютона). Если же целевая функция имеет общий вид, то метод ДФП эффективен за счет использования сопряженных направлений.
На практике оказалось, что метод ДФП может давать отрицательные шаги или окончиться в нестационарной точке. Это возможно, когда Hk+1становится плохо обусловленной. Этого можно избежать путем увеличения числа получаемых значимых цифр или перезаданием матрицы Hk+1в виде специальной диагональной матрицы H, где
.
Ошибки округления и особенно неточность линейного поиска может послужить причиной потери устойчивости метода ДФП и даже привести к ошибочным шагам, когда значение целевой функции на некоторой итерации возрастает вместо того, чтобы уменьшаться.
По классификации Ньютоновских методов данный алгоритм является квази-Ньютоновским, хотя он использует в явном виде только первые частные производные, а значит, может рассматриваться и как градиентный метод.
Практическая проверка эффективности алгоритма показала, что он столь же эффективен, как и метод Флетчера-Ривса.