Davidon-Fletcher-Powell Method

The Davidon-Fletcher-Powell (DFP) [Section 6.3.3] method belongs to the family of Variable Metric Methods (VMM),  The method was first introduced by Davidon and several years later was developed in its current form by Fletcher and Powell.  Like the Conjugate Gradient method, these methods have the property of quadratic convergence. Generally, these family of methods go beyond that. As the solution is approached they behave like theNewton’s method (Section 6.4). While the Newton’s method is presented later, its quadratic convergence property is quite impressive –it will locate the solution to a quadratic problem in one iteration.

This Newton-like behavior of the VMM, as the solution is approached has caused them to be referred as Quasi-Newton  or Newton-like Methods.
The DFP method is presented here for historical interest and also the fact it is a little easier to understand than the others.

The improvement  of the Conjugate Gradient method over the Steepest Descent method was possible because of the inclusion of the history from the previous iteration. In the quasi-Newton methods the history from all previous iterations is available. This information is collected in a n x n matrix called the metric. The metric is updated with each iteration and is used to establish the search direction. An initial choice for the metric is also required. It must be a symmetric positive definite matrix. For the method to converge the metric must hold on to its positive definite property through the iterations. In DFP method, the metric approaches the inverse of the Hessian at the solution.  This is a big bonus since the positive definiteness of the matrix will also establish sufficient conditions (SOC).  This happens without calculating the second derivative matrix, which is a no no in optimization


Algorithm: (A 6.7)
Step 1
step 1 dfp
Step 2
step 2 dfp
Step 3
step 3 dfp

MATLAB Code:
The DFP algorithm (A 6.7) is coded in the file DFP.m. Similar to the previous programs, for two variables the design changes are tracked on a background contour plot. The default initial metric is the identity matrix generated using a MATLAB built in function. GoldSection_nVar.m, along with UpperBound_nVar.m, gradfunction.m, and the problem file is also needed.

Usage:     DFP('Example6_1',[0.5 0.5],4,0.0001,0,1,20);

Output:    The output here is brief (as a result of commenting many of the fprintf statements).  Students are encourages to uncomment them to see how the numbers flow (this is available in the text):
>> DFP('Example6_1',[0.5 0.5],4,0.0001,0,1,20);
iteration number:       1
gradient length squared:      2.8411
objective function value:      4.7832
iteration number:       2
gradient length squared:    3.1140e-005
objective function value:      3.0000
The problem:  Example6_1

The design vector,function value and KT value
during the iterations
    0.5000    0.5000    5.3125    5.2969
    0.5996    0.9483    4.7832    2.8411
    2.9996    1.9987    3.0000    0.0000

% calling the program
% summary information for program control







% tabular information on the iterations



dfp graphical solution

Other VMM Techniques
There are several VMM methods, and you can create your own following Reference 7 in this chapter.  The most widely used is the Broyden-Fletcher-Goldfarb-Shanno (BFGS) available in Section 6.3.4.