Optimal Search for the Global Maximum of Functions with Bounded Seminorm
Patricio Basso · SIAM Journal on Numerical Analysis · 1985
This paper deals with methods seeking the global maximum of a real valued function defined over a real interval $[a,b]$ with prescribed seminorm, i.e. the integral of the square of the derivative. An optimal one-step search algorithm is devised, which provides the minimum guaranteed value of the Lebesgue measure of the set of possible values of the global maximum after evaluating a given information operator at the next point. At each step of the algorithm the value of the function at a new point $x_n $ and the se minorm taken over the interval $[a,x_n ]$ are evaluated. In order to obtain the optimal algorithm, the interpolatory envelope of a certain class of functions is constructed utilizing the minimum seminorm properties of the first order spline functions. A simple search method, which is near optimal, is also described.