Construction of continuous piecewise-linear bounds for the composition of functions from one variable

Abstract

This article addresses the problem of constructing lower and upper bounding functions for univariate functions. This problem is of a crucial importance in global deterministic optimization, where such bounds are used both to estimate а target function and to reduce the search area of the global extremum. In practice, existing approaches to global optimization do not always show high accuracy of bounding functions. The article develops the previously proposed approach of using piecewise-linear bounds as an estimate of functions of one variable. The main focus is on the construction of piecewise-linear bounds for the composition of functions, as well as on the continuity of these bounds. The necessary theoretical statements with proofs that allow the synthesis of continuous piecewise-linear estimates from the expression of a function presented in algebraic form are considered. Using the composition of trigonometric functions as an example, an algorithm for constructing the lower piecewise-linear boundary using the properties of convexity and concavity is considered in detail. The computational experiment presented in the article shows the method of constructing the lower  piecewiselinear boundary and compares the proposed approach with the technique of using interval analysis and slope arithmetic. The proposed approach demonstrates high accuracy and continuity of the obtained bounds.