Lattice search

From Glossary

Jump to: navigation, 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.


Views
Personal tools