Conjugate Gradient (Fletcher-

Reeves) Method for Unconstrained

Optimization Problem

By: Dr. R. S. Bisht

Email: rsbisht@[Link],
rsb.mech08@[Link]
 By: Dr. R. [Link]

Conjugate Gradient (Fletcher-

Reeves) Method for Unconstrained
Optimization Problems
Step by Step 3 Simple Steps Rule for
Explanations each problem
Utilize Conjugate Step 1:Find the search direction 𝑆𝐼 as
Direction 𝑆𝑖 = −𝛻𝑓𝑖 +𝛽𝑖 𝑆𝑖−1
𝛻𝑓𝑖 2
Where 𝛽𝑖 = .
𝛻𝑓𝑖−1 2
Step2:Determine
𝑆𝑖𝑇 𝑆𝑖
The conjugate-gradient 𝜆𝑖 =
𝑆𝑖𝑇 𝐻𝑖 𝑆𝑖
method convergence in
And set X𝑖+1 = 𝑋𝑖 + 𝜆𝑖 𝑠𝑖
at most 𝑛 steps. Here. 𝑛
is the number of decision
Step3:Test the optimality for the new
variables
point 𝑋𝑖+1 .
Recall: In the previous lecture,

Steepest descent (Cauchy) method

In this method, we minimize the function with the help

of the descent direction (i.e., negative of the gradient
𝑆𝑖 = −𝛻𝑓𝑖 ).
The Steepest Descent method, take many steps

to reach the optimum solution, i.e.,

convergence is very slow.

❖ The convergence characteristics of the steepest
descent method can be improved greatly by modifying
it into a conjugate method.

❖ In Conjugate method, it considers a conjugate

direction involving the use of the gradient of the
function.

The direction 𝑆1 is conjugate to 𝑆2 over the

Hessian matrix 𝐴 is
𝑆1𝑇 𝐴𝑆2 = 0.
For any minimization method, the conjugate direction is
quadratically convergent.

Advantages of Conjugate direction

The above property will be very useful because it

ensures that the method will minimize a quadratic
function in n steps or less. Here, n is the number of the
decision variables.

Examples:

• 𝑓 𝑋 = 𝑥12 + 𝑥22 − 2𝑥1 𝑥2 𝑓 𝑋 = 𝑥12 − 𝑥32 + 𝑥1 𝑥3

−𝑥2 + 4 −2.5𝑥2 𝑥3 + 𝑥1 − 3𝑥3
Here, 𝑛 = 2 Here, 𝑛 = 3
 Development of the Conjugate
Gradient (Fletcher-Reeves) Method
Consider a quadratic function

1 𝑇
𝑓 𝑋 = 𝑆 𝐴𝑋 + 𝐵𝑇 𝑋 + 𝐶
2

Let 𝑋1 be the starting point for the

minimization and let the first search direction
be the Steepest descent direction.

𝛻𝑓 = 𝐴𝑋 + 𝐵
𝑆1 = −𝛻𝑓1 = −𝐴𝑋1 − 𝐵
 Thus, new point is 𝑋2 = 𝑋1 + 𝜆1 𝑆1

𝑋2 −𝑋1
Or 𝑆1 = 𝜆1

Where 𝜆1 is the minimizing step length in the

Direction of 𝑆1 , that

𝑆1𝑇 𝛻𝑓 = 0 𝑎𝑡 𝑋2

𝑖, 𝑒. , 𝑆1𝑇 (𝐴𝑋1 + 𝐵) = 0

𝑖, 𝑒. . 𝑆1𝑇 (𝐴[𝑋1 + 𝜆1 𝑆1 ]+𝐵) = 0

𝑆𝑖𝑇 𝑆𝑖
𝜆𝑖 = 𝑇
𝑆1𝑇 𝐴𝑋1 + 𝐵 𝑆1𝑇 𝛻𝑓1 𝛻𝑓1𝑇 𝛻𝑓1 𝑆𝑖 𝐻𝑖 𝑆𝑖
𝜆1 = − =− 𝑇 = 𝑇
𝑆1𝑇 𝐴𝑆1 𝑆1 𝐴𝑆1 𝑆1 𝐴𝑆1
Now, express the second search direction
As a linear combination of −𝛻𝑓2 and 𝑆1
𝛻𝑓2 − 𝛻𝑓1 = 𝐴𝑋2 + 𝐵 − (𝐴𝑋1 + 𝐵)

= 𝐴(𝑋2 − 𝑋1 )
𝑆2 = −𝛻𝑓2 + 𝛽2 𝑆1
(𝑋 − 𝑋 )𝑇 (𝛻𝑓 − 𝛻𝑓 )𝑇
2 1 2 1
𝑆𝑜 𝑆1𝑇 𝐴 = 𝐴=
𝜆1 𝜆1
Where 𝛽2 is to be chosen so as to
Make 𝑆1 and 𝑆2 are conjugate. Thus
(𝛻𝑓2 −𝛻𝑓1 )𝑇
(𝛻𝑓2 + 𝛽2 𝑆1 )= 0
𝛾1
𝑖, 𝑒. . 𝑆1𝑇 𝐴𝑆2 = 0
−𝛻𝑓2𝑇 𝛻𝑓2 + 𝛻𝑓2𝑇 𝛻𝑓2 + 𝛽2 𝛻𝑓2𝑇 𝑆1 −
Substitute the value of𝑆2 , we get 𝛽2 𝛻𝑓2𝑇 𝑆1 = 0
Since, 𝛻𝑓1𝑇 𝛻𝑓2 = −𝑆1𝑇 𝛻𝑓2 = 0,
𝑖. 𝑒 𝑆1𝑇 𝐴(−𝛻𝑓2 + 𝛽2 𝑆1 )= 0
Since ,𝐴 𝑖𝑠 𝑠𝑦𝑚𝑚𝑒𝑡𝑟𝑖𝑐 𝑚𝑎𝑡𝑟𝑖𝑥 𝑇 𝑇 2
so 𝛽 = − 𝛻𝑓2 𝛻𝑓2 = 𝛻𝑓2 𝛻𝑓2 = |𝛻𝑓2 |
2
𝛻𝑓1𝑇 𝛻𝑓1 𝛻𝑓1𝑇 𝛻𝑓1 |𝛻𝑓1 |2
 Similarly, consider the third search direction as a
linear combination of 𝑆1 , 𝑆2 and − 𝛻𝑓3 as

𝑆3 = −𝛻𝑓3 + 𝛽3 𝑆2 + 𝛿3 𝑆1
Where the values of 𝛽3 𝛿3 can be found by making
𝑆3 conjugate to 𝑆2 and 𝑆1 respectively.

i.e, 𝑆1𝑇 𝐴𝑆3 = 𝑎𝑛𝑑 𝑆1𝑇 𝐴𝑆2 = 0

From 𝑆1𝑇 𝐴𝑆3 = 0, 𝑤𝑒 𝑐𝑎𝑛 𝑏𝑒 𝑓𝑜𝑢𝑛𝑑 𝑡ℎ𝑎𝑡 𝛿3 = 0 𝛿3 = 0

From 𝑆2𝑇 𝐴𝑆3 = 0, 𝑤𝑒 𝑐𝑎𝑛 𝑏𝑒 𝑓𝑜𝑢𝑛𝑑 𝑡ℎ𝑎𝑡 |𝛻𝑓3 |2

𝛽3 =
|𝛻𝑓2 |2
In general, Search direction in conjugate-gradient
(Fletcher-Reeves) method is

𝑆𝑖 = −𝛻𝑓𝑖 + 𝛽𝑖 𝑆𝑖−1

|𝛻𝑓𝑖 |2
where 𝛽𝑖 =
|𝛻𝑓𝑖−1 |2
 Step 1:find the search direction 𝑆𝑖 as
Algorithm: Conjugate Gradient
(Fletcher - Reeves) Method |𝛻𝑓𝑖 |2
𝑆𝑖+1 = −𝛻𝑓𝑖 + 𝛽𝑖 𝑆𝑖−1 where 𝛽𝑖 =
|𝛻𝑓𝑖−1 |2

Minimize 𝑓(𝑥)
Calculate 𝛻𝑓 and Hessian matrix 𝐴 from the given Step 2: Determine the optimal step length
𝑓(𝑥)
𝛻𝑓1𝑇 𝛻𝑓𝑖
𝜆𝑖 = 𝑇
𝑆1 𝐴𝑆𝑖
In the direction of 𝑆𝑖 and set
Set 𝑆0 = 0
𝑋𝑖+1 = 𝑋𝑖 + 𝜆𝑖 𝑆𝑖
Start with arbitrary 𝑋1 and iteration number i = 1. Step 3: Test the optimality for the new
point 𝑋𝑖+1 .
Example: Minimize
𝑓 𝑥1 , 𝑥2 = 𝑥1 − 𝑥2 + 2𝑥12 + 2𝑥1 𝑥2 + 𝑥22 n

Starting from the point 𝑋1 = 0, 0 .

Solution:

The gradient of 𝑓 𝑖𝑠

𝜕𝑓 Hessian Matrix is
𝜕𝑥1
𝛻𝑓 =
𝜕𝑓 𝜕2𝑓 𝜕2𝑓
𝜕𝑥2 𝜕𝑥12 𝜕𝑥1 𝜕𝑥2
𝐴= 𝜕2𝑓 𝜕2𝑓
1 + 4𝑥1 + 2𝑥2 𝜕𝑥2 𝜕𝑥1 𝜕𝑥22
=
−1 + 2𝑥1 + 2𝑥2
4 2
=
2 2
Iteration 1: At 𝑋1 = 0,0

1 Iteration 2: AT 𝑋2 :
Step 1: 𝛻𝑓1 = |𝛻𝑓2 |2
−1 −1 2
1 Step 1: 𝛻𝑓2 = 𝑎𝑛𝑑 = 𝛽2 = |𝛻𝑓 |2 = 2 = 1
𝑆1 = −𝛻𝑓1 = −1 1
−1
Step 2: Compute 𝜆1 at 𝑋1 Thus,𝑆2 = −𝛻𝑓2 + 𝛽2 𝑆2
𝛻𝑓1𝑇 𝛻𝑓1 2
𝜆1 = 𝑇 = =1 1 −1 0
𝑆1 𝐴𝑆1 2 = +1 =
1 1 2
𝛻𝑓1𝑇 𝛻𝑓𝑖 1+1 2 1
Hence ,the new point is Step 2: 𝜆2 = = =8=4
𝑆1𝑇 𝐴𝑆𝑖 [0 2] 4
4

𝑋2 = 𝑋1 + 𝜆1 𝑆1 Thus, the new point is

0 −1 −1 𝑋3 = 𝑋2 + 𝜆2 𝑆2
= +1 =
0 1 1 −1 1 −1 −1
= +4 =
Step 3:Check the optimum. 1 1 1.5
0
Step 3: Check the optimum.𝛻𝑓3 =
−1 0 0
𝛻𝑓2 = ≠
−1 0 Thus, 𝑋3 is optimum point.
So, 𝑋2 is not optimum so move next Iteration
 Note: If we want to calculate the next iteration, then
we also get the same results as

Iteration 3: At 𝑋3

0
Step 1:𝛻𝑓3 = and
0

|𝛻𝑓3 |2 0
𝛽2 = = = 0.
|𝛻𝑓2 |2 2

Thus, 𝑆3 = −𝛻𝑓3 + 𝛽3 𝑆2

0 0 0
=− +0 =
0 2 0
This shows that there is no search direction to
reduce 𝑓 further, and hence 𝑋3 is optimum.
Gradient Conjugate Gradient (Fletcher-
Reeves) Method
 Sensitivity to Initial Guess: The convergence speed of the method can be
highly dependent on the choice of the initial point. A poor starting point may
lead to slower convergence or even divergence.
 Non-convex Problems: The method may struggle with non-convex functions,
as it can get stuck in local minima instead of finding the global minimum.
 Slow Convergence for Ill-conditioned Problems: If the problem is ill-
conditioned (i.e., the ratio of the largest to the smallest eigenvalue of the
Hessian matrix is large), the convergence of the method can be slow.
 Memory Limitation: Although it uses less memory than other methods like
Newton's method, for extremely large problems, even the storage of gradient
information in multiple iterations can be a limitation.
 PRACTICE PROBLEMS

1. Minimize the following 𝑓 𝑋 using conjugate gradient method.

1. 𝑓 𝑋 = 𝑥12 − 𝑥1 𝑥3 + 3𝑥22 2. 𝑓 𝑋 = 5𝑥12 + 2𝑥22 3. 𝑓 𝑋

𝑥0 = (1,2)𝑇 𝐴𝑛𝑠: ? ? −2𝑥1 𝑥2 − 4𝑥1 − 4𝑥2 + 4, = 𝑥12 − 0.5𝑥1 𝑥2 + 𝑥22 .
𝑋0 = (0,0)𝑇 Ans: (2/3,4/3) 𝑋0 = (0,0)𝑇 𝐴𝑛𝑠: ? ?

3 1
4. 𝑓 𝑋 = 2𝑥12 𝑥22
+ + 2𝑥1 𝑥2 5. 𝑓 𝑋 = 2 𝑥12 + 2 𝑥22 − 𝑥1 𝑥2
+𝑥1 − 𝑥2 , 𝑋0 = (0,0)𝑇 −2𝑥1 ,
Ans: (-13, 2) 𝑋0 = (−2,4)𝑇 Ans: (1,1)

2. Find the minimum of 𝑓 𝑋 = 9𝑥12 + 4𝑥1 𝑥2 + 4𝑥22 − 18𝑥1 − 4𝑥2 + 9 by method of conjugate
directions. Do only two iterations after starting from the point (0, 0) and taking the first step in
the direction of steepest descent. Ans: 0 at (1, 0)
Assignment for submission
Q1. Minimize the following 𝑓(𝑋) using the conjugate gradient
(Fletcher-Reeves) method. Compare the results with the Newton
and Steepest Descent (Cauchy) methods. Use up to four iterations
for each case.

𝑓 𝑋 = 𝑥12 − 𝑥1 𝑥2 + 3𝑥22

Initial condition: 𝑋1 = (1, 2)𝑇

Q2. Minimize the following 𝑓(𝑋) using the conjugate gradient
(Fletcher-Reeves) method. Compare the results with the Newton
and Steepest Descent (Cauchy) methods. Use up to four iterations
for each case.

𝑓 𝑋 = 5𝑥12 + 2𝑥22
−2𝑥1 𝑥2 − 4𝑥1 − 4𝑥2 + 4,

Initial condition: 𝑋1 = (0,0)𝑇

Q3. Minimize the following 𝑓 𝑋 using conjugate gradient (Fletcher-
Reeves) method. Compare the results with Newtons and
Steepest Descent (Cauchy) Method. Use minimum three
iterations for each cases.

𝑓 𝑋 = 𝑥12 − 0.5𝑥1 𝑥2 + 𝑥22 .

Initial condition: 𝑋0 = (0, 0)𝑇

Q4. Minimize the following 𝑓(𝑋) using the conjugate gradient
(Fletcher-Reeves) method. Compare the results with the Newton
and Steepest Descent (Cauchy) methods. Use up to four iterations
for each case.

3 1
𝑓 𝑋 = 2 𝑥12 + 2 𝑥22 − 𝑥1 𝑥2 −2𝑥1 ,
Initial condition: 𝑋0 = (−2,4)𝑇
Q5. Minimize the following 𝑓(𝑋) using the conjugate gradient
(Fletcher-Reeves) method. Compare the results with the Newton
and Steepest Descent (Cauchy) methods. Use up to four iterations
for each case.

𝑓 𝑋 = 2𝑥12 + 𝑥22 + 2𝑥1 𝑥2 + 𝑥1 − 𝑥2 ,

Initial condition: 𝑋0 = (0,0)𝑇

Thankyou for
your attention.