Piecewise Linear Bounding Functions in Univariate Global Optimization

Abstract

The paper addresses the problem of constructing lower and upper bounding functions for univariate functions. This problem is of a crucial importance in global optimization where such bounds are used by deterministic methods to reduce the search area. Existing approaches do not always show the high accuracy of limiting functions in global optimization. It should be noted that bounding functions are expected to be relatively easy to construct and manipulate with. To solve this problem, it is proposed to use piecewise linear estimators for bounding univariate functions. The article gives a definition of a piecewise linear function, discusses their basic properties, as well as the basic arithmetic operations applicable to them. Using an example of elementary mathematical functions, an algorithm is proposed for constructing lower and upper piecewise linear estimates. For this purpose, the properties of convexity and concavity of elementary functions are applied. The rules proposed in the paper enable an automated synthesis of lower and upper bounds from the function’s expression in an algebraic form. The numerical examples presented in the article compare the proposed approach with the technique of using interval analysis and slope arithmetic. The proposed approach demonstrates the high accuracy piecewise linear bounds.