next up previous

2.3 Nonderivative Methods     continued...

Coordinate Descent methods form the basis to nonderivative methods [22,45]. In the simplest variant, the search directions at each step are taken as the standard basis vectors. A sweep through these n search vectors produces a sequential modification of one function variable at a time. Through repeatedly sweeping the n-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, n mutually conjugate directions are generated after n 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 [22,45]. 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 n sweeps.