Piecewise Linear Bounding Functions in Univariate Global Optimization

Alexander Usov

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.

Full Text:

PDF (Russian)

References


Khamisov Oleg, Posypkin Mikhail, Usov Alexander. Piecewise linear bounding functions for univariate global optimization // Optimization and Applications / Ed. by Yury Evtushenko, Milojica Jaćimović, Michael Khachay et al. — Cham : Springer International Publishing, 2019. — P. 170–185.

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.

Shary S.P. Finite-dimensional interval analysis. institute of compunational technologies, sb ras, novosibirsk. — 2016.

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

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

Ershov AR, 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, CEUR-WS.org, Vol. 1623. P. 218-255, online http://ceur-ws.org/Vol-1623/papermp19.pdf.

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.

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.


Refbacks

  • There are currently no refbacks.


Abava   FRUCT 2019

ISSN: 2307-8162