The Powell conjugate gradient algorithm

Since the generation of the conjugate directions in the Fletcher-Reeves algorithm requires the computation of $\nabla f(\mathbf{x})$ at each iteration, and this computation it is not always feasible, Powell ([15]) has developed a method to generate the conjugate directions using only a one-dimensional search at each iteration: if $\mathbf{x}^1$, $\mathbf{x}^2$ are two vectors generated by one-dimensional searches in the same direction $\mathbf{v}$, but from different points, then $\mathbf{x}^1-\mathbf{x}^2$ is mutually conjugate to $\mathbf{v}$.

Algorithm 5.35   Powell conjugate gradient algorithm

The Powell algorithm is equivalent to a one-dimensional search made in a sequential way along mutually conjugate directions. The only critic point of the Powell is the line $7$ of the algorithm 4.35: replacing th $n$-th direction $\mathbf{h}^n$ with the vector $\mathbf{x}^{n}-\mathbf{x}^{0}$ tends to produce at each iteration a set of directions that are more linearly dependent. The solution is to reinitialize every $n$ iterations the set of directions $\mathbf{h}$; these directions can be the columns of any orthogonal matrix, and there is an heuristic scheme due to Powell.

Figure 4.2: Minimization by Powell algorithm of a function $\sim x^4$: 20 steps.

The figure 4.2 shows 20 iterations of the Powell algorithm to find the minimum (located at $x=30$) of a mono-dimensional function $\sim x^4$. As it can be see, the algorithm finds the minimum at $x=31.7$ and it is not fooled by the presence of a local minimum at $x=10$. The figure 4.3 shows 24 iterations to find the minimum (located at $x=15$) of a more complicated function $\sim x^6$: again the algorithm finds the global minimum at $x=13.7$ in a presence of local minima.
In both cases a better precision on the location of the minimum could be obtained increasing the number of iterations.

Figure 4.3: Minimization by Powell algorithm of a function $\sim x^6$: 24 steps.