Bounding phase method
Bounding phase method is used to bracket the minimum of a function. This
method guarantees to bracket the minimum of a unimodal function. The
algorithm begins with an initial guess and thereby finds a search direction
based on two more function evaluations in the vicinity of the initial guess.
Thereafter, an exponential search strategy is adopted to reach the optimum.
In the following algorithm, an exponent of two is used, but any other value
may very well be used.
Algorithm for Bounding phase method
Algorithm:
I Step 1: Choose an initial guess x(0) and an increment ∆. Set k = 0.
Algorithm for Bounding phase method
Algorithm:
I Step 1: Choose an initial guess x(0) and an increment ∆. Set k = 0.
I Step 2:
If f (x(0) − |∆|) ≥ f (x(0) ) ≥ f (x(0) + |∆|), then ∆ is positive;
Algorithm for Bounding phase method
Algorithm:
I Step 1: Choose an initial guess x(0) and an increment ∆. Set k = 0.
I Step 2:
If f (x(0) − |∆|) ≥ f (x(0) ) ≥ f (x(0) + |∆|), then ∆ is positive;
Else if f (x(0) − |∆|) ≤ f (x(0) ) ≤ f (x(0) + |∆|), then ∆ is negative;
Algorithm for Bounding phase method
Algorithm:
I Step 1: Choose an initial guess x(0) and an increment ∆. Set k = 0.
I Step 2:
If f (x(0) − |∆|) ≥ f (x(0) ) ≥ f (x(0) + |∆|), then ∆ is positive;
Else if f (x(0) − |∆|) ≤ f (x(0) ) ≤ f (x(0) + |∆|), then ∆ is negative;
Else go to Step 1.
I Step 3: Set x(k+1) = x(k) + 2k ∆.
Algorithm for Bounding phase method
Algorithm:
I Step 1: Choose an initial guess x(0) and an increment ∆. Set k = 0.
I Step 2:
If f (x(0) − |∆|) ≥ f (x(0) ) ≥ f (x(0) + |∆|), then ∆ is positive;
Else if f (x(0) − |∆|) ≤ f (x(0) ) ≤ f (x(0) + |∆|), then ∆ is negative;
Else go to Step 1.
I Step 3: Set x(k+1) = x(k) + 2k ∆.
I Step 4: If f (x(k+1) ) ≤ f (x(k) ), set k = k + 1 and go to Step 3; Else the
minimum lies in the interval (x(k1) , x(k+1) ) and Terminate.
Remark
1. If the chosen ∆ is large, the bracketing accuracy of the minimum point
is poor but the bracketing of the minimum is faster.
Algorithm for Bounding phase method
Algorithm:
I Step 1: Choose an initial guess x(0) and an increment ∆. Set k = 0.
I Step 2:
If f (x(0) − |∆|) ≥ f (x(0) ) ≥ f (x(0) + |∆|), then ∆ is positive;
Else if f (x(0) − |∆|) ≤ f (x(0) ) ≤ f (x(0) + |∆|), then ∆ is negative;
Else go to Step 1.
I Step 3: Set x(k+1) = x(k) + 2k ∆.
I Step 4: If f (x(k+1) ) ≤ f (x(k) ), set k = k + 1 and go to Step 3; Else the
minimum lies in the interval (x(k1) , x(k+1) ) and Terminate.
Remark
1. If the chosen ∆ is large, the bracketing accuracy of the minimum point
is poor but the bracketing of the minimum is faster.
2. On the other hand, if the chosen ∆ is small, the bracketing accuracy is
better, but more function evaluations may be necessary to bracket the
minimum.
Algorithm for Bounding phase method
Algorithm:
I Step 1: Choose an initial guess x(0) and an increment ∆. Set k = 0.
I Step 2:
If f (x(0) − |∆|) ≥ f (x(0) ) ≥ f (x(0) + |∆|), then ∆ is positive;
Else if f (x(0) − |∆|) ≤ f (x(0) ) ≤ f (x(0) + |∆|), then ∆ is negative;
Else go to Step 1.
I Step 3: Set x(k+1) = x(k) + 2k ∆.
I Step 4: If f (x(k+1) ) ≤ f (x(k) ), set k = k + 1 and go to Step 3; Else the
minimum lies in the interval (x(k1) , x(k+1) ) and Terminate.
Remark
1. If the chosen ∆ is large, the bracketing accuracy of the minimum point
is poor but the bracketing of the minimum is faster.
2. On the other hand, if the chosen ∆ is small, the bracketing accuracy is
better, but more function evaluations may be necessary to bracket the
minimum.
3. This method of bracketing the optimum is usually faster than exhaustive
search method discussed in the previous section.
Example
Example
Find the minimum of the function f (x) = (100 − x)2 using the Bounding
Phase Method with x(0) = 30 and ∆ = 5.
Solution:
Iteration:1
Step 1. We choose an initial guess x(0) = 30 and an increment ∆ = 5. We also
set k = 0.
Example
Example
Find the minimum of the function f (x) = (100 − x)2 using the Bounding
Phase Method with x(0) = 30 and ∆ = 5.
Solution:
Iteration:1
Step 1. We choose an initial guess x(0) = 30 and an increment ∆ = 5. We also
set k = 0.
Step 2. We calculate three function values to proceed with the algorithm:
f (x(0) − |∆|) = f (25) = 5625, f (x(0) ) = f (30) = 4900, and
f (x(0) + |∆|) = f (35) = 4225. We observe that
f (x(0) − |∆|) > f (x(0) ) > f (x(0) + |∆|). Thus, we set ∆ = +0.5.
Example
Example
Find the minimum of the function f (x) = (100 − x)2 using the Bounding
Phase Method with x(0) = 30 and ∆ = 5.
Solution:
Iteration:1
Step 1. We choose an initial guess x(0) = 30 and an increment ∆ = 5. We also
set k = 0.
Step 2. We calculate three function values to proceed with the algorithm:
f (x(0) − |∆|) = f (25) = 5625, f (x(0) ) = f (30) = 4900, and
f (x(0) + |∆|) = f (35) = 4225. We observe that
f (x(0) − |∆|) > f (x(0) ) > f (x(0) + |∆|). Thus, we set ∆ = +0.5.
Step 3. We compute the next guess: x(1) = x(0) + 20 ∆ = 35.
Example
Example
Find the minimum of the function f (x) = (100 − x)2 using the Bounding
Phase Method with x(0) = 30 and ∆ = 5.
Solution:
Iteration:1
Step 1. We choose an initial guess x(0) = 30 and an increment ∆ = 5. We also
set k = 0.
Step 2. We calculate three function values to proceed with the algorithm:
f (x(0) − |∆|) = f (25) = 5625, f (x(0) ) = f (30) = 4900, and
f (x(0) + |∆|) = f (35) = 4225. We observe that
f (x(0) − |∆|) > f (x(0) ) > f (x(0) + |∆|). Thus, we set ∆ = +0.5.
Step 3. We compute the next guess: x(1) = x(0) + 20 ∆ = 35.
Step 4. The function value at x(1) is 4225 which is less than that at x(0) . Thus,
we set k = 1 and go to Step 3. This completes one iteration of the
Bounding Phase algorithm.
Example
Example
Find the minimum of the function f (x) = (100 − x)2 using the Bounding
Phase Method with x(0) = 30 and ∆ = 5.
Solution:
Iteration:1
Step 1. We choose an initial guess x(0) = 30 and an increment ∆ = 5. We also
set k = 0.
Step 2. We calculate three function values to proceed with the algorithm:
f (x(0) − |∆|) = f (25) = 5625, f (x(0) ) = f (30) = 4900, and
f (x(0) + |∆|) = f (35) = 4225. We observe that
f (x(0) − |∆|) > f (x(0) ) > f (x(0) + |∆|). Thus, we set ∆ = +0.5.
Step 3. We compute the next guess: x(1) = x(0) + 20 ∆ = 35.
Step 4. The function value at x(1) is 4225 which is less than that at x(0) . Thus,
we set k = 1 and go to Step 3. This completes one iteration of the
Bounding Phase algorithm.
The iterations values are given in the next slide.
Bounding Phase method
k x(k) x(k+1) f (x(k) ) f (x(k+1) ) f (x(k) ) ≤ f (x(k+1) )
0 30 35 4900 4225 No
1 35 45 4225 3025 No
2 45 65 3025 1225 No
3 65 105 1225 25 No
4 105 185 25 7225 Yes
Therefore, the minimum lies in (65, 185).
What is the advantage and disadvantage of the Bracketing
Methods
• The exhaustive search method requires, in general, more function
evaluations to bracket the minimum but the user has a control over the
final bracketing range.
What is the advantage and disadvantage of the Bracketing
Methods
• The exhaustive search method requires, in general, more function
evaluations to bracket the minimum but the user has a control over the
final bracketing range.
• The bounding phase method can bracket the minimum very fast
(usually exponentially fast) but the final bracketing range may be poor.
What is the advantage and disadvantage of the Bracketing
Methods
• The exhaustive search method requires, in general, more function
evaluations to bracket the minimum but the user has a control over the
final bracketing range.
• The bounding phase method can bracket the minimum very fast
(usually exponentially fast) but the final bracketing range may be poor.
Exercise:
1. Bracket the minimum for the function f (x) = x sin(4x) on [0, 3] using
Exhaustive search method with n = 6. Do 5 iterations.
2. Given that f (x) = x2 + 2x in the interval [−3, 4]. Apply the Exhaustive
search method on the identified optimum interval in [−3; 4], with the
number of intermediate points as n = 10 to further identify the
improved optimum interval.
3. Perform five iterations to minimize the function f (x) = x(x − 1.5),
x ∈ [0, 1] using the Bounding Phase Method with x(0) = 0 and ∆ = 0.1.
4. Perform five iterations of Exhaustive search method to find the
54
minimum of the function f (x) = x2 + in the interval (0, 5).
x
Consider only 10 Intermediate points or n = 10.
5. Bracket the minimum for the function f (x) = x sin(4x) on [0, 3] using
Bounding Phase method with x(0) = 0 and ∆ = 0.5. Do 5 iterations.
6. Minimize f (x) = (100 − x)2 , x ∈ (80, 120), n = 5, Perform five
iterations of Exhaustive Search Method.
54
7. Find the minimum of the function f (x) = x2 + using the Bounding
x
(0)
Phase Method with x = 0.6 and ∆ = 0.5.