Explicit Univariate Global Optimization with Piecewise Linear Support Functions Oleg Khamisov⋆ Melentiev Energy Systems Institute, Lermontov st. 130, Irkutsk, Russia khamisov@isem.irk.ru http://www.sei.irk.ru/ Abstract. Piecewise linear convex and concave support functions com- bined with Pijavskii’s method are proposed to be used for solving global optimization problems. Rules for constructing support functions are in- troduced. Keywords: global minimum, support functions, piecewise concave and convex func- tions. 1 Introduction We study the effectiveness of global optimization technique with nonlinear support functions. It is assumed that objective and constrained functions are explicit functions, and we take this term to mean the following. Given a set of elementary functions, an ex- plicit function can be constructed from the elementary ones by means of the operations of adding, subtraction, multiplication, and division of two functions, multiplication by a constant, as well as the operations of composition and taking maximum or minimum of two functions. It is obvious that the problem of finding the global minimum of an explicit function may be quite complicated because, generally, an explicit function is not convex. Possibilities of explicit functions optimization have already been studied. In [1] ex- plicit functions are called factorable. Following step by step the process of construction of an explicit function, we can also track the global minimum or at least the range of a current function. The question is what is the best way to do this. One of the most commonly used approach to global optimization is based on the properties of the Lipschitz constant of the function to be minimized. The Lipschitz constant is a uniform measure of function’s rate of change over all the feasible set. This is both its advantage and drawback. The Lipschitz constant for any function over any segment can be found as the maximum of the absolute value of its derivative. After that, it is easy to define step by step an estimate of the true Lipschitz constant for any ⋆ This work is supported by the RFBR grand number 15-07-08986 Copyright ⃝ c by the paper’s authors. Copying permitted for private and academic purposes. In: A. Kononov et al. (eds.): DOOR 2016, Vladivostok, Russia, published at http://ceur-ws.org Explicit Global Optimization 219 particular explicit function [2]. Methods of Lipschitz optimization ([3]–[9]) are reasonably easily and quickly coded. This is their indubitable advantage. The drawback is that every operation worsens the estimate of the true Lipschitz constant, immediately affecting the efficiency. In addi- tion, the Lipschitz constant equally estimates the rate of change of the objective all over the segment, so, this constant is defined by segments of the fastest variation, which generally may contain no points of global minimum. To the contrary, the func- tion may change more smoothly near points of global minimum. One of the ways out is to estimate Lipschitz constant according to the search region [10]. Also, some methods estimate Lipschitz constant on the basis of previously calculated values of the objec- tive [11]. In this case, overestimation of Lipschitz constant and loss of the true global optimum may be a problem. Global search is much more efficient if the objective is known to be differentiable and its derivative is known to satisfy the Lipschitz condition ([12]–[17]). Effective algorithms for global minimization of one-dimensional functions over a segment are presented in [18], [19], [14]. Obviously, for this class of functions the operations of taking maximum and minimum of two functions have to be excluded, because they do not retain the differentiability of the objective. Another successfully developing field of global optimization is so called d.c. pro- gramming [20]–[22]. A d.c. function is a function representable as a difference of two convex continuous functions. A d.c. program is a problem of minimization of a d.c. function subject to equality and inequality constraints defined also by d.c. functions. Not considering in detail a wide variety of methods for solving d.c. problems, we only notice that finding a good representation (if it exists) of a given function in the form of a difference of two convex function may appear to be a quite complicated problem. For global minimization of a univariate explicit function, we present a method of piecewise linear support functions [23], [24] which is a generalization of well-known Piyavskii’s method [25]. It should be also noted the the proposed method belongs to the class of characteristical algorithms [26] and can be easily parallelized. The optimization technique suggested in the paper differs from interval analysis approach used in global optimization [27] and is closely related to automatic differenti- ation [28], however not so much developed. In general, the approach of the paper can be considered as an initial extension of automatic differentiation to global optimization. 2 The problem and Piecewise linear support functions We consider the global optimization problem f (x) → min, x ∈ [α, β], (1.1) where α, β ∈ R, α ≤ β and function f (x) satisfies the following definition. Definition 1.1. A function f (x) is said to have a convex support function-majorant and concave support function-minorant if there exist functions φ+ (x, y) and φ− (x, y) such that 1. φ+ (x, y) is convex and continuous with respect to x at any fixed y ∈ [α, β]; 2. φ− (x, y) is concave and continuous with respect to x at any fixed y ∈ [α, β]; 220 Oleg Khamisov 3. φ− (x, y) ≤ f (x) ≤ φ+ (x, y) for any x, y ∈ [α, β]; 4. φ− (y, y) = f (y) = φ+ (y, y) for any y ∈ [α, β]. The functions φ+ (x, y) and φ− (x, y) are called support function-majorant and support function-minorant, correspondingly . Any function satisfying Definition 1.1 is lower semicontinuous [24]. It is easy to see that any locally Lipschitz function satisfies this definition. In this paper we propose to construct φ+ (x, y) and φ− (x, y) as piecewise linear functions. Definition 2.1. A convex piecewise linear support function-majorant of a function f (x) and a concave piecewise linear support function-minorant of function f (x) over a segment [α, β] at a support point y will denote such functions φ+ (x, y) and φ− (x, y) that satisfy Definition 1.1 and have the form { } φ+ (x, y) = max k1+ (y)x + b+ + + 1 (y), k2 (y)x + b2 (y) , (2.1) { } φ− (x, y) = min k1− (y)x + b− − − 1 (y), k2 (y)x + b2 (y) (2.2) − − − − where k1+ (y), b+ + + 1 (y), k2 (y), b2 (y), k1 (y), b1 (y), k2 (y), and b2 (y) are certain numbers. Constructing the piecewise linear support functions for linear and convex functions is obvious, so we consider here one of the most trouble in global optimization function f (x) = sin(x) and analyze the following four special cases. I. Point y ∈ [− π2 , 0]. The function sin(x) is convex over the segment [− π2 , y], hence sin(x) ≥ sin(y)+cos(y)(x−y), x ∈ [− π2 , y] and, consequently, k1− = cos(y), b− 1 = sin(y)− k1− y. Over the segment [0, 23 π], the graph of the function sin(x) lies above the tangent line through the origin. The value v1 = 4.493409458 is found from the transcendental equation sin(v)−cos(v)v = 0. Next, from the linear equation sin(v1 )+cos(v1 )(z −v1 ) = −1 with respect to z the solution z1 = 4.603338848 is obtained. Then, over the segment [y, 23 π], the graph of the function sin(x) lies above the straight line through the points (y, sin(y)) and (z1 , −1): sin(x) ≥ k2− x+b− − sin(y)+1 − 2 , x ∈ [y, 2 π], k2 = y−z1 , b2 = sin(y)−k2 y. 3 − II. Point y ∈ [0, π2 ]. Over the segment [− π2 , y], the graph of the function sin(x) lies above the straight line through the points (−1, 1) and (y, sin(y)): sin(x) ≥ k1− x+b− 1 ,x ∈ [− π2 , y], k1− = sin(y)+1 y+1 , b − 1 = sin(y) − k − 1 y. Over the segment [ π 3 , 2 2 π], the graph of π the function sin(x) pases above the tangent line through the point ( 2 , 1). The value v2 = 3.901918697 is a solution of the transcendent equation sin(v) + cos(v)( π2 − v) = 1 belonging to the segment [ π2 , 32 π]. Find the value z2 = 4.330896607 as a solution of the linear equation sin(v2 ) + cos(v2 )(z − v2 ) = −1 with respect to z. It is easy to see that, over the segment [y, 23 π], the graph of the function sin(x) is located above the straight line through the points (y, sin(y)) and (−1, 1): sin(x) ≥ k2− x + b− 2 , x ∈ [y, 2 π], 3 k2− = y−z2 , b− sin(y)+1 2 = sin(y) − k2 y. − III. Point y ∈ [ 2 , π]. Over the segment [− π2 , π2 ] , the graph of the function sin(x) π lies above the tangent line through the point ( π2 , 1). The value v3 = −0.7603260437 is a solution of the transcendent equation sin(v) + cos(v)( π2 − v) = 1 belonging to the segment [− π2 , π2 ]. The value z3 = −1.189303953 is obtained as a solution of the linear equation sin(v3 ) + cos(v3 )(z − v3 ) = −1 with respect to z. It is easy to see that, over the segment [ π2 , y], the graph of the function sin(x) is located above the straight line through (z3 , −1) and (y, sin(y)): sin(x) ≥ k1− x + b− − 1 , x ∈ [− 2 , y], k1 = π sin(y)+1 − y−z3 , b1 = Explicit Global Optimization 221 sin(y) − k1− y. Next, over the segment [y, 32 π], the graph of the function sin(x) lies over the straight line through the points (y, sin(y)) and (π + 1, −1): sin(x) ≥ k2− x + b− 2 ,x ∈ − sin(y)+1 − − [y, 2 π], k2 = y−π−1 , b2 = sin(y) − k2 y. 3 IV. A support point y ∈ [π, 23 π]. Over the segment [− π2 , π], the graph of the function lies above the tangent line through the point (π, 0). The value v4 = −1.351816804 is a solution of the transcendental equation sin(v) + cos(v)(π − v) = 0 belonging to the segment [− π2 , 0]. Again, the value z4 = −1.461746193 is obtained as a solution of the linear equation sin(v4 ) + cos(v4 )(z − v4 ) = −1. with respect to z. Over the segment [− π2 , y], the graph of the function sin(x) is located above the straight line through the points (z4 , −1) and (y, sin(y)): sin(x) ≥ k1− x + b− − 1 , x ∈ [− 2 , y], k1 = π sin(y)+1 − − y−z4 , b1 = sin(y) − k1 y. Over the segment [y, 2 π], the function sin(x) is convex 3 therefore k2− = cos(y), b− − 2 = sin(y) − k2 y. To summarize, the rule for constructing a concave piecewise linear minorant of the function sin(x) over the segment [− π2 , 32 π] is the following. Input: the function f (x) = sin(x) and a point y. Step 1. If − π2 ≤ y ≤ 0, then k1− = cos(y), k2− = sin(y)+1 y−z1 . If 0 ≤ y ≤ π2 , then k1− = sin(y)+1 − sin(y)+1 y+1 , k2 = y−z2 . If π2 ≤ y ≤ π, then k1− = sin(y)+1 − sin(y)+1 y−z3 , k2 = y−π−1 . − sin(y)+1 − If π ≤ y ≤ 3π 2 , then k1 = y−z4 , k2 = cos(y). Step 2. b− − − − 1 = sin(y) − k1 y, b2 = sin(y) − k2 y. Step 3. Stop. In general, rules for constructing support functions are based on similar geometrical ideas and can be found, for example, in [29]. 3 General rules for constructing piecewise linear support functions Let function f (x) and its support function-majorant φ+ f (x, y) and support function- minorant φ−f (x, y) be given: { } φ+ + + f (x, y) = max kf 1 (y)x + bf 1 (y), kf+2 (y)x + b+f 2 (y) , (3.1) { } φ− − − f (x, y) = min kf 1 (y)x + bf 1 (y), kf−2 (y)x + b− f 2 (y) . (3.2) Denote lf+1 (x, y) = kf+1 (y)x + b+ + + + f 1 (y), lf 2 (x, y) = kf 2 (y)x + bf 2 (y), lf−1 (x, y) = kf−1 (y)x + b− − − − f 1 (y), lf 2 (x, y) = kf 2 (y)x + bf 2 (y). Then − − − φ+ + + f (x, y) = max{lf 1 (x, y), lf 2 (x, y)}, φf (x, y) = min{lf 1 (x, y), lf 2 (x, y)}. 222 Oleg Khamisov − Assume that for another function h(x) its support functions φ+ h (x, y) and φh (x, y) are also known. The goal of this section is to present rules for constructing support functions-minorant and functions-majorant for the functions F1 (x) = cf (x), F2 (x) = f (x) + h(x), F3 (x) = f (x) − h(x), F4 (x) = f 2 (x), 1 F5 (x) = f (x) · h(x), F6 (x) = , F7 (x) = max{f (x), h(x)}, f (x) F8 (x) = min{f (x), h(x)}, F9 (x) = f (h(x)) where c is a constant. 3.1. The function F1 (x) = cf (x). It is obvious that { + max{c · l1+ (x, y), c · l2+ (x, y)}, c≥0 φF1 (x, y) = max{c · l1− (x, y), c · l2− (x, y)}, c < 0, { min{c · l1− (x, y), c · l2− (x, y)}, c≥0 φ− F1 (x, y) = min{c · l1+ (x, y), c · l2+ (x, y)}, c < 0. 3.2. The function F2 (x) = f (x) + h(x). In this case φ+ + + + + F2 (x, y) = max{lf 1 (x, y) + lh1 (x, y), lf 2 (x, y) + lh2 (x, y)}, φ− − − F2 (x, y) = min{lf 1 (x, y) + lh1 (x, y), lf−2 (x, y) + lh2 − (x, y)}. 3.3. The function F3 (x) = f (x) − h(x). Obviously follows from 3.1 and 3.2. 3.4. The function F4 (x) = f 2 (x). From (f (x) − f (y))2 ≥ 0 we have f 2 (x) ≥ 2f (x)f (y) − f 2 (y). For obtaining φ− F4 (x, y) the rule from 3.1 is used with c = 2f (y). Find constants f and f such that f ≤ f (x) ≤ f ∀x ∈ X. Calculate ẑ = f (y). Suppose that f < ẑ < f . Then z 2 ≤ (f + ẑ)z − f ẑ, z ∈ [f , ẑ], z 2 ≤ (f + ẑ)z − f ẑ, z ∈ [ẑ, f ]. { } Consequently, z 2 ≤ max (f + ẑ)z − f ẑ, (f + ẑ)z − f ẑ , z ∈ [f , f ]. After the substi- tution z = f (x), ẑ = f (y), we obtain f 2 (x) ≤ max{(f + f (y))f (x) − f f (y), (f + f (y))f (x) − f f (y)}. Then use support convex majorants for the functions (f + f (y))f (x) − f f (y) and (f + f (y))f (x) − f f (y). 2 2 2 3.5. The function F5 (x) = f (x) · h(x). Since f (x) · h(x) = (f (x)+h(x)) 2 − f 2(x) − h 2(x) , support functions for F5 (x) can be constructed by subsequent application of the rules from 3.1-3.4. 3.6. The function F6 (x) = f (x) 1 . It is assumed that f (x) > 0 ∀x ∈ [α, β]. The func- tion F6 (x) is a composition of the functions φ(z) = z1 and f (x). Let 0 < f < f (x) < f ∀x ∈ [α, β] and denote ẑ = f (y). The function φ(z) is convex over the segment [f , f ]. Therefore F (x) = φ(f (x)) ≥ f (y) 1 − ff2(x) (y) . A concave minorant of the function Explicit Global Optimization 223 − ff2(x) (y) is constructed by the rule presented in 3.1 with c = − f 2 (y) . A convex majorant 1 is constructed in the same way as in 3.4, with the auxiliary function z 2 substituted by the function z1 . It is easy to see now that construction of support majorants and minorants of a concave function f (x) consists in construction of support majorants and minorants of the convex function −f (x), multiplying them by −1 and applying the rule from 3.1.√In this way support majorants and minorants for the elementary functions f6 (x) = x and f7 (x) = ln(x) are constructed. 3.7. The function F7 (x) = max{f (x), h(x)}. Without loss of generality, let us as- sume that max{f (y), h(y)} = f (y). Then F7 (x) ≥ f (x) ≥ φ− f (x, y), what means that φ−f (x, y) is a concave minorant of the function F 7 (x). On the other hand, F7 (x) ≤ + + + + max{φf (x, y), φh (x, y)}. Since the functions φf (x, y) and φh (x, y) are convex in x, the function ψ(x) = max{φ+ + f (x, y), φh (x, y)} is also convex in x. Constructing a sup- port majorant of the function ψ(x) we simultaneously obtain a support piecewise linear majorant for the function F7 (x). 3.8. The function F8 (x) = min{f (x), h(x)}. Since min{f (x), h(x)} = − max{−f (x), −h(x)}, support functions can be found by application of the rules from 3.1 and 3.7. 3.9. The function F9 (x) = f (h(x)). From (3.1) and (3.2) we have { } F7 (x) ≤ φ+ f (h(x), h(y)) = max k + f1 (h(y))h(x) + b+ f1 (h(y)), k + f2 (h(y))h(x) + b+ f2 (h(y)) , { (3.7) } F7 (x) ≥ φ− − − − − f (h(x), h(y)) = min kf 1 (h(y))h(x) + bf 1 (h(y)), kf 2 (h(y))h(x) + bf 2 (h(y)) . (3.8) The right-hand expressions of inequalities (3.7) and (3.8) are piece-wise linear with respect to the function h(x). Application of the rules presented in 3.7, 3.8, 3.1, and 3.2 suffices to construct support majorants and minorants. The above-introduced rules for constructing support piecewise linear functions are applicable to any explicit function. The process of construction of a support functions is analogous in some way to the process of differentiation of a function: both can be automatized. Hence, the quite scrupulous procedure of finding support functions can be entrusted to a computer. The analytical representations of required functions are not always necessary, it is sufficient to have only algorithms of finding their values at any feasible point. That is the reason that a user needs nothing to do but explicitly set an objective, everything else can be automatized according to the above-described rules. 4 A Modification of Piyavskii’s Method The method of solving problem (1.1) proposed in this paper is a modification of the well-known Piyavskii’s method [25]. Given points x1 , ..., xk , determine next point xk+1 as a global solution of the problem ψk (x) = max {φ− (x, xi )} → min, x ∈ [α, β]. (4.1) 1≤i≤k 224 Oleg Khamisov After that, calculate the record fk+1 = min{f (xi ) : i = 1, ..., k + 1}, and if fk+1 − ψ(xk+1 ) ≤ ε where ε > 0 is a required precision then the point xl , l = 1, ..., k + 1 such that f (xl ) = fk is the ε-optimal solution. A starting point x1 ∈ [α, β] is arbitrary. If the functions ψk (x) are uniformly bounded every limit point of sequence xk is a global solution of problem (1.1) ([25]). At the k-th iteration of the method the points x1 , ..., xk divide the segment [α, β] into p subsegments [αj , β j ], j = 1, ..., p such that α1 = α, β p = β, β j = αj+1 . Next point xk+1 belongs to one of these subsegments, hence it is sufficient to build support functions only over the subsegment containing xk+1 . Such a strengthening of Piyavskii’s method has been already used in Lipschitz optimization [10]. Another strengthening lies in the fact that a support function depends on the support point providing more accurate piecewise linear approximation of the objective over a segment, in contrast to [10] where approximation accuracy is determined by the Lipschitz constant (though over a smaller segment). The rules for constructing support functions presented in the previous section are aimed to improvement of accuracy of piecewise linear approxima- tion through shortening the current subsegment. Computational experiment performed in [29] shows acceleration in convergence from 3 to 10 times in comparison to results presented in [4]. References 1. McCormick, G.P.: Computability of global solutions to factorable nonconvex programs. Part I - Convex underestimating problems. Mathematical Programming 10, 147-175 (1976). 2. Sukharev, A.G. Minimax Models in the Theory of Numerical Methods. Springer Science & Business Media, 258 p. (2012) 3. Evtushenko, Yu.: Numerical methods for finding global extreme (case of a non-uniform mesh). USSR Comput. Maths. Math. Phys. 11(6), 38-54 (1971) 4. Hansen, P., Jaumard, B.: Lipschitz optimization. In: Handbook of global optimization, pp.407-494. Kluwer Acad. Publ., Dordrecht (1995) 5. Pinter J.: Global Optimization in Action. Kluwer Acad. Publ., Dordrecht (1996) 6. Evtushenko Yu. G., Posypkin M. A.: Nonuniform covering method as applied to multicri- teria optimization problems with guaranteed accuracy. Computational Mathematics and Mathematical Physics Volume 53, Issue 2, pp 144-157 (2013) 7. Evtushenko Yu. G., Malkova V.U., Stanevichyus A.A.: Parallel global optimization of functions of several variables. Computational Mathematics and Mathematical Physics Volume 49, Issue 2, pp 246-260 (2009) 8. Strongin R. G., Sergeyev Ya. D.: Global optimization with non-convex constraints: Se- quential and parallel algorithms, Kluwer Academic Publishers, Dordrecht, 728 pp. (2000) 9. Sergeyev Ya. D., Strongin R. G., Lera D.: Introduction to Global Optimization Exploiting Space-Filling Curves, Springer, New York, 135 pp. (2013) 10. Sergeev Ya.D.: An one-dimensional determenistic global optimization algorithm. Comput. Maths. Math. Phys. 35, 705-717 (1995) 11. Wood G.R., Zhang B.P.: Estimation of the Lipschitz constant of a function. Journal of Global Optimization 8, 91-103 (1996) 12. Baritompa, W.: Accelerations for a variety of global optimization methods. Journal of Global Optimization 4, 37-45 (1994) Explicit Global Optimization 225 13. Breiman, L., Cutler, A.: A deterministic algorithm for global optimization. Mathematical Programming 58, 179-199 (1993) 14. Sergeyev Ya. D.: Global one-dimensional optimization using smooth auxiliary functions. Mathematical Programming 81(1), 127-146 (1998). 15. Kvasov D.E., Sergeyev Ya. D.: A univariate global search working with a set of Lipschitz constants for the first derivative. Optimization Letters 3(2), 303-318 (2009). 16. Kvasov D.E., Sergeyev Ya. D.: Univariate geometric Lipschitz global optimization algo- rithms. Numerical Algebra, Control and Optimization 2(1), 69-90 (2012). 17. Sergeyev Ya. D., Mukhametzhanov M.S., Kvasov D.E., Lera D.: Derivative-Free Local Tuning and Local Improvement Techniques Embedded in the Univariate Global Opti- mization. DOI: 10.1007/s10957-016-0947-5 (2016) 18. Gergel, V.P.: A global optimization algorithm with derivatives. In: Dinamika sistem i op- timizatsiya (System Dynamics and Optimization), pp.161-178. State University of Nizhni Novgorod, Nizhni Novgorod (1992) (in Russian) 19. Gergel, V.P.: A global optimization algorithm for multivariate functions with Lipschitzian first derivatives. Journal of Global Optimization 10, 257-281 (1997) 20. Tuy H.: D.C. optimization: theory, methods and algorithms. In: Handbook of global op- timization, pp.149-216. Kluwer Acad. Publ., Dordrecht (1995) 21. Horst, R., Tuy, H.: Global optimization. Deterministic approaches. Springer-Verlag, Berlin (1996) 22. Strekalovsky A.S.: On the Minimization of the Difference of Convex Functions on a Fea- sible Set. Comp. Math. And Math. Physics, 43(3) pp. 380-390 (2003) 23. Khamisov, O.V.: On optimization properties of functions with a concave minorant. Journal of Global Optimization 14, 79-101 (1999) 24. Khamisov, O.V.: Global optimization of functions with a concave support minorant. Com- put. Maths. Math. Phys. 44(9), 1473-1483 (2004) 25. Piyavskii, S.A.: An algorithm for finding the absolute extremum of a function. USSR Comput. Math. Math. Phys. 12, 57-67 (1972). 26. Grishagin, V.A., Sergeyev, Y.D., Strongin, R.G.: Parallel Characteristical Algorithms for Solving Problems of Global Optimization. Journal of Global Optimization, 10(2), 185-206 (1997) 27. Hansen, E., Walster, G.: Global optimization using interval analysis. Second edition, re- vised and expanded. Marcel Dekker, New York, 489 pp. (2004) 28. Griewank, A., Walther, A.: Evaluating Derivatives: Principles and Techniques of Algo- rithmic Differentiation. Other Titles in Applied Mathematics 105, 426 pp. (2008) 29. Khamisov O.V., Yershov A.R.: Automatic global optimization. Discrete Analysis and Operations Research, Ser. 2, 11(2), 45-68 (in Russian) (2004)