One-dimensional search methods based only on comparison of function values
Use when derivative f'(x) is inconvenient or expensive to evaluate, or is not available.
Always pose the optimisation problem with constraints!
But if a local minimum is suspected within a much smaller region than defined by lower and upper bounds on x, then it may be worthwhile starting with an unrestricted search to establish a tighter bounded search region.
Acceleration provides a compromise between taking many short steps, and finding a very large bounded search region.
This version of the algorithm is slightly complicated because we assume there are bounds in the problem.
Minimise f(D) = 2.0 D + 0.4 + 0.5 D-4.75 s.t. , .
|Lower bound for diameter||0.1 m|
|Upper bound for diameter||2.5 m|
|Starting value for diameter||0.2 m|
|Initial step in diameter||0.1 m|
|Step acceleration factor||2.0|
|D = 0.1||cost = 28117.666|
|D = 0.2||cost = 1045.707|
|D = 0.3||cost = 153.280|
|D = 0.5||cost = 14.854|
|D = 0.9||cost = 3.024|
|D = 1.7||cost = 3.840|
Lower bound for bounded search 0.5 m
Upper bound for bounded search 1.7 m
When a region is known to contain a minimum for the problem, apply an iterative strategy for interval reduction.
Systematically exclude one or more sub-intervals in which the optimum does not lie. Thereby create a new interval for the next iteration.
Divide interval into 3 equal sub-intervals.
Eliminate the sub-interval which is not adjacent to the minimum f.
Cost: 2 function evaluations per iteration
Benefit: Reduce search range by 33.3 % at next iteration.
Drawback: the interior point already calculated cannot be re-used within the new interval.
Divide interval into 4 equal sub-intervals.
Cost: 2 or 3 function evaluations per iteration
Benefit: Reduce search range by 50 % at next iteration.
Advantage: after the first iteration which needs 3 function evaluations, the middle point in the surviving two sub-intervals can be re-used. Thus rapidly becomes more efficient than `third-interval' method.
Divide interval into 3 sub-intervals.
The sub-intervals are symmetric, but not equal.
Then ensure that sub-intervals for the new interval of length L' can be constructed with the same relative proportions as those in the previous iteration.
(a) permits re-use of one point from the previous iteration;
(b) does not prejudice the rest of the search by changing the relative sub-interval sizes.
To achieve this condition,
Cost: 1 or 2 function evaluations per iteration
Benefit: Reduce search range by 38.2 % at next iteration.
Advantage: after the first iteration which needs 2 function evaluations, the point within the surviving sub-interval can be re-used. The method was designed to achieve this.
Golden section is the most efficient method which makes no assumption (based on gradient information, for example) about where in the search interval the minimum is likely to be.
Reduce search range to 0.001 of initial length. Let this process take Ni iterations.
Continue with the pipe diameter optimisation.
Start bounded search with 0.5 < D < 1.7 m.
Set diameter tolerance to 0.001m.
Use Golden Section. See section 126.96.36.199
When no information is available except comparison of function values,
Return to Section 5.3 Index
Return to Section 5 Index
Course Organiser Last modified: Tue Aug 25 12:16:41 BST