Section 5.3.2.1: Algorithm for Unbounded Search

Given:

xL	lower bound specified for optimisation
xU	upper bound specified for optimisation
x0	starting point for search (should be feasible: xL < x0 < xU)
	starting step size
	acceleration factor (greater than 1)

and a procedure to evaluate f(x)

1.

Construct 3 initial search points at .

If either of the adjacent points crosses x_L or x_U reset the value to the constraint.

2.

Calculate the objective function at each of the 3 points and identify which has the smallest value.

3.

If the middle point is the minimum we have a bounded search range between the leftmost and rightmost points; exit.

4.

Otherwise, iteratively search in the direction of descent:

+ if the rightmost point was the minimum,
- if the leftmost point was minimum.

Set the current step size = initial step size

(a)

If the point furthest in the direction of search is on a constraint boundary (x_L or x_U), we have a bounded search range between that point and the one next to it; exit. Otherwise,

(b)

redefine current step size = current step size; this provides acceleration of the search

(c)

create a new search point beyond the rightmost (+) or leftmost(-) by the new current step size (but do not pass the constraint boundary);
calculate the objective at this point and with the adjacent two points define a new search range.

(d)

Find the point in the new search range with the minimum objective value.

(e)

If it is the middle one, we have a bounded search range,

(f)

otherwise repeat from 4(a) until a bounded search range is found, or too many iterations.

Return to Section 5.3.2
Return to Section 5.3 Index
Return to Section 5 Index