SEQUENTIAL MINIMAX SEARCH FOR A MAXIMUM

SEQUENTIAL MINIMAX SEARCH FOR A MAXIMUM

1953 | J. KIEFER
The paper presents a sequential minimax search algorithm for finding the maximum of a unimodal function on the unit interval without assuming continuity or differentiability. For any ε > 0 and number N of observations, the algorithm provides an ε-minimax procedure that guarantees an interval containing the maximum with length no greater than ε plus the minimal possible length for N observations. The algorithm is based on the Fibonacci sequence and recursively divides the interval based on function evaluations. It is shown that this procedure satisfies the minimax property, meaning it minimizes the maximum possible interval length over all possible functions in the class F. The paper also discusses the limitations of the minimax procedure and suggests an alternative strategy that is not minimax but often useful in practice. The algorithm is compared to other methods and shown to be more efficient when the number of observations is not fixed in advance. The paper concludes with a discussion of the broader implications of these methods for the theory of divergent iteration processes.The paper presents a sequential minimax search algorithm for finding the maximum of a unimodal function on the unit interval without assuming continuity or differentiability. For any ε > 0 and number N of observations, the algorithm provides an ε-minimax procedure that guarantees an interval containing the maximum with length no greater than ε plus the minimal possible length for N observations. The algorithm is based on the Fibonacci sequence and recursively divides the interval based on function evaluations. It is shown that this procedure satisfies the minimax property, meaning it minimizes the maximum possible interval length over all possible functions in the class F. The paper also discusses the limitations of the minimax procedure and suggests an alternative strategy that is not minimax but often useful in practice. The algorithm is compared to other methods and shown to be more efficient when the number of observations is not fixed in advance. The paper concludes with a discussion of the broader implications of these methods for the theory of divergent iteration processes.
Reach us at info@study.space