2.3 Nonderivative Methods



next up previous
Next: 2.4 Gradient Methods Up: 2 Methods for Unconstrained Previous: 2.2.4 Convergence Characterization

2.3 Nonderivative Methods

 

Minimization methods that incorporate only function values generally involve some systematic method to search the conformational space. Although they are generally easy to implement, their realized convergence properties are rather poor. They may work well in special cases when the function is quite random in character or the variables are essentially uncorrelated. In general, the computational cost, dominated by the number of function evaluations, can be excessively high for functions of many variables and can far outweigh the benefit of avoiding derivative calculations. The techniques briefly sketched below are thus more interesting from a historical perspective.

Coordinate Descent methods form the basis to nonderivative methods [45][22]. In the simplest variant, the search directions at each step are taken as the standard basis vectors. A sweep through these search vectors produces a sequential modification of one function variable at a time. Through repeatedly sweeping the -dimensional space, a local minimum might ultimately be found. Since this strategy is inefficient and not reliable, Powell's variant has been developed [51]. Rather than specifying the search vectors a priori, the standard basis directions are modified as the algorithm progresses. The modification ensures that, when the procedure is applied to a convex quadratic function, mutually conjugate directions are generated after sweeps. A set of mutually conjugate directions with respect to the (positive-definite) Hessian of such a convex quadratic is defined by for all . This set possesses the important property that a successive search along each of these directions suffices to find the minimum solution [45][22]. Powell's method thus guarantees that in exact arithmetic (i.e., in absence of round-off error), the minimum of a convex quadratic function will be found after sweeps.

If obtaining the analytic derivatives is out of the question, viable alternatives remain. The gradient can be approximated by finite-differences of function values, such as

 

for suitably chosen intervals [30]. Alternatively, automatic differentiation, essentially a new algebraic construct [53][35][19], may be used. In any case, these calculated derivatives may then be used in a gradient or quasi-Newton method. Such alternatives will generally provide significant improvement in computational cost and reliability, as will be discussed in the following sections.



next up previous
Next: 2.4 Gradient Methods Up: 2 Methods for Unconstrained Previous: 2.2.4 Convergence Characterization



verena@csep1.phy.ornl.gov