Numerical Methods (Engr-280)

Optimization
Finding minima and maxima

Dakar American University of Science and Technology (DAUST)

Dr. Amadou Toure

11 April, 2023

Dr. Amadou Toure Numerical Methods (Engr-280) Optimization 11 April, 2023 1 / 12

Dr. Amadou Toure Numerical Methods (Engr-280) Optimization 11 April, 2023 2 / 12
Motivation
Optimization: the process of creating something that is as effective as possible.

Engineers design devices and products that perform tasks in an efficient

fashion for the least cost.
Optimization: attempt to balance performance and limitations.
From a mathematical perspective:
▶ optimization deals with finding the maxima and minima of a function
that depends on one or more variables.
▶ The goal is to determine the values of the variables that yield maxima
or minima for the function.
Most practical problems require numerical, computer solutions.
Numerically, optimization is similar in spirit to the root-location methods.
▶ both involve guessing and searching for a point on a function.
▶ Root location → searching for where the function equals zero.
▶ Optimization → searching for the function’s extreme points.

Dr. Amadou Toure Numerical Methods (Engr-280) Optimization 11 April, 2023 3 / 12

Cut equal square sides 𝑥 of each corner and fold to make box
Find the value of 𝑥 that maximizes the volume of the box

𝑉 (𝑥) = 𝐻 × 𝐿 × 𝑊
= 𝑥(12 − 2𝑥)(10 − 2𝑥)
= 4𝑥(6 − 𝑥)(5 − 𝑥)
= 4𝑥(𝑥2 − 11𝑥 + 30)
maximum: one of the solutions of:
𝑑𝑉 (𝑥)
= 12𝑥2 − 88𝑥 + 120 = 0
𝑑𝑥
Roots: 𝑥 = 5.52, 𝑥 = 1.81
𝑉 (5.52) ≈ −5.81,
𝑉 (1.81) ≈ 96.77
max Volume ≡ corner cut:1.81 × 1.81
Note: Solution can be approximated by
inspecting the plot of 𝑉 (𝑥) for 𝑥 > 0

Dr. Amadou Toure Numerical Methods (Engr-280) Optimization 11 April, 2023 4 / 12

 Root vs Optima
𝑓(𝑥) ′
𝑓 (𝑥) = 0
″
𝑓 (𝑥) < 0 Maximum

𝑓(𝑥) = 0

Root
Root Root 𝑥

Optimum:
Where the curve is flat
′
′ ≡ 𝑓 (𝑥) = 0
Minimum 𝑓 (𝑥) = 0 ″
″ 𝑓 (𝑥) ⇒ maximum or minimum:
𝑓 (𝑥) > 0 ″
⎧𝑓 (𝑥) > 0 Minimum
′ { ″
𝑓 (𝑥) = 0 ⎨𝑓 (𝑥) < 0 Maximum
{𝑓 ″ (𝑥) = 0 Inflection
⎩
′
One Optimization approach: solving the root problem: 𝑓 (𝑥) = 0
Dr. Amadou Toure Numerical Methods (Engr-280) Optimization 11 April, 2023 5 / 12
 𝑓(𝑥) Minimization of 𝑓(𝑥) ≡ Maximization of −𝑓(𝑥)

𝑓(𝑥)

𝑥∗ Minimum 𝑓(𝑥)

𝑥
Maximum −𝑓(𝑥)

−𝑓(𝑥)

The process of finding a maximum versus finding a minimum is essentially identical

the same value x∗ both minimizes f(x) and maximizes −f(x)
Dr. Amadou Toure Numerical Methods (Engr-280) Optimization 11 April, 2023 6 / 12
Some Optimization Methods

Function of one variable

If 𝑓(𝑥) is known and continuous, use methods for zeros of
′
functions to find 𝑓 (𝑥) = 0
▶ Then make sure that you really found a minimum!

Golden section search

Parabolic interpolation
In Matlab: fminbnd

Dr. Amadou Toure Numerical Methods (Engr-280) Optimization 11 April, 2023 7 / 12

Golden section search, for minimum
Like bisection, Golden section search is a bracketing method
two points inside the interval are used.
▶ Given the bracket [𝑙, 𝑢] the two values in between are chosen as
(𝑢 − 𝑙) (𝑢 − 𝑙)
𝑚𝑙 = 𝑢 − , 𝑚𝑢 = 𝑙 +
𝜙 𝜙
√
(1 + 5)
where 𝜙 = is the golden ratio
2
Then either 𝑙 is moved to 𝑚𝑙 or 𝑢 to 𝑚𝑢 in such that:
smallest of 𝑓(𝑚𝑙 ) and 𝑓(𝑚𝑢 ) still remains in the interval.

This process is repeated until we are satisfied with the precision.

1
The error is multiplied with ≈ 0.61 in every iteration
𝜙
√
1 2 5−1
▶ Note: = √ = =𝜙−1
𝜙 1+ 5 2
Dr. Amadou Toure Numerical Methods (Engr-280) Optimization 11 April, 2023 8 / 12
𝑓(𝑥) The Golden-Section Search Algorithm
Eliminate
Minimum Initial step: choose two interior points
(𝑥1 , 𝑥2 ) according to the golden ratio (𝜙)

𝑥1 = 𝑥𝑙 + 𝑑
𝑥2 = 𝑥𝑢 − 𝑑
xl 𝑑 𝑥1 𝑥 𝑑 = (𝜙 − 1)(𝑥𝑢 − 𝑥𝑙 )
𝑥2 𝑑 xu
𝑙1 𝑙2

𝑙1 + 𝑙2

𝑓(𝑥) 𝑙1 + 𝑙2 𝑙 𝑙
= 1 , Let 𝜙 = 1
Old Old 𝑙1 𝑙2 𝑙2
𝑥2 𝑥1 → 𝜙2 − 𝜙 − 1 = 0
√
1+ 5
+ve root: 𝜙 = = 1.6180339 …
2

xl 𝑥2 𝑥1 xu 𝑥
Second step: define a new interval that en-
compasses the optimum
New
Dr. Amadou Toure Numerical Methods (Engr-280) Optimization 11 April, 2023 9 / 12
Parabolic search, for minimum
We use a bracket as well, and some given point in the interior.
Let the bracket be [𝑥1 , 𝑥3 ] and the point in the interior 𝑥2 .
There is only one parabola connecting three points.
▶ Then we can differentiate it,
▶ set the result equal to zero, and solve for an estimate of the optimal 𝑥 .
4

The new point is found by fitting a degree 2 polynomial through the points
(𝑥1 , 𝑓(𝑥1 )), (𝑥2 , 𝑓(𝑥2 )) and (𝑥3 , 𝑓(𝑥3 )).
The new point 𝑥4 is found as the minimum to this degree 2 polynomial.
1 (𝑥1 − 𝑥2 )2 (𝑓(𝑥2 ) − 𝑓(𝑥3 )) − (𝑥3 − 𝑥2 )2 (𝑓(𝑥2 ) − 𝑓(𝑥1 ))
▶ 𝑥4 = 𝑥2+
2 (𝑥1 − 𝑥2 )(𝑓(𝑥2 ) − 𝑓(𝑥3 )) − (𝑥3 − 𝑥2 )(𝑓(𝑥2 ) − 𝑓(𝑥1 ))
▶ Then one of the enpoints of the bracket is moved to the one of the

interior points with greatest function value.

▶ The other interior point must remain in the bracket.

Repeat this until a satisfactory solution is found.

This method is fast but insecure!
Dr. Amadou Toure Numerical Methods (Engr-280) Optimization 11 April, 2023 10 / 12
 True Maximum Parabololic approximation of Maximum
𝑓(𝑥)

True Function
Parabolic Function

𝑥1 𝑥2 𝑥4 𝑥3 𝑥
Dr. Amadou Toure Numerical Methods (Engr-280) Optimization 11 April, 2023 11 / 12
MATLAB Function: fminbnd

Dr. Amadou Toure Numerical Methods (Engr-280) Optimization 11 April, 2023 12 / 12