Finds the minimum point of a smooth function of a single variable using only function evaluations.
F — User-supplied
function to compute the value of the function to be minimized. The form is F(X), where
X – The point at which
the function is evaluated. (Input)
X should not be
changed by F.
F – The computed function value at the
point X.
(Output)
F must be declared EXTERNAL in the calling program.
XGUESS — An initial guess of the minimum point of F. (Input)
BOUND — A positive number that limits the amount by which X may be changed from its initial value. (Input)
X — The point at which a minimum value of F is found. (Output)
STEP — An order
of magnitude estimate of the required change in X.
(Input)
Default: STEP = 1.0.
XACC — The
required absolute accuracy in the final value of X. (Input)
On a normal return there are points on either side of X within a distance
XACC at which
F is no less
than F(X).
Default: XACC = 1.e-4.
MAXFN — Maximum
number of function evaluations allowed. (Input)
Default: MAXFN = 1000.
Generic: CALL UVMIF (F, XGUESS, BOUND, X [,…])
Specific: The specific interface names are S_UVMIF and D_UVMIF.
Single: CALL UVMIF (F, XGUESS, STEP, BOUND, XACC, MAXFN, X)
Double: The double precision name is DUVMIF.
The routine UVMIF uses a safeguarded quadratic interpolation method to find a minimum point of a univariate function. Both the code and the underlying algorithm are based on the routine ZXLSF written by M.J.D. Powell at the University of Cambridge.
The routine UVMIF
finds the least value of a univariate function, f, that is specified by
the function subroutine F.
Other required data include an initial estimate of the solution, XGUESS
, and a positive number BOUND.
Let x0 = XGUESS
and b = BOUND,
then x is restricted to the interval
[x0 − b,
x0 + b]. Usually,
the algorithm begins the search by moving from x0 to x =
x0 + s,
where
s = STEP
is also provided by the user and may be positive or negative. The first two
function evaluations indicate the direction to the minimum point, and the search
strides out along this direction until a bracket on a minimum point is found or
until x reaches one of the bounds x0 ± b. During
this stage, the step length increases by a factor of between two and nine per
function evaluation; the factor depends on the position of the minimum point
that is predicted by quadratic interpolation of the three most recent function
values.
When an interval containing a solution has been found, we will have three points, x1, x2, and x3, with x1< x2 < x0 and f (x2) ≤ f (x1) and f (x2) ≤ f (x3). There are three main ingredients in the technique for choosing the new x from these three points. They are (i) the estimate of the minimum point that is given by quadratic interpolation of the three function values, (ii) a tolerance parameter ɛ, that depends on the closeness of f to a quadratic, and (iii) whether x2 is near the center of the range between x1 and x3 or is relatively close to an end of this range. In outline, the new value of x is as near as possible to the predicted minimum point, subject to being at least ɛ from x2, and subject to being in the longer interval between x1 and x2 or x2 and x3 when x2 is particularly close to x1 or x3. There is some elaboration, however, when the distance between these points is close to the required accuracy; when the distance is close to the machine precision; or when ɛ is relatively large.
The algorithm is intended to provide fast convergence when f has a positive and continuous second derivative at the minimum and to avoid gross inefficiencies in pathological cases, such as
f (x) = x + 1.001|x|
The algorithm can make ɛ large automatically in the pathological cases. In this case, it is usual for a new value of x to be at the midpoint of the longer interval that is adjacent to the least calculated function value. The midpoint strategy is used frequently when changes to f are dominated by computer rounding errors, which will almost certainly happen if the user requests an accuracy that is less than the square root of the machine precision. In such cases, the routine claims to have achieved the required accuracy if it knows that there is a local minimum point within distance d of x, where d = XACC, even though the rounding errors in f may cause the existence of other local minimum points nearby. This difficulty is inevitable in minimization routines that use only function values, so high precision arithmetic is recommended.
Informational errors
Type Code
3 1 Computer rounding errors prevent further refinement of X.
3 2 The final value of X is at a bound. The minimum is probably beyond the bound.
4 3 The number of function evaluations has exceeded MAXFN.
A minimum point of ex - 5x is found.
USE
UVMIF_INT
USE UMACH_INT
IMPLICIT
NONE
! Declare variables
INTEGER MAXFN, NOUT
REAL BOUND, F, FX, STEP, X, XACC, XGUESS
EXTERNAL F
! Initialize variables
XGUESS = 0.0
XACC = 0.001
BOUND = 100.0
STEP = 0.1
MAXFN = 50
!
! Find minimum for F = EXP(X) - 5X
CALL UVMIF (F, XGUESS, BOUND, X, STEP=STEP, XACC=XACC, MAXFN=MAXFN)
FX = F(X)
! Print results
CALL UMACH (2, NOUT)
WRITE (NOUT,99999) X, FX
!
99999 FORMAT (' The minimum is at ', 7X, F7.3, //, ' The function ' &
, 'value 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
The minimum is
at 1.609
The
function value is -3.047
|
Visual Numerics, Inc. PHONE: 713.784.3131 FAX:713.781.9260 |