UVMGS
Finds the minimum point of a nonsmooth function of a single variable.
Required Arguments
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.
A — On input, A is the lower endpoint of the interval in which the minimum of F is to be located. On output, A is the lower endpoint of the interval in which the minimum of F is located. (Input/Output)
B — On input, B is the upper endpoint of the interval in which the maximum of F is to be located. On output, B is the upper endpoint of the interval in which the minimum of F is located. (Input/Output)
XMIN — The approximate minimum point of the function F on the original interval (A, B). (Output)
Optional Arguments
TOL — The allowable length of the final subinterval containing the minimum point. (Input)
Default: TOL = 1.e-4.
FORTRAN 90 Interface
Generic: CALL UVMGS (F, A, B, XMIN [, …])
Specific: The specific interface names are S_UVMGS and D_UVMGS.
FORTRAN 77 Interface
Single: CALL UVMGS (F, A, B, TOL, XMIN)
Double: The double precision name is DUVMGS.
Description
The routine UVMGS uses the golden section search technique to compute to the desired accuracy the independent variable value that minimizes a unimodal function of one independent variable, where a known finite interval contains the minimum.
Let 
= TOL. The number of iterations required to compute the minimizing value to accuracy is the greatest integer less than or equal to
where a and b define the interval and
The first two test points are v1 and v2 that are defined as
v1 = a + c(b ‑ a), and v2 = b ‑ c(b ‑ a)
If f(v1) < f(v2), then the minimizing value is in the interval (a, v2). In this case, b←v2, v2 ←v1, and v1←a + c(b‑a). If f(v1) ≥ f(v2), the minimizing value is in (v1, b). In this case, a←v1, v1←v2, and v2←b ‑ c(b ‑ a).
The algorithm continues in an analogous manner where only one new test point is computed at each step. This process continues until the desired accuracy is achieved. XMIN is set to the point producing the minimum value for the current iteration.
Mathematically, the algorithm always produces the minimizing value to the desired accuracy; however, numerical problems may be encountered. If f is too flat in part of the region of interest, the function may appear to be constant to the computer in that region. Error code 2 indicates that this problem has occurred. The user may rectify the problem by relaxing the requirement on , modifying (scaling, etc.) the form of f or executing the program in a higher precision.
Comments
1. Informational errors
|
Type |
Code |
Description |
|
3 |
1 |
TOL is too small to be satisfied. |
|
4 |
2 |
Due to rounding errors F does not appear to be unimodal. |
2. On exit from UVMGS without any error messages, the following conditions hold:
(B-A) ≤ TOL.
A ≤ XMIN and XMIN ≤ B
F(XMIN) ≤ F(A) and F(XMIN) ≤ F(B)
3. On exit from UVMGS with error code 2, the following conditions hold:
A ≤ XMIN and XMIN ≤ B
F(XMIN) ≥ F(A) and F(XMIN) ≥ F(B) (only one equality can hold).
Further analysis of the function F is necessary in order to determine whether it is not unimodal in the mathematical sense or whether it appears to be not unimodal to the routine due to rounding errors in which case the A, B, and XMIN returned may be acceptable.
Example
A minimum point of 3x2 ‑ 2x + 4 is found.
USE UVMGS_INT
USE UMACH_INT
IMPLICIT NONE
! Specification of variables
INTEGER NOUT
REAL A, B, FCN, FMIN, TOL, XMIN
EXTERNAL FCN
! Initialize variables
A = 0.0E0
B = 5.0E0
TOL = 1.0E-3
! Minimize FCN
CALL UVMGS (FCN, A, B, XMIN, TOL=TOL)
FMIN = FCN(XMIN)
! Print results
CALL UMACH (2, NOUT)
WRITE (NOUT,99999) XMIN, FMIN, A, B
99999 FORMAT (' The minimum is at ', F5.3, //, ' The ', &
'function value is ', F5.3, //, ' The final ', &
'interval is (', F6.4, ',', F6.4, ')', /)
!
END
!
! REAL FUNCTION: F = 3*X**2 - 2*X + 4
REAL FUNCTION FCN (X)
REAL X
!
FCN = 3.0E0*X*X - 2.0E0*X + 4.0E0
!
RETURN
END
Output
The minimum is at 0.333
The function value is 3.667
The final interval is (0.3331,0.3340)
