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

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

Visual Numerics, Inc. Visual Numerics - Developers of IMSL and PV-WAVE http://www.vni.com/ PHONE: 713.784.3131 FAX:713.781.9260