LATTICE SEARCH

Lattice search - This finds the maximum of a unimodal function on a finite set, (x1, x2, ..., xm), by evaluating the function at points placed by the modified fibonacci sequence : K_(n+2) = K_(n+1) + K_n + 1. This modification comes from the improvement obtained by dropping the inferior end point after an evaluation: if the set is in [a, b] and f(x) < f(y), the new interval is [x+1, b] dropping the point x from the remaining search set. The method proceeds the same as fibonacci search , except the placements follow the modified fibonacci sequence, which is equivalent to K_n = F_(n+1) - 1, reflecting the improvement that accumulates as n increases, for the extra point dropped after each evaluation. The placement ratio, K_(n-1)/K_n, also approaches the golden mean , so lattice search also approaches the golden section search . Some refer to fibonacci search when they mean lattice search. The following table shows the difference. For example, with 20 evaluations, fibonacci search can guarantee finding the maximum on a set of 10,946 points, while lattice search can find it on a set of 17,710 points. Golden section is included for comparison as well. With 20 evaluations it can find the maximum on a set of only 9,349 points.

 n 5 10 15 20 =================================== F_n 8 89 987 10946 K_n 12 143 1596 17710 golden 6 76 843 9349 section =================================== 

Lattice search minimizes the max number of evaluations needed to find the maximum on a given set of points. If the number in that set is K_N, the number of evaluations is N. If the number in the set is not exactly some modified fibonacci number, one can fill in dummy points at the end of the set. For example, if K_(N-1) < m < K_N, let the set be (x1, ..., xm, y1, ..., yk), where k = K_N - m. Then, the (minimum) number of evaluations to guarantee finding the maximum of any unimodal function is N.