Piecewise linear bounding functions in univariate global optimization
- PDF / 1,710,087 Bytes
- 17 Pages / 595.276 x 790.866 pts Page_size
- 36 Downloads / 186 Views
FOCUS
Piecewise linear bounding functions in univariate global optimization Mikhail Posypkin1
· Alexander Usov1 · Oleg Khamisov2
© Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract 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. Keywords Univariate global optimization · Piecewise linear functions · Estimators · Deterministic methods
1 Introduction Deterministic global optimization heavily relies on bounds for objectives and constraints. By comparing the upper and lower bounds, the search region can be significantly reduced. The bounds are calculated as a solution to a relaxed problem where objectives and/or constraints are substituted by bounding functions. The latter is also referenced to as minorants, majorants, estimators, support functions in the literature. Those functions have a relatively simple structure that allows an efficient resolution of the relaxed problem. Communicated by Yaroslav D. Sergeyev.
B
Mikhail Posypkin [email protected] Alexander Usov [email protected] Oleg Khamisov [email protected]
1
Federal Research Center “Computer Science and Control” of the Russian Academy of Sciences, Vavilova 40, Moscow, Russia
2
Melentiev Energy Systems Institute of Siberian Branch of the Russian Academy of Sciences, Lermontov St., 130, Irkutsk, Russia 664033
In this paper, we consider a problem of finding a global minimum of a univariate function f (x) over interval [a, b]. Assume that the objective function has lower and upper bounding functions. The function φ(x) is called the lower(upper) bounding function for the function f (x) on the interval [a, b] if f (x) ≥ φ(x) ( f (x) ≤ φ(x)) for any x ∈ [a, b]. Suppose we know the lower bounding function φ(x) for the objective f (x). Then, we can exclude from the further consideration the set of points satisfying the following inequality:
φ(x) ≥ fr − ε,
(1)
where fr is a record (the best solution found) and ε is a given accuracy of the solution (Evtush
Data Loading...
