Function Minimization Without Evaluating Derivatives--a Review

The problem of minimizing a function/(x) of n variables x = (xu x2, xn) from a given approximation to the minimum XQ, has received considerable attention in recent years. In particular two separate problems can be distinguished—functions for which both the function / and the first derivatives or gradient //t>x,can be evaluated at any given point x, and functions for which only/can be evaluated. Although satisfactory methods have been given by Fletcher and Powell (1963), and by Fletcher and Reeves (1964) for solving the first of these problems, the situation with regard to the latter problem is less clear. Historically it was found that the simplest concepts, those of tabulation, random search, or that of improving each variable in turn, were hopelessly inefficient and often unreliable. Improved methods were soon devised such as the Simplex method of Himsworth, Spendley and Hext (1962), the "pattern search" method of Hooke and Jeeves (1959), and a method due to Rosenbrock (1960). Both the latter methods have been widely used, that of Rosenbrock being probably the most efficient. However, all these methods rely on an ad hoc rather than a theoretical approach to the problem. Developments of gradient methods of minimization meanwhile were showing the value of iterative procedures based on properties of a quadratic function. In particular the most efficient methods involved successive linear minimizations along so-called "conjugate directions" generated as the minimization proceeded. An explanation of these terms is given in Fletcher and Reeves (1964).