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.

### Unbounded search

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.

### Basic idea

• 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 = xL or x = xU.

See section 5.3.2.1 for algorithm for unbounded search.

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.

### Example

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

### Bounded search

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

### Third-interval elimination

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.

### Half-interval elimination

Divide interval into 4 equal sub-intervals.

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

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.

### Golden section search

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

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.

### Comparison of methods

Reduce search range to 0.001 of initial length. Let this process take Ni iterations.

Third-interval

Function evaluations = 2 Ni = 36

Half-interval

Function evaluations =3 + 2 (Ni - 1) = 21

Golden section

(1 - 0.3820)Ni = 10-3

Function evaluations =2 + 1 (Ni - 1) = 16

### Example

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

### Summary

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

Course Organiser