## Fletcher-Reeves-Polak-Ribiere

Given a function*:*

**f***R*→

^{n}*R*the Fletcher-Reeves-Polak-Ribiere method belongs to a group of methods called conjugate gradient methods which attempt to locate a local minimum of

*f*.

Given a quadratic function

*f (*a set of vectors {

**x**) =**x**A^{T}**x**+**b**+ c^{T}x*∈*

**y**_{i}*R*:

^{n}*i = 1,...,k*} are conjugate directions for

*f*if <

*|*

**y**_{i}*A*|

*> =*

**y**_{j}*= 0 for*

**y**A^{T}_{i}**y**_{j}*i ≠ j*.

The following lemma is due to Fletcher and Reeves: Given a quadratic function

*f (*and a point

**x**) =**x**A^{T}**x**+**b**+ c^{T}x*,*

**x**_{1}*= -*

**v**_{1}*= -*

**g**_{1}**grad**

*f (*and for

**x**)_{1}*k*≥ 1, define

*= -*

**v**_{k+1}*+ (*

**g**_{k+1}*/*

**g**^{T}_{k+1}g_{k+1}*)*

**g**^{T}_{k}g_{k}*, where*

**v**_{k}*=*

**g**_{j}*f*

**grad***(*and

**x**)_{j}*=*

**x**_{k+1}*- 2 (*

**x**_{k}*/ <*

**g**^{T}_{k}v_{k}*| A |*

**v**_{k}*> )*

**v**_{k}*, then {*

**v**_{k}*} forms a set of conjugate directions for*

**v**_{k}*f*.

In general the conjugate gradient methods proceed as follows:

**Initialization:**Choose a point,, which approximates the location of a local minimum. Set**x**_{0}*k*= 0 and=**v**_{-1}**0**.**Check if the stopping criterion is satisfied:**The conventional stopping rule is: Stop if ||f**grad***(*|| < ε for either the**x**)_{k}*max*-norm or the*l*-norm. If the stopping criterion is satisfied, then halt. Otherwise, continue._{2}**Calculate New Search Direction:**Set*α*(see below). Define_{k}=**v**_{k}+ α**grad**f (**x**)_{k}_{k}.**v**_{k-1}**Determine the Displacement Vector**Given*Δ x*:_{k}and**x**_{k}, let**v**_{k}*λ*be the value of_{k}*λ*which minimizes*f (*. Then set**x**- λ_{k}**v**)_{k}*Δ*=**x**_{k}*λ*_{k}.**v**_{k}**Update the estimate for the location of a local minimum:**Set=**x**_{k+1}+**x**_{k}*Δ*, then increment**x**_{k}*k*and go to step 2.

*α*vary. For the Fletcher-Reeves-Polak-Ribiere method the estimate for

_{k}*α*is

_{k+1}*α*=

_{k}*) /*

**g**(^{T}_{k}**g**-_{k}**g**_{k-1}*, where*

**g**^{T}_{k-1}g_{k-1}*=*

**g**_{j}*f*

**grad***(*and

**x**)_{j}*k ≠ 0 mod n*

*α*= 0 if

_{k}*k = 0 mod n*

### Function List

- int Fletcher_Reeves_Polak_Ribiere( double (*f)(double *), void (*df)(double*, double*), int (*Stopping_Rule)(double*, double*, int, int), double *a, double *dfa, double line_search_cutoff, double line_search_cutoff_scale_factor, double line_search_tolerance, int n )

This routine uses the Fletcher-Reeves-Polak-Ribiere method to approximately locate a local minimum of the user-supplied function*f(*. The procedure starts at**x**)=**x***a*. The gradient is calculated using the user-supplied function*df(*where**x**,*dfa*)*dfa*is the*n*-dimensional array whose*i*component^{th}*dfa[i]*is ∂f(**x**)/∂x_{i}. The parameters*line_search_cutoff*,*line_search_cutoff_scale_factor*and*line_search_tolerance*are used for minimizing the function,*f (*down the line in a direction opposite to that given by the gradient. See Minimize_Down_the_Line for a discription of these parameters. The arguments to the user-supplied**x**),*stopping_rule*are: the new estimate of the location of the local minimum, the gradient of the function evaluated at the new estimate**x***f(*, the total number of iterations performed, and**x**)*n*the dimension of. The user-supplied**x***stopping_rule*should return a non-zero, either positive or negative, integer to halt the procedure and return zero to continue iterating, the return value -1 is the only intrinsic return value used by the Fletcher-Reese-Polak-Ribiere routine. Upon exiting the function returns either the return of the user-supplied*stopping-rule*or a -1 indicating that there was not enough dynamic heap memory. The value*a*is set to the current estimate.

*C* Source Code

- The file, fletcher_reeves_polak_ribiere.c, contains the version of Fletcher_Reeves_Polak_Ribiere( ) written in
*C*.