UMPOL
Minimizes a function of N variables using a direct search polytope algorithm.
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 – Vector of length N at which point the function is evaluated. (Input)
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 — Real vector of length N containing the best estimate of the minimum found. (Output)
Optional Arguments
N — Dimension of the problem. (Input)
Default: N = SIZE (X,1).
XGUESS — Real vector of length N which contains an initial guess to the minimum. (Input)
Default: XGUESS = 0.0.
S — On input, real scalar containing the length of each side of the initial simplex. (Input/Output)
If no reasonable information about S is known, S could be set to a number less than or equal to zero and UMPOL will generate the starting simplex from the initial guess with a random number generator. On output, the average distance from the vertices to the centroid that is taken to be the solution; see Comment 4.
Default: S = 0.0.
FTOL — First convergence criterion. (Input)
The algorithm stops when a relative error in the function values is less than FTOL, i.e. when (F(worst) ‑ F(best)) < FTOL * (1 + ABS(F(best))) where F(worst) and F(best) are the function values of the current worst and best points, respectively. Second convergence criterion. The algorithm stops when the standard deviation of the function values at the N + 1 current points is less than FTOL. If the subroutine terminates prematurely, try again with a smaller value for FTOL.
Default: FTOL = 1.e-7.
MAXFCN — On input, maximum allowed number of function evaluations. (Input/ Output)
On output, actual number of function evaluations needed.
Default: MAXFCN = 200.
FVALUE — Function value at the computed solution. (Output)
FORTRAN 90 Interface
Generic: CALL UMPOL (FCN, X [, …])
Specific: The specific interface names are S_UMPOL and D_UMPOL.
FORTRAN 77 Interface
Single: CALL UMPOL (FCN, N, XGUESS, S, FTOL, MAXFCN, X, FVALUE)
Double: The double precision name is DUMPOL.
Description
The routine UMPOL uses the polytope algorithm to find a minimum point of a function f(x) of n variables. The polytope method is based on function comparison; no smoothness is assumed. It starts with n + 1 points x1, x2, …, xn + 1. At each iteration, a new point is generated to replace the worst point xj, which has the largest function value among these n + 1 points. The new point is constructed by the following formula:
xk = c + α(c ‑ xj)
where
and α(α > 0) is the reflection coefficient.
When xk is a best point, that is f(xk) ≤ f(xi) for i = 1, …, n + 1, an expansion point is computed xe = c + β(xk ‑ c) where β(β > 1) is called the expansion coefficient. If the new point is a worst point, then the polytope would be contracted to get a better new point. If the contraction step is unsuccessful, the polytope is shrunk by moving the vertices halfway toward current best point. This procedure is repeated until one of the following stopping criteria is satisfied:
Criterion 1:
fbest ‑ fworst ≤ ɛf (1. + ∣fbest∣)
Criterion 2:
where fi = f (xi), fj = f (xj), and ɛf is a given tolerance. For a complete description, see Nelder and Mead (1965) or Gill et al. (1981).
Comments
1. Workspace may be explicitly provided, if desired, by use of U2POL/DU2POL. The reference is:
CALL U2POL (FCN, N, XGUESS, S, FTOL, MAXFCN, X, FVALUE, WK)
The additional argument is:
WK — Real work vector of length N**2 + 5 * N + 1.
2. Informational error
Type | Code | Description |
|---|
4 | 1 | Maximum number of function evaluations exceeded. |
3. Since UMPOL uses only function value information at each step to determine a new approximate minimum, it could be quite inefficient on smooth problems compared to other methods such as those implemented in routine UMINF that takes into account derivative information at each iteration. Hence, routine UMPOL should only be used as a last resort. Briefly, a set of N + 1 points in an N-dimensional space is called a simplex. The minimization process iterates by replacing the point with the largest function value by a new point with a smaller function value. The iteration continues until all the points cluster sufficiently close to a minimum.
4. The value returned in S is useful for assessing the flatness of the function near the computed minimum. The larger its value for a given value of FTOL, the flatter the function tends to be in the neighborhood of the returned point.
Example
The function
is minimized and the solution is printed.
USE UMPOL_INT
USE UMACH_INT
IMPLICIT NONE
! Variable declarations
INTEGER N
PARAMETER (N=2)
!
INTEGER K, NOUT
REAL FTOL, FVALUE, S, X(N), XGUESS(N)
EXTERNAL FCN
!
! Initializations
! XGUESS = ( -1.2, 1.0)
!
DATA XGUESS/-1.2, 1.0/
!
FTOL = 1.0E-10
S = 1.0
!
CALL UMPOL (FCN, X, xguess=xguess, s=s, ftol=ftol,&
fvalue=fvalue)
!
CALL UMACH (2, NOUT)
WRITE (NOUT,99999) (X(K),K=1,N), FVALUE
99999 FORMAT (' The best estimate for the minimum value of the', /, &
' function is X = (', 2(2X,F4.2), ')', /, ' with ', &
'function value FVALUE = ', E12.6)
!
END
! External function to be minimized
SUBROUTINE FCN (N, X, F)
INTEGER N
REAL X(N), F
!
F = 100.0*(X(1)*X(1)-X(2))**2 + (1.0-X(1))**2
RETURN
END
Output
The best estimate for the minimum value of the
function is X = ( 1.00 1.00)
with function value FVALUE = 0.502496E-10
