# Lattice search

### From Glossary

This finds the maximum of a
unimodal function on a finite set, ,
by evaluating the function at points placed by the *modified fibonacci sequence*:
. This modification
comes from the improvement obtained by dropping the inferior end
point after an evaluation: if the set is in and
, the new interval is dropping
the point 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 , reflecting the improvement that accumulates as increases, for the extra point dropped after each evaluation. The placement ratio, , 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 maximum number of evaluations needed to find the maximum on a given set of points. If the number in that set is , the number of evaluations is . 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 let the set be , where . Then, the (minimum) number of evaluations to guarantee finding the maximum of any unimodal function is .