Minimax Optimization of Unimodal Functions by Variable Block Search

Abstract

A minimax search plan is developed for locating the maximum of a one dimensional unimodal function using a sequence of blocks of simultaneous function evaluations. Any number of evaluations can be made in each block, generalizing a previously developed constant block plan based on the Avriel numbers [1, 5]. A new set of numbers is produced, containing the Avriel numbers as a subset and filling the large gaps between consecutive Avriel numbers. This enables the selection of a search strategy more closely meeting the desired reduction ratio, reducing the number of experiments required by as much as 50% compared to constant block search. The proposed search strategy is optimal in the sense that for a required final interval of uncertainty, known to contain the point where the function obtains its maximum, and for given values for the number of experiments in each block, it has the largest possible starting interval. A plan for determining the optimal number of experiments per block is given. A discrete variable version of the search plan is also described.