UVMID
Finds the minimum point of a smooth function of a single variable using both function evaluations and first derivative evaluations.
Required Arguments
F — User-supplied function to define the function to be minimized. The form is
F(X), where
X — The point at which the function is to be evaluated. (Input)
F — The computed value of the function at X. (Output)
F must be declared EXTERNAL in the calling program.
G — User-supplied function to compute the derivative of the function. The form is
G(X), where
X — The point at which the derivative is to be computed. (Input)
G — The computed value of the derivative at X. (Output)
G must be declared EXTERNAL in the calling program.
A — A is the lower endpoint of the interval in which the minimum point of F is to be located. (Input)
B — B is the upper endpoint of the interval in which the minimum point of F is to be located. (Input)
X — The point at which a minimum value of F is found. (Output)
Optional Arguments
XGUESS — An initial guess of the minimum point of F. (Input)
Default: XGUESS = (a + b) / 2.0.
ERRREL — The required relative accuracy in the final value of X. (Input)
This is the first stopping criterion. On a normal return, the solution X is in an interval that contains a local minimum and is less than or equal to MAX(1.0, ABS(X)) * ERRREL. When the given ERRREL is less than machine epsilon, SQRT(machine epsilon) is used as ERRREL.
Default: ERRREL = 1.e-4.
GTOL — The derivative tolerance used to decide if the current point is a local minimum. (Input)
This is the second stopping criterion. X is returned as a solution when GX is less than or equal to GTOL. GTOL should be nonnegative, otherwise zero would be used.
Default: GTOL = 1.e-4.
MAXFN — Maximum number of function evaluations allowed. (Input)
Default: MAXFN = 1000.
FX — The function value at point X. (Output)
GX — The derivative value at point X. (Output)
FORTRAN 90 Interface
Generic: CALL UVMID (F, G, A, B, X [, …])
Specific: The specific interface names are S_UVMID and D_UVMID.
FORTRAN 77 Interface
Single: CALL UVMID (F, G, XGUESS, ERRREL, GTOL, MAXFN, A, B, X, FX, GX)
Double: The double precision name is DUVMID.
Description
The routine UVMID uses a descent method with either the secant method or cubic interpolation to find a minimum point of a univariate function. It starts with an initial guess and two endpoints. If any of the three points is a local minimum point and has least function value, the routine terminates with a solution. Otherwise, the point with least function value will be used as the starting point.
From the starting point, say xc, the function value fc = f (xc), the derivative value gc = g(xc), and a new point xn defined by xn = xc ‑ gc are computed. The function fn = f(xn), and the derivative gn = g(xn) are then evaluated. If either fn ≥ fc or gn has the opposite sign of gc, then there exists a minimum point between xc and xn; and an initial interval is obtained. Otherwise, since xc is kept as the point that has lowest function value, an interchange between xn and xc is performed. The secant method is then used to get a new point
Let xn←xs and repeat this process until an interval containing a minimum is found or one of the convergence criteria is satisfied. The convergence criteria are as follows:
Criterion 1:
Criterion 2:
where ɛc = max{1.0, ∣xc∣}ɛ, ɛ is a relative error tolerance and ɛg is a gradient tolerance.
When convergence is not achieved, a cubic interpolation is performed to obtain a new point. Function and derivative are then evaluated at that point; and accordingly, a smaller interval that contains a minimum point is chosen. A safeguarded method is used to ensure that the interval reduces by at least a fraction of the previous interval. Another cubic interpolation is then performed, and this procedure is repeated until one of the stopping criteria is met.
Comments
Informational errors
Type | Code | Description |
|---|
3 | 1 | The final value of X is at the lower bound. The minimum is probably beyond the bound. |
3 | 2 | The final value of X is at the upper bound. The minimum is probably beyond the bound. |
4 | 3 | The maximum number of function evaluations has been exceeded. |
Example
A minimum point of ex ‑ 5x is found.
USE UVMID_INT
USE UMACH_INT
IMPLICIT NONE
! Declare variables
INTEGER MAXFN, NOUT
REAL A, B, ERRREL, F, FX, G, GTOL, GX, X, XGUESS, FTOL
EXTERNAL F, G
! Initialize variables
XGUESS = 0.0
! Set ERRREL to zero in order
! to use SQRT(machine epsilon)
! as relative error
ERRREL = 0.0
GTOL = 0.0
A = -10.0
B = 10.0
MAXFN = 50
!
! Find minimum for F = EXP(X) - 5X
CALL UVMID (F, G, A, B, X, XGUESS=XGUESS, ERRREL=ERRREL, &
GTOL=FTOL, MAXFN=MAXFN, FX=FX, GX=GX)
! Print results
CALL UMACH (2, NOUT)
WRITE (NOUT,99999) X, FX, GX
!
99999 FORMAT (' The minimum is at ', 7X, F7.3, //, ' The function ' &
, 'value is ', F7.3, //, ' The derivative is ', F7.3)
!
END
! Real function: F = EXP(X) - 5.0*X
REAL FUNCTION F (X)
REAL X
!
REAL EXP
INTRINSIC EXP
!
F = EXP(X) - 5.0E0*X
!
RETURN
END
!
REAL FUNCTION G (X)
REAL X
!
REAL EXP
INTRINSIC EXP
!
G = EXP(X) - 5.0E0
RETURN
END
Output
The minimum is at 1.609
The function value is -3.047
The derivative is -0.001
