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

Alexander L. Usov


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.

Full Text:

PDF (Russian)


Khamisov Oleg Posypkin Mikhail Usov Alexander. Piecewise linear bounding functions for univariate global optimization. –– IX INTERNATIONAL CONFERENCE OPTIMIZATION AND APPLICATIONS (2018);

Usov Alexander. Piecewise linear bounding functions in univariate

global optimization // International Journal of Open Information Technologies. –– 2019. –– Vol. 7, no. 5. –– P. 9–16.

Evtushenko Yurii Gavrilovich. A numerical method of search for the global extremum of functions (scan on a nonuniform net) // Zhurnal Vychislitel’noi Matematiki i Matematicheskoi Fiziki. –– 1971. –– Vol. 11, no. 6. –– P. 1390–1403.

Evtushenko Yury, Posypkin Mikhail. A deterministic approach to global box-constrained optimization // Optimization Letters. –– 2013. –– Vol. 7, no. 4. –– P. 819–829.

Ershov A.R, Khamisov Oleg Valerievich. Automatic global optimization // Diskretnyi Analiz i Issledovanie Operatsii. –– 2004. –– Vol. 11, no. 2. –– P. 45–68.

Khamisov Oleg. Explicit univariate global optimization with piecewise linear support functions. –– Proc. DOOR 2016,, Vol. 1623. P. 218-255, online

Ratz Dietmar. An optimized interval slope arithmetic and its application. –– Inst. für Angewandte Mathematik, 1996.

Bompadre A., Mitsos A. Convergence rate of McCormick relaxations // Journal of Global Optimization. –– 2012. –– Vol. 52, no. 1. –– P. 1–28.

Floudas C.A., Gounaris C.E. A review of recent advances in global optimization // Journal of Global Optimization. –– 2009. –– Vol. 45, no. 1. –– P. 3–38.

Khajavirad Anita, Sahinidis Nikolaos. Convex envelopes of products of convex and component-wise concave functions // Journal of Global Optimization. –– 2012. –– Vol. 52, no. 3. –– P. 3911–409.

Khamisov Oleg. Optimization with quadratic support functions in nonconvex smooth optimization. –– AIP Conference Proceedings 1776, 050010 (2016); doi: 10.1063/1.4965331.

Kudryavtsev L.D. Course of mathematical analysis. volume 1: textbook for bachelors-6th ed., reprint. and additional. –– 2017.

Shary S.P. Finite-dimensional interval analysis. institute of computational technologies, ras. –– 2016.

Hansen Eldon, Walster G William. Global optimization using interval analysis: revised and expanded. –– CRC Press, 2003.

Ratz Dietmar. A nonsmooth global optimization technique using slopes: the one-dimensional case // Journal of Global Optimization. –– 1999. –– Vol. 14, no. 4. –– P. 365–393.

Pardalos panos M, Rosen JB. Reduction of nonlinear integer separable programming problems // International journal of computer mathematics. –– 1988. –– Vol. 24, no. 1. –– P. 55–64.

Rosen J Ben, Pardalos Panos M. Global minimization of largescale constrained concave quadratic problems by separable programming // Mathematical Programming. –– 1986. –– Vol. 34, no. 2. –– P. 163–174.


  • There are currently no refbacks.

Abava  Absolutech Convergent 2020

ISSN: 2307-8162