Section Algorithm for Unbounded Search

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)

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.
Calculate the objective function at each of the 3 points and identify which has the smallest value.
If the middle point is the minimum we have a bounded search range between the leftmost and rightmost points; exit.
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
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,
redefine current step size = $\tau \times$ current step size; this provides acceleration of the search
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.
Find the point in the new search range with the minimum objective value.
If it is the middle one, we have a bounded search range,
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