UMINF

Minimizes a function of N variables using a quasi-Newton method 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.

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.

X — Vector of length N containing the computed solution. (Output)

Optional Arguments

N — Dimension of the problem. (Input)

Default: N = SIZE (X,1).

Default: N = SIZE (X,1).

XGUESS — Vector of length N containing an initial guess of the computed solution. (Input)

Default: XGUESS = 0.0.

Default: XGUESS = 0.0.

XSCALE — Vector of length N containing the diagonal scaling matrix for the variables. (Input)

XSCALE is used mainly in scaling the gradient and the distance between two points. In the absence of other information, set all entries to 1.0.

Default: XSCALE = 1.0.

XSCALE is used mainly in scaling the gradient and the distance between two points. In the absence of other information, set all entries to 1.0.

Default: XSCALE = 1.0.

FSCALE — Scalar containing the function scaling. (Input)

FSCALE is used mainly in scaling the gradient. In the absence of other information, set FSCALE to 1.0.

Default: FSCALE = 1.0.

FSCALE is used mainly in scaling the gradient. In the absence of other information, set FSCALE to 1.0.

Default: FSCALE = 1.0.

IPARAM — Parameter vector of length 7. (Input/Output)

Set IPARAM(1) to zero for default values of IPARAM and RPARAM. See Comment 4.

Default: IPARAM = 0.

Set IPARAM(1) to zero for default values of IPARAM and RPARAM. See Comment 4.

Default: IPARAM = 0.

RPARAM — Parameter vector of length 7.(Input/Output)

See Comment 4.

See Comment 4.

FVALUE — Scalar containing the value of the function at the computed solution. (Output)

FORTRAN 90 Interface

Generic: CALL UMINF (FCN, X [, …])

Specific: The specific interface names are S_UMINF and D_UMINF.

FORTRAN 77 Interface

Single: CALL UMINF (FCN, N, XGUESS, XSCALE, FSCALE, IPARAM, RPARAM, X, FVALUE)

Double: The double precision name is DUMINF.

Description

The routine UMINF uses a quasi-Newton method to find the minimum of a function f(x) of n variables. Only function values are required. The problem is stated as follows:

Given a starting point xc, the search direction is computed according to the formula

d = -B-1 gc

where B is a positive definite approximation of the Hessian and gc is the gradient evaluated at xc. A line search is then used to find a new point

xn = xc + λd, λ > 0

such that

f(xn) ≤ f(xc) + αgT d, α ∈ (0, 0.5)

Finally, the optimality condition ∥g(x)∥ = ɛ is checked where ɛ is a gradient tolerance.

When optimality is not achieved, B is updated according to the BFGS formula

where s = xn ‑ xc and y = gn ‑ gc. Another search direction is then computed to begin the next iteration. For more details, see Dennis and Schnabel (1983, Appendix A).

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, IMSL routine UMING should be used instead.

Comments

1. Workspace may be explicitly provided, if desired, by use of U2INF/DU2INF. The reference is:

CALL U2INF (FCN, N, XGUESS, XSCALE, FSCALE, IPARAM, RPARAM, X, FVALUE, WK)

The additional argument is:

WK — Work vector of length N(N + 8). WK contains the following information on output: The second N locations contain the last step taken. The third N locations contain the last Newton step. The fourth N locations contain an estimate of the gradient at the solution. The final N2 locations contain the Cholesky factorization of a BFGS approximation to the Hessian at the solution.

2. Informational errors

Type | Code | Description |
---|---|---|

4 | 2 | The iterates appear to be converging to a noncritical point. |

4 | 3 | Maximum number of iterations exceeded. |

4 | 4 | Maximum number of function evaluations exceeded. |

4 | 5 | Maximum number of gradient evaluations exceeded. |

4 | 6 | Five consecutive steps have been taken with the maximum step length. |

2 | 7 | Scaled step tolerance satisfied; the current point may be an approximate local solution, or the algorithm is making very slow progress and is not near a solution, or STEPTL is too big. |

3 | 8 | The last global step failed to locate a lower point than the current X value. |

3. The first stopping criterion for UMINF occurs when the infinity norm of the scaled gradient is less than the given gradient tolerance (RPARAM(1)). The second stopping criterion for UMINF occurs when the scaled distance between the last two steps is less than the step tolerance (RPARAM(2)).

4. If the default parameters are desired for UMINF, then set IPARAM(1) to zero and call the routine UMINF. Otherwise, if any nondefault parameters are desired for IPARAM or RPARAM, then the following steps should be taken before calling UMINF:

CALL U4INF (IPARAM, RPARAM)

Set nondefault values for desired IPARAM, RPARAM elements.

Note that the call to U4INF will set IPARAM and RPARAM to their default values so only nondefault values need to be set above.

The following is a list of the parameters and the default values:

IPARAM — Integer vector of length 7.

IPARAM(1) = Initialization flag.

IPARAM(2) = Number of good digits in the function

Default: Machine dependent.

Default: Machine dependent.

IPARAM(3) = Maximum number of iterations.

Default: 100.

Default: 100.

IPARAM(4) = Maximum number of function evaluations.

Default: 400.

Default: 400.

IPARAM(5) = Maximum number of gradient evaluations.

Default: 400.

Default: 400.

IPARAM(6) = Hessian initialization parameter.

If IPARAM(6) = 0, the Hessian is initialized to the identity matrix; otherwise, it is initialized to a diagonal matrix containing

If IPARAM(6) = 0, the Hessian is initialized to the identity matrix; otherwise, it is initialized to a diagonal matrix containing

on the diagonal where t = XGUESS, fs = FSCALE, and s = XSCALE.

Default: 0.

Default: 0.

IPARAM(7) = Maximum number of Hessian evaluations.

Default: Not used in UMINF.

Default: Not used in UMINF.

RPARAM — Real vector of length 7.

RPARAM(1) = Scaled gradient tolerance.

The i-th component of the scaled gradient at x is calculated as

The i-th component of the scaled gradient at x is calculated as

where g = ∇f (x), s = XSCALE, and fs = FSCALE.

Default:

Default:

in double where ɛ is the machine precision.

RPARAM(2) = Scaled step tolerance. (STEPTL)

The i-th component of the scaled step between two points x and y is computed as

The i-th component of the scaled step between two points x and y is computed as

where s = XSCALE.

Default: ɛ2/3 where ɛ is the machine precision.

Default: ɛ2/3 where ɛ is the machine precision.

RPARAM(3) = Relative function tolerance.

Default: Not used in UMINF.

Default: Not used in UMINF.

RPARAM(4) = Absolute function tolerance

Default: Not used in UMINF.

Default: Not used in UMINF.

RPARAM(5) = False convergence tolerance.

Default: Not used in UMINF.

Default: Not used in UMINF.

RPARAM(6) = Maximum allowable step size.

Default: 1000 max(ɛ1, ɛ2) where

Default: 1000 max(ɛ1, ɛ2) where

RPARAM(7) = Size of initial trust region radius.

Default: Not used in UMINF.

Default: Not used in UMINF.

If double precision is required, then DU4INF is called, and RPARAM is declared double precision.

5. Users wishing to override the default print/stop attributes associated with error messages issued by this routine are referred to “Error Handling” in the Introduction.

Example

The function

is minimized.

USE UMINF_INT

USE U4INF_INT

USE UMACH_INT

IMPLICIT NONE

INTEGER N

PARAMETER (N=2)

!

INTEGER IPARAM(7), L, NOUT

REAL F, RPARAM(7), X(N), XGUESS(N), &

XSCALE(N)

EXTERNAL ROSBRK

!

DATA XGUESS/-1.2E0, 1.0E0/

!

! Relax gradient tolerance stopping

! criterion

CALL U4INF (IPARAM, RPARAM)

RPARAM(1) = 10.0E0*RPARAM(1)

! Minimize Rosenbrock function using

! initial guesses of -1.2 and 1.0

CALL UMINF (ROSBRK, X, XGUESS=XGUESS, IPARAM=IPARAM, RPARAM=RPARAM, &

FVALUE=F)

! Print results

CALL UMACH (2, NOUT)

WRITE (NOUT,99999) X, F, (IPARAM(L),L=3,5)

!

99999 FORMAT (' The solution is ', 6X, 2F8.3, //, ' The function ', &

'value is ', F8.3, //, ' The number of iterations is ', &

10X, I3, /, ' The number of function evaluations is ', &

I3, /, ' The number of gradient evaluations is ', I3)

!

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 1.000 1.000

The function value is 0.000

The number of iterations is 15

The number of function evaluations is 40

The number of gradient evaluations is 19