One-dimensional search methods based only on comparison of function values

- for unbounded (or loosely bounded) search,
- within a bounded interval.

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.

- Start searching near a chosen point, with chosen step size.

- Check to right and left.

- Accelerate search in whichever direction leads to descent.
- Terminate search when
- (a) a local minimum is bracketed
- (b) a bound of the feasible region is reached:

*x*=*x*_{L}or*x*=*x*_{U}.

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.
,
.

DATA:

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 |

RESULT:

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.

Terminate when

- (a) objective is within some tolerance (for
*f*) across the interval, and/or - (b) interval is smaller than some

tolerance in*x*.

Methods

- 1.
- Third-interval elimination
- 2.
- Half-interval elimination
- 3.
- Golden section search

Divide interval into 3 equal sub-intervals.

Symmetric no preference for one end of the interval or the other.

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.

Eliminate the two sub-intervals which are not adjacent to the minimum

**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.

Eliminate the sub-interval which is not adjacent to the minimum

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.

This

(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,
must satisfy

whose only root between 0 and 1 is

**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 *N*_{i} iterations.

**Third-interval**

Function evaluations = 2

**Half-interval**

Function evaluations =3 + 2 (

**Golden section**

(1 - 0.3820)^{Ni} = 10^{-3}

Function evaluations =2 + 1 (

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 5.3.2.2

When no information is available except comparison of function values,

- perform an unbounded search using acceleration
- if no constraints were given, or
- if a smaller bounded search range is desired.

- perform bounded search using
- an equal-interval method (half-interval is best), or
- Golden Section (most efficient `unbiased' method).

Return to Section 5.3 Index

Return to Section 5 Index

Course Organiser Last modified: Tue Aug 25 12:16:41 BST