min_uncon_polytope
Minimizes a function of n variables using a direct search polytope algorithm.
Synopsis
#include <imsl.h>
float *imsl_f_min_uncon_polytope(void fcn(), int n, ..., 0)
The type double function is imsl_d_min_uncon_polytope.
Required Arguments
void fcn (int n, float x[],float *f) (Input)
User-supplied function to evaluate the function to be minimized.
Arguments
int n (Input)
Length of x.
float x[] (Input)
Array of length n at which point the function is evaluated.
float *f (Output)
The computed function value at the point x.
int n (Input)
Dimension of the problem.
Return Value
An array of length n containing the best estimate of the minimum found. To release this space, use imsl_free. If no solution was computed, then NULL is returned.
Synopsis with Optional Arguments
#include <imsl.h>
float *imsl_f_min_uncon_polytope(void fcn(), int n,
IMSL_XGUESS, float xguess[],
IMSL_TOLERANCE, float ftol,
IMSL_MAX_FCN, int *maxfcn,
IMSL_SIDE_LENGTH, float *s,
IMSL_FVALUE, float *fvalue,
IMSL_RETURN_USER, float x[],
IMSL_FCN_W_DATA, void fcn(),void *data,
0)
Optional Arguments
IMSL_XGUESS, float xguess[] (Input)
An array of length n which contains an initial guess to the minimum.
Default: xguess = 0.0
IMSL_TOLERANCE, float ftol (Input)
The error tolerance used is based on two convergence criteria.
First convergence criterion: The algorithm stops when a relative error in the function values is less than ftol, i.e. when (fcn(worst) ‑ fcn(best)) < ftol * (1 + fabs(fcn(best))) where fcn(worst) and fcn(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 routine terminates prematurely, try again with a smaller value for ftol.
Default: ftol = 1.e-5 in single precision and 1.e-10 in double precision.
IMSL_MAX_FCN, int *maxfcn (Input/Output)
On input, maximum allowed number of function evaluations. On output, actual number of function evaluations needed.
Default: maxfcn = 300
IMSL_SIDE_LENGTH, float *s (Input/Output)
On input, real scalar containing the length of each side of the initial simplex. If no reasonable information about s is known, s could be set to a number less than or equal to zero and imsl_f_min_uncon_polytope will generate the starting simplex from the initial guess with a random number generator. On output, the average distance from the final vertices to their centroid; see Remark 2.
Default: s = 0.0
IMSL_FVALUE, float *fvalue (Output)
Function value at the computed solution.
IMSL_RETURN_USER, float x[] (Output)
Array with n components containing the computed solution.
IMSL_FCN_W_DATA, void fcn (int n, float x[],float *f, void *data), void *data (Input)
User supplied function to evaluate the function to be minimized, which also accepts a pointer to data that is supplied by the user. data is a pointer to the data to be passed to the user-supplied function. See the Introduction, Passing Data to User-Supplied Functions at the beginning of this manual for more details.
Description
The routine imsl_f_min_uncon_polytope 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 the current best point. This procedure is repeated until one of the following stopping criteria is satisfied:
Criterion 1:
fworst ‑ fbest≤ ɛf (1. + |fbest|)
Criterion 2:
where fi = f (xi), fj = f (xj), ɛf is a given tolerance and
For a complete description, see Nelder and Mead (1965) or Gill et al. (1981).
Remarks
1. Since imsl_f_min_uncon_polytope 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 imsl_f_min_uncon_multivar that takes into account derivative information at each iteration. Hence, routine imsl_f_min_uncon_polytope should be used only 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 with a new point with a smaller function value. The iteration continues until all the points cluster sufficiently close to a minimum.
2. 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.
#include <imsl.h>
#include <stdio.h>
void fcn(int n, float x[], float *f);
#define N 2
int main() {
float xguess[N] = {-1.2, 1.0};
float *x, fvalue;
float ftol = 1.0e-7, s = 1.0;
x = imsl_f_min_uncon_polytope(fcn, N,
IMSL_XGUESS, xguess,
IMSL_TOLERANCE, ftol,
IMSL_FVALUE, &fvalue,
IMSL_SIDE_LENGTH, &s,
0);
printf("The best estimate for the minimum value of the\n");
printf("function is x = (%4.2f, %4.2f) with\n", x[0], x[1]);
printf("function value fvalue = %12.6e\n", fvalue);
}
void fcn(int n, float x[], float *f)
{
float t1, t2;
t1 = x[0]*x[0]-x[1];
t2 = 1.0-x[0];
*f = 100.0*t1*t1 + t2*t2;
}
The best estimate for the minimum value of the
function is x = (1.00, 1.00) with
function value fvalue = 2.126065e-007
Fatal Errors
|
IMSL_FCN_EVAL_EXCEEDED_MAXFCN |
Maximum number of function evaluations exceeded. |
|
IMSL_STOP_USER_FCN |
Request from user supplied function to stop algorithm. User flag = "#". |
