For description of the algorithm see M.J.D.Powell, Recent Advances Unconstrained Optimization, Mathematical Programming, 1(1971),26-57.
NQ=i2 = NP*NP + 8*NP
IER = Greater than 0 if optimum is achieved
IER = 3 Function value is accurate to relative ACC
IER = 2 Norm of gradient is less than ACC
IER = 1 Attempted step size is less than ACC (relatively)
IER = -1 Iteration limit exceeded
IER = -2 Function error in FP or SP
IER = -3 Input error
IER = -4 Not enough scratch storage
IER = -9 Function error in first FUNC call
IER =-13 No stopping criterion enabled
IER =-14 Invalid H matrix input
SECTION 3.1 OPTIONS
Besides the general options the following are available.... The options which will most likely be of interest to the user are ISP,IST,FDFRAC,FOPT, and IVER in decreasing order.
IVER = 1 for Version 1 of DFP. Choice of 2 or 3 below.
R.Fletcher, A New Approach to Variable Metric Algorithms,
Computer Journal, Vol. 13, No. 3, 1970.
IVER = 2 for Version 2 of DFP. Davidon-Fletcher-Powell algorithm
IVER = 3 for Version 3 of DFP. Broyden's method.
IVER = 4 for Version 4 of DFP. Rank 1 correction formula.
Default value is 1.
LT For internal use only
IFP = 1 if symmetric 1st derivatives are desired.
IFP = 2 if simple 1st derivatives are desired.
IFP = 3 if choice of 1 or 2 (determined by Stewart).
See G.W.Stewart, A Modification of Davidon's Minimization Method to Accept Difference Approximations, Journal of the Association for Computing Machinery, Vol. 14, No. 1,1967.
Default value is 3. Note: The simple (one-sided) derivatives are cheaper but less accurate than the symmetric ones.
ISP = for GRADX only
NLOOP = Number of times the method loops trying to find an improved function value (Default value is 7).
IST = 0 if DFP step yields an improvement, no linear searching
= 1 if linear optimizing via DLNSR is desired.
= 2 if stretching via LNSR is desired.
Default value is 1.
ILOOP = For internal use only.
FDFRAC = Fraction of X(I) over which finite differences of the
function are taken for numerical derivatives (.0001 to .001)
Default value is .0001
FDMIN = Minimum acceptable value of FDFRAC*X(I). The equation used is E = MAX (ABS(X(I)*FDFRAC),FDMIN). Default is 1.D-6
STEP1 = Length of initial steepest descent (ascent) step.
Default value of 1.
STPACC = Accuracy required in linear optimizing. Default is ACC/NP.
NLNSR = Max number of steps in each linear search. Default is 20.
STPMIN = Minimum stepsize permitted in DFP step. Default is
FOPT = Best available estimate of optimum function value for the purpose of computing an initial step length. Default is 0.
INFLG = See Section 3.2
SECTION 3.2 SAVING THE H MATRIX
The H matrix (approximate inverse of second derivatives) which is produced by the DFP routine can be saved (in hex code) by
where X0 is the vector of variables and NP is the length. This feature is useful if the user needs to limit the number of iterations, but would like to continue the optimization later. The values of the variables are also saved by this routine. If optimization is to be continued later, it is important to use this option, for otherwise DFP will, at restart time, reinitialize the H matrix to the identity matrix. A call to PUNCH may be made at any point between use of DFP and the use of DERIV or another call to OPT.
To read these values in during a later run, the main program should include
The values for the variables are also
read, so it is unnecessary to initialize them in the main
program. INFLG should be reset to zero for an optimization which
does not require H matrix input.
Note: The subroutine PUNCH records the current values of the variables and the H matrix in a file with logical device number 9 (unless redefined by the user). Before executing a program with PUNCH(X0,NP) in it, the user should issue the command
The routine which reinitializes the variable values and the H matrix (in a subsequent run) assumes that the required numbers are in the file with logical number NREAD which also defaults to 9 (see COMMON/BREAD/NREAD in Section 1.1).It is generally practical not to give NREAD and NPUNCH different values. When DFP reads the numbers in the file, it then rewinds the file and subsequent output by the PUNCH subroutine overwrites the previously stored num- bers. Thus subsequent calls of DFP will first read the numbers recorded in the file in the previous run and then the PUNCH call will write out the new temporary result. In this way DFP can be called repetitively to execute a small number of itera- tions each time; each run will be properly initialized to the end point of the previous run without any further action by the user.
If the user is using the Stewart derivative routine (IFP=3), the program will not return exactly the same results as if the execution had never been interrupted. This should not affect their accuracy. For IFP = 1 or 2, the optimization will continue as if the interruption had never occurred, with precisely the same values for all matrices and variables.
Return to the Beginning