Process Optimization

(CHE 544)

PART II – Lecture 2
One Dimensional Search Methods:
Golden Section Method
2022/2023 Omega Semester 1
 Gold Section Method: Overview
• It is applicable for finding optimal solution to one dimensional nonlinear
programming problems.
• The golden section method is also an elimination technique in which the
given interval of uncertainty is reduced iteratively.
• It is totally dependent on the golden ratio, 𝛾, which is approximately
1.618.
• The golden ratio is related to the Fibonacci number.

2022/2023 Omega Semester 2

• To apply the golden section method, the function to be optimized
must be unimodal within the given interval of uncertainty.
• If the function is multimodal, (i.e. if it has several local maxima and
local minima), the given interval of uncertainty has to be broken into
smaller intervals which are unimodal.
• The golden section method is similar to Fibonacci method; however,
unlike the Fibonacci method, the number of experiments in the
golden section method are not predefined.
• Experimenting is stopped based on the tolerance limit.

2022/2023 Omega Semester 3

 Derivation of the golden ratio
Recall: 𝐹𝑛 = 𝐹𝑛−1 + 𝐹𝑛−2 (1)
𝐹𝑛 𝐹𝑛−2
=1+ (2)
𝐹𝑛−1 𝐹𝑛−1
𝐹𝑛 𝐹𝑛−1 𝐹𝑛−𝑗
Let 𝛾 = lim = lim = lim
𝑛→∞ 𝐹𝑛−1 𝐹
𝑛→∞ 𝑛−2 𝑛→∞ 𝐹𝑛−(𝑗+1)
𝐹𝑛 𝐹𝑛−2
From (2) 𝛾 = lim ⇒ 1 + lim
𝑛→∞ 𝐹𝑛−1 𝑛→∞ 𝐹𝑛−1

𝛾 =1+1 𝛾
⇒𝛾−1−1 𝛾 =0
⇒ 𝛾2 − 𝛾 − 1 = 0
1± 5
𝛾=
2
2022/2023 Omega Semester 4
 1+ 5
• The positive ratio, ≈ 1.618 is the golden ratio
2
1− 5
• The negative ratio, ≈ −0.618 is the conjugate root or conjugate
2
golden ratio.

2022/2023 Omega Semester 5

 Iterative Process
Step 1: Given initial length of uncertainty, 𝐿𝑜, = [𝑎, 𝑏]
Step 2: Evaluate 𝐿∗2
∗
𝐹𝑛−2 𝐹𝑛−2 𝐹𝑛−1
𝐿2 = lim 𝐿𝑜 = lim . 𝐿𝑜
𝑛→∞ 𝐹𝑛 𝑛→∞ 𝐹𝑛−1 𝐹𝑛

1
𝐿∗2 = 2 𝐿𝑜
𝛾

Step 3: Generate the first two experiments, 𝑥1 & 𝑥2

𝑥1 = 𝑎 + 𝐿∗2
𝑥2 = 𝑏 − 𝐿∗2

2022/2023 Omega Semester 6

• Step 4: Evaluate 𝑓 𝑥1 & 𝑓 𝑥2 and discard the section of the initial
length of uncertainty not in favour of the optimization problem.
• Note: This depends on the topography of the graph and the nature
of the optimization problem (whether it is a minimization problem or
a maximization problem).
• Step 5: The new certainty interval 𝐿2 is either [𝑎, 𝑥2 ] or [𝑥1 , 𝑏]

2022/2023 Omega Semester 7

Step 6: Evaluate 𝐿∗3
𝐹𝑛−3 𝐹𝑛−3 𝐹𝑛−2 𝐹𝑛−1
𝐿∗3 = lim 𝐿𝑜 = lim . . 𝐿𝑜
𝑛→∞ 𝐹𝑛 𝑛→∞ 𝐹𝑛−2 𝐹𝑛−1 𝐹𝑛
1
𝐿∗3 = 3 𝐿𝑜
𝛾
• Step 7: Generate the 𝑥3
• If 𝐿2 were to be [𝑎, 𝑥2 ], you will discover that 𝑥1 will already be 𝐿∗3 from 𝑥2
end of the interval. Then 𝑥3 will be 𝑎 + 𝐿∗3
• If 𝐿2 were to be [𝑥1 , 𝑏], you will discover that 𝑥2 will already be 𝐿∗3 from 𝑥1
end of the interval. Then 𝑥3 will be 𝑏 − 𝐿∗3
• Step 8: Evaluate 𝑓 𝑥3 and discard the section of the uncertainty interval
not in favour of the optimization problem.
2022/2023 Omega Semester 8
 𝐹𝑛−2 1
Step 9: 𝐿3 = 𝐿2 − 𝐿∗3 = lim 𝐿𝑜 = 𝐿
𝑛→∞ 𝑛𝐹 𝛾2 𝑜

Step 10: Generate the next experiment until the stopping tolerance is met.

To generate 𝒋𝒕𝒉 experiments: 1

𝐿𝑗∗ = 𝑗 𝐿𝑜
𝛾
1
𝐿𝑗 = 𝑗−1 𝐿𝑜
𝛾

• Conclusion: When the final length of uncertainty, 𝐿𝑗 is less than a small and
positive value, 𝜖 (i. e. 𝐿𝑗 < 𝜖), then the iteration is stopped and 𝐿𝑗 is declared
the optimum length of uncertainty.
2022/2023 Omega Semester 9
• Worked Example: Minimize 𝑓 𝑥 = 4𝑥 3 + 𝑥 2 − 7𝑥 + 14 with the
interval 0,1 using the golden section method. Take stopping
tolerance 𝜖 = 0.15
Solution
Given: 𝐿𝑜 = 0,1 , 𝜖 = 0.15
• Generate 𝒙𝟏 & 𝒙𝟐
1
𝐿∗2 = 2 𝐿𝑜 = 0.3819
𝛾
𝑥1 = 0.3819
𝑥2 = 1 − 𝐿∗2 = 0.6181

2022/2023 Omega Semester 10

𝑓 𝑥1 =11.6953, 𝑓 𝑥2 = 10.9999
• Since 𝑓 𝑥2 < 𝑓 𝑥1 discard 𝑎, 𝑥1

1
𝐿2 = 𝐿𝑜
𝛾
1
= × 1 = 0.6180 ≮ 𝜖, 𝑡ℎ𝑒𝑛 𝑚𝑜𝑣𝑒 𝑡𝑜 𝑡ℎ𝑒 𝑒𝑥𝑝𝑒𝑟𝑖𝑚𝑒𝑛𝑡
1.618

2022/2023 Omega Semester 11

• Generate: 𝒙𝟑
1
𝐿∗3 = 3 𝐿𝑜 = 0.2361
𝛾
• You will discover that 𝑥2 and 𝑥1 are 𝐿∗3 apart
𝑥3 = 1 − 𝐿∗3 = 0.7639

𝑓 𝑥3 = 11.0193
• Since, 𝑓 𝑥2 < 𝑓 𝑥3 discard 𝑥3 , 𝑏

2022/2023 Omega Semester 12

 1
𝐿3 = 2 𝐿𝑜
𝛾
1
= 2
× 1 = 0.3819 ≮ 𝜖, 𝑡ℎ𝑒𝑛 𝑚𝑜𝑣𝑒 𝑡𝑜 𝑡ℎ𝑒 𝑒𝑥𝑝𝑒𝑟𝑖𝑚𝑒𝑛𝑡
1.618
• Generate 𝒙𝟒
1
𝐿∗4
= 4 𝐿𝑜 = 0.1459
𝛾
• You will discover that 𝑥2 and 𝑥3 are 𝐿∗4 apart
𝑥4 = 𝑥1 + 𝐿∗4 = 0.5278
𝑓 𝑥4 = 11.1721
• Since, 𝑓 𝑥3 < 𝑓 𝑥2 discard 𝑥1 , 𝑥4
2022/2023 Omega Semester 13
 1
𝐿4 = 3 𝐿𝑜
𝛾
1
= 3
× 1 = 0.236 ≮ 𝜖, 𝑡ℎ𝑒𝑛 𝑚𝑜𝑣𝑒 𝑡𝑜 𝑡ℎ𝑒 𝑒𝑥𝑝𝑒𝑟𝑖𝑚𝑒𝑛𝑡
1.618

• Generate 𝒙𝟓 ,
1
𝐿∗5 = 5 𝐿𝑜 = 0.0902
𝛾
2022/2023 Omega Semester 14
• You will discover that 𝑥2 and 𝑥4 are 𝐿∗5 apart
𝑥5 = 𝑥3 − 𝐿∗5
= 0.7639 − 0.0902 = 0.6737
𝑓 𝑥5 = 10.9611
• Since, 𝑓 𝑥5 < 𝑓 𝑥2 discard 𝑥4 , 𝑥2

2022/2023 Omega Semester 15

 1
𝐿5 = 4 𝐿𝑜 = 0.1458 < 0.15
𝛾
• Therefore, the final length of uncertainty is 𝑥2 , 𝑥3
𝐿5 𝐿5
2 2

|
𝑥2 𝑥∗
𝑥3
0.6181 0.691 0.7639

𝐿5

• The optimal solution will lie between 0.6181, 0.7639

𝐿5
• The minimizer is therefore 𝑥 ∗ = 𝑥3 − = 0.691
2
• The minimum of the function is therefore 𝑓 𝑥 ∗ = 10.9602
2022/2023 Omega Semester 16
Exercise
Use the golden section method to:
1. find the value of 𝑥 in the interval 0, 1 which minimizes the function
𝑓 𝑥 = 𝑥 𝑥 − 1.5 .
2. find the maximum of the function 𝑓 𝑥 = sin 𝑥 6 + tan 1 − 𝑥 𝑒 30𝑥 in
the interval 0, 1 .

2022/2023 Omega Semester 17