Piecewise linear bounding functions in univariate global optimization

The paper addresses the problem of constructing lower and upper estimators for univariate functions. This problem is of crucial importance in global optimization, where such bounds are used to reduce the search area. We propose to use piecewise linear estimators for bounding univariate functions and show how such estimators can be derived from the function’s algebraic expression. The basic properties of such estimators are formulated and proved. We implemented the algorithms for the automated construction of lower and upper piecewise linear estimators and experimentally compared the proposed approach with the first-order interval bounds, Pijavskij method, and slope arithmetic. Numerical examples demonstrate that the piecewise linear estimators are more accurate with respect to the mentioned approaches. We also show that global optimization algorithms can significantly benefit from using piecewise linear estimators. Another advantage of the proposed approach is that the objective function does not have to be differentiable. This feature can favorably distinguish this method from other methods where the first and second derivatives are used.