# Lattice search

This finds the maximum of a unimodal function on a finite set, $LaTeX: \{x_1, x_2, \ldots, x_m\}$, by evaluating the function at points placed by the modified fibonacci sequence: $LaTeX: 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 $LaTeX: [a, b]$ and $LaTeX: f(x) < f(y)$, the new interval is $LaTeX: [x+1, b]$ dropping the point $LaTeX: 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 $LaTeX: K_n = F_{n+1} - 1$, reflecting the improvement that accumulates as $LaTeX: n$ increases, for the extra point dropped after each evaluation. The placement ratio, $LaTeX: 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 maximum number of evaluations needed to find the maximum on a given set of points. If the number in that set is $LaTeX: K_N$, the number of evaluations is $LaTeX: 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 $LaTeX: K_{N-1} < m < K_N,$ let the set be $LaTeX: {x_1, \ldots, x_m, y_1, \ldots, y_k\}$, where $LaTeX: k = K_N- m$. Then, the (minimum) number of evaluations to guarantee finding the maximum of any unimodal function is $LaTeX: N$.