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)
$\alpha$ starting step size
$\tau$ acceleration factor (greater than 1)

and a procedure to evaluate f(x)

1.
Construct 3 initial search points at $x_0, x_0 - \alpha, x_0 + \alpha $.
If either of the adjacent points crosses xL or xU 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 (xL or xU), we have a bounded search range between that point and the one next to it; exit. Otherwise,
(b)
redefine current step size = $\tau \times$ 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

Course Organiser
Last modified: Tue Aug 25 11:01:25 BST