Direct Search or Derivative Free Methods

Direct search methods use only function evaluations. They search for the minimum of an objective function without calculating derivatives analytically or numerically. Direct methods are based upon heuristic rules which make no a priori assumptions about the objective function. They tend to have much poorer convergence rates than gradient methods when applied to smooth functions. Several authors claim that direct search methods are not as efficient and robust as the indirect or gradient search methods (Bard, 1974 Edgar and Himmelblau, 1988 Scales, 1986). However, in many instances direct search methods have proved to be robust and reliable particularly for systems that exhibit local minima or have complex nonlinear constraints (Wang and Luus, 1978). 

The Simplex algorithm and that of Powell s are examples of derivative-free methods (Edgar and Himmelblau, 1988 Seber and Wild, 1989, Powell, 1965). In this chapter only two algorithms will be presented (1) the LJ optimization procedure and (2) the simplex method. The well known golden section and Fibonacci methods for minimizing a function along a line will not be presented. Kowalik and Osborne (1968) and Press et al. (1992) among others discuss these methods in detail. 

Usually the space over which the objective function is minimized is not defined as the p-dimensional space of p continuously variable parameters. Instead it is a discrete configuration space of very high dimensionality. In general the number of elements in the configuration space is exceptionally large so that they cannot be fully explored with a reasonable computation time. 

For parameter estimation purposes, simulated annealing can be implemented by discretizing the parameter space. Alternatively, we can specify minimum and maximum values for each unknown parameter, and by using a random number uniformly distributed in the range [0,1], we can specify randomly the potential parameter values as 

Another interesting implementation of simulated annealing for continuous minimization (like a typical parameter estimation problem) utilizes a modification of the downhill simplex method. Press et al. (1992) provide a brief overview of simulated annealing techniques accompanied with listings of computer programs that cover all the above cases. 

---