UMCGF
Minimizes a function of N variables using a conjugate gradient algorithm and a finite-difference gradient.
Required Arguments
FCN — User-supplied subroutine to evaluate the function to be minimized. The usage is
CALL FCN (N, X, F), where
N – Length of X. (Input)
X – The point at which the function is evaluated. (Input)
X should not be changed by FCN.
F – The computed function value at the point X. (Output)
FCN must be declared EXTERNAL in the calling program.
DFPRED — A rough estimate of the expected reduction in the function. (Input)
DFPRED is used to determine the size of the initial change to X.
X — Vector of length N containing the computed solution. (Output)
Optional Arguments
N — Dimension of the problem. (Input)
Default: N = SIZE (X,1).
XGUESS — Vector of length N containing the initial guess of the minimum. (Input)
Default: XGUESS = 0.0.
XSCALE — Vector of length N containing the diagonal scaling matrix for the variables. (Input)
Default: XSCALE = 1.0.
GRADTL — Convergence criterion. (Input)
The calculation ends when the sum of squares of the components of G is less than GRADTL.
Default: GRADTL = 1.e-4.
MAXFN — Maximum number of function evaluations. (Input)
If MAXFN is set to zero, then no restriction on the number of function evaluations is set.
Default: MAXFN = 0.
G — Vector of length N containing the components of the gradient at the final parameter estimates. (Output)
FVALUE — Scalar containing the value of the function at the computed solution. (Output)
FORTRAN 90 Interface
Generic: CALL UMCGF (FCN, DFPRED, X [, …])
Specific: The specific interface names are S_UMCGF and D_UMCGF.
FORTRAN 77 Interface
Single: CALL UMCGF (FCN, N, XGUESS, XSCALE, GRADTL, MAXFN, DFPRED, X, G, FVALUE)
Double: The double precision name is DUMCGF.
Description
The routine UMCGF uses a conjugate gradient method to find the minimum of a function f (x) of n variables. Only function values are required.
The routine is based on the version of the conjugate gradient algorithm described in Powell (1977). The main advantage of the conjugate gradient technique is that it provides a fast rate of convergence without the storage of any matrices. Therefore, it is particularly suitable for unconstrained minimization calculations where the number of variables is so large that matrices of dimension
n cannot be stored in the main memory of the computer. For smaller problems, however, a routine such as routine
UMINF, is usually more efficient because each iteration makes use of additional information from previous iterations.
Since a finite-difference method is used to estimate the gradient for some single precision calculations, an inaccurate estimate of the gradient may cause the algorithm to terminate at a noncritical point. In such cases, high precision arithmetic is recommended. Also, whenever the exact gradient can be easily provided, routine
UMCGG should be used instead.
Comments
1. Workspace may be explicitly provided, if desired, by use of U2CGF/DU2CGF. The reference is:
CALL U2CGF (FCN, N, XGUESS, XSCALE, GRADTL, MAXFN, DFPRED, X, G, FVALUE, S, RSS, RSG, GINIT, XOPT, GOPT)
The additional arguments are as follows:
S — Vector of length N used for the search direction in each iteration.
RSS — Vector of length N containing conjugacy information.
RSG — Vector of length N containing conjugacy information.
GINIT — Vector of length N containing the gradient values at the start of an iteration.
XOPT — Vector of length N containing the parameter values that yield the least calculated value for FVALUE.
GOPT — Vector of length N containing the gradient values that yield the least calculated value for FVALUE.
2. Informational errors
Type | Code | Description |
|---|
4 | 1 | The line search of an integration was abandoned. This error may be caused by an error in gradient. |
4 | 2 | The calculation cannot continue because the search is uphill. |
4 | 3 | The iteration was terminated because MAXFN was exceeded. |
3 | 4 | The calculation was terminated because two consecutive iterations failed to reduce the function. |
3. Because of the close relation between the conjugate-gradient method and the method of steepest descent, it is very helpful to choose the scale of the variables in a way that balances the magnitudes of the components of a typical gradient vector. It can be particularly inefficient if a few components of the gradient are much larger than the rest.
4. If the value of the parameter GRADTL in the argument list of the routine is set to zero, then the subroutine will continue its calculation until it stops reducing the objective function. In this case, the usual behavior is that changes in the objective function become dominated by computer rounding errors before precision is lost in the gradient vector. Therefore, because the point of view has been taken that the user requires the least possible value of the function, a value of the objective function that is small due to computer rounding errors can prevent further progress. Hence, the precision in the final values of the variables may be only about half the number of significant digits in the computer arithmetic, but the least value of FVALUE is usually found to be quite accurate.
Example
The function
is minimized and the solution is printed.
USE UMCGF_INT
USE UMACH_INT
IMPLICIT NONE
! Declaration of variables
INTEGER N
PARAMETER (N=2)
!
INTEGER I, MAXFN, NOUT
REAL DFPRED, FVALUE, G(N), GRADTL, X(N), XGUESS(N)
EXTERNAL ROSBRK
!
DATA XGUESS/-1.2E0, 1.0E0/
!
DFPRED = 0.2
GRADTL = 1.0E-6
MAXFN = 100
! Minimize the Rosenbrock function
CALL UMCGF (ROSBRK, DFPRED, X, xguess=xguess, gradtl=gradtl, &
g=g, fvalue=fvalue)
! Print the results
CALL UMACH (2, NOUT)
WRITE (NOUT,99999) (X(I),I=1,N), FVALUE, (G(I),I=1,N)
99999 FORMAT (' The solution is ', 2F8.3, //, ' The function ', &
'evaluated at the solution is ', F8.3, //, ' The ', &
'gradient is ', 2F8.3, /)
!
END
!
SUBROUTINE ROSBRK (N, X, F)
INTEGER N
REAL X(N), F
!
F = 1.0E2*(X(2)-X(1)*X(1))**2 + (1.0E0-X(1))**2
RETURN
END
Output
The solution is 0.999 0.998
The function evaluated at the solution is 0.000
The gradient is -0.001 0.000
