Minimizes a function of n variables subject to bounds on the variables using a direct search complex algorithm.

#include <imsl.h>

float *imsl_f_min_con_polytope (void fcn(), int n, float xlb[], float xub[], …, 0)

The typedouble function is imsl_d_min_con_polytope.

A pointer to the solution x containing the best estimate for the minimum. To release this space, use imsl_free. If no solution can be computed, then NULL is returned.

Each iteration begins by determining the best and two worst points in the present complex, and then constructing a new “reflection” point xr by the formula

where

is the centroid of the 2n - 1 best points and α (α > 0) is the reflection coefficient. (See optional argument IMSL_REFLCOEF). Depending on how the new reflection point xr compares with the existing complex points, the iteration proceeds as follows:

If xr is neither better than the best point nor worse than the second worst point, then xr replaces the worst point xj and, if neither of the stopping criteria (see below) is satisfied, a new iteration begins.

If xr is a best point, that is, if f(xr) ≤ f(xi) for i = 1, …, 2n, an expansion point xe is computed to see if an even better point can be obtained by moving further in the reflection direction:

where β (β > 1) is called the expansion coefficient (see optional argument IMSL_EXPNCOEF), and worst point xj is replaced by the better of xe and xr and, if neither of the stopping criteria is satisfied, a new iteration begins.

If xr and xj are the two worst points, then the complex is contracted to try to get a better new contraction point xc:

Whenever the new point generated is beyond the bound, it will be projected onto the bound. If, at the end of an iteration, one of the following stopping criteria is satisfied, then the process ends with the best point returned as the optimum.

Criterion 1:

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).

Since imsl_f_min_con_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. Hence function imsl_f_min_con_polytope should be used only as a last resort. Briefly, a set of 2 * n points in ann -dimensional space is called a complex. 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.

The problem

is solved with an initial guess (1.2, 1.0), and the solution is printed.

This example is intended to illustrate the use of optional arguments available for imsl_f_min_con_polytope, and how their use can affect the number of function calls needed to complete the optimization process. The same problem as in Example 1 is approached in five ways, including the use of a function penalty in an attempt to constrain the solution space. In each case, the number of function evaluations required is output.

Solution 1 uses xlb and xub to impose bounds, as in Example 1. Solution 2 through 5 use a function penalty to impose constraints, and to varying degrees make use of optional arguments IMSL_XCPLX, IMSL_REFLCOEF, IMSL_EXPNCOEF, and IMSL_CNTRCOEF.

Note that the actual number of function calls required to complete the minimization process may vary, depending on the computing platform and precision used.