Explicit Univariate Global Optimization with Piecewise Linear Support Functions

Abstract

Piecewise linear convex and concave support functions combined with Pijavskii's method are proposed to be used for solving global optimization problems. Rules for constructing support functions are introduced.

Keywords

• global minimum
• support functions
• piecewise concave and convex functions

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 explicit 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 nding 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 ] explicit 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 de ne 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 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 addition, the Lipschitz constant equally estimates the rate of change of the objective all over the segment, so, this constant is de ned by segments of the fastest variation, which generally may contain no points of global minimum. To the contrary, the function 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 objective [ 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 eld of global optimization is so called d.c. programming [ 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 de ned also by d.c. functions. Not considering in detail a wide variety of methods for solving d.c. problems, we only notice that nding 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 differentiation [ 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 2 [ ; ]; (1:1) where ; 2 R; and function f (x) satis es the following de nition.

De nition 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 xed y 2 [ ; ]; 2. φ (x; y) is concave and continuous with respect to x at any xed y 2 [ ; ]; 3. φ (x; y) f (x) φ+(x; y) for any x; y 2 [ ; ]; 4. φ (y; y) = f (y) = φ+(y; y) for any y 2 [ ; ].

The functions φ+(x; y) and φ (x; y) are called support function-majorant and support function-minorant, correspondingly .

Any function satisfying De nition 1.1 is lower semicontinuous [ 24 ]. It is easy to see that any locally Lipschitz function satis es this de nition. In this paper we propose to construct φ+(x; y) and φ (x; y) as piecewise linear functions.

De nition 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 De nition 1.1 and have the form φ+(x; y) = max {k1+(y)x + b1+(y); k2+(y)x + b2+(y)}; φ (x; y) = min {k1 (y)x + b1 (y); k2 (y)x + b2 (y)} (2:1) (2:2) where k1+(y), b1+(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 [ 2 ; 0]. The function sin(x) is convex over the segment [ 2 ; y], hence sin(x) sin(y)+cos(y)(x y); x 2 [ 2 ; y] and, consequently, k1 = cos(y); b1 = sin(y) k1 y: Over the segment [0; 32 ], 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; 32 ], 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+b2 ; x 2 [y; 32 ]; k2 = siny(yz)+11 ; b2 = sin(y) k2 y:

II. Point y 2 [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+b1 ; x 2 [ 2 ; y]; k1 = siny(+y)1+1 ; b1 = sin(y) k1 y: Over the segment [ 2 ; 23 ], 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 ; 23 ]. 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; 32 ], 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 + b2 ; x 2 [y; 23 ]; k2 = siny(yz)+21 ; b2 = sin(y)

k2 y:

III. Point y 2 [ 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 + b1 ; x 2 [ 2 ; y]; k1 = siny(yz)+31 ; b1 = 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 + b2 ; x 2 [y; 23 ]; k2 = syin(y)+11 ; b2 = sin(y)

k2 y:

IV. A support point y 2 [ ; 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 + b1 ; x 2 [ 2 ; y]; k1 = siny(yz)+41 ; b1 = sin(y) k1 y: Over the segment [y; 32 ], the function sin(x) is convex therefore k2 = cos(y); b2 = 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 y If 0 If 2 2 y y 0, then k1 = cos(y); k2 = sin(yz)+11 .

y 2 , then k1 = sin(y)+1 ; k2 = sin(yz)+21 .

y+1 y , then k1 = sin(yz)+31 ; k2 = syin(y)+1 .

y 1 32 , then k1 = siny(yz)+41 ; k2 = cos(y).

If y Step 2. b1 = 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 functionminorant φf (x; y) be given: φf+(x; y) = max {kf+1(y)x + bf+1(y);

kf+2(y)x + bf+2(y)} ; φf (x; y) = min {kf1(y)x + bf1(y); kf2(y)x + bf2(y)} : (3:1) (3:2)

Denote

Then

lf+1(x; y) = kf+1(y)x + bf+1(y); lf+2(x; y) = kf+2(y)x + bf+2(y); lf1(x; y) = kf1(y)x + bf1(y); lf2(x; y) = kf2(y)x + bf2(y): φf+(x; y) = maxflf+1(x; y); lf+2(x; y)g; φf (x; y) = minflf1(x; y); lf2(x; y)g: 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 f (x) F5(x) = f (x) h(x); F6(x) =

; F7(x) = maxff (x); h(x)g;

F8(x) = minff (x); h(x)g; F9(x) = f (h(x)) where c is a constant. 3.1. The function F1(x) = cf (x). It is obvious that φF+1 (x; y) = φF1 (x; y) = { maxfc l1+(x; y); c l2+(x; y)g; c 0

maxfc l1 (x; y); c l2 (x; y)g; c < 0; { minfc l1 (x; y); c l2 (x; y)g; c 0

minfc l1+(x; y); c l2+(x; y)g; c < 0: 3.2. The function F2(x) = f (x) + h(x). In this case φF+2 (x; y) = maxflf+1(x; y) + lh+1(x; y); lf+2(x; y) + lh+2(x; y)g; φF2 (x; y) = minflf1(x; y) + lh1(x; y); lf2(x; y) + lh2(x; y)g: 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 8x 2 X. Calculate z^ = f (y). Suppose that f < z^ < f . Then z2 (f + z^)z f z^; z 2 [f ; z^]; z2 (f + z^)z f z^; z 2 [z^; f ]: Consequently, z2 max {(f + z^)z tution z = f (x), z^ = f (y), we obtain f z^; (f + z^)z

f z^}; z 2 [f ; f ]. After the substif 2(x)

maxf(f + f (y))f (x) f f (y); (f + f (y))f (x) f f (y)g: 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). 3.5. The function F5(x) = f (x) h(x). Since f (x) h(x) = (f(x)+2h(x))2 f22(x) h22(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(1x) . It is assumed that f (x) > 0 8x 2 [ ; ]. The function F6(x) is a composition of the functions φ(z) = z1 and f (x). Let 0 < f < f (x) < f 8x 2 [ ; ] and denote z^ = f (y): The function φ(z) is convex over the segment [f ; f ]. Therefore F (x) = φ(f (x)) f(1y) ff2((xy)) : A concave minorant of the function ff2((xy)) is constructed by the rule presented in 3.1 with c = f21(y) . A convex majorant is constructed in the same way as in 3.4, with the auxiliary function z2 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) = px and f7(x) = ln(x) are constructed. 3.7. The function F7(x) = maxff (x); h(x)g. Without loss of generality, let us assume that maxff (y); h(y)g = f (y). Then F7(x) f (x) φf (x; y); what means that φf (x; y) is a concave minorant of the function F7(x). On the other hand, F7(x) maxfφf+(x; y); φh+(x; y)g: Since the functions φf+(x; y) and φh+(x; y) are convex in x, the function (x) = maxfφf+(x; y); φh+(x; y)g is also convex in x. Constructing a support majorant of the function (x) we simultaneously obtain a support piecewise linear majorant for the function F7(x). 3.8. The function F8(x) = minff (x); h(x)g.

Since minff (x); h(x)g = maxf f (x); h(x)g, 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) F7(x) φf+(h(x); h(y)) = max {kf+1(h(y))h(x) + bf+1(h(y)); kf+2(h(y))h(x) + bf+2(h(y))} ; (3:7) φf (h(x); h(y)) = min {kf1(h(y))h(x) + bf1(h(y)); kf2(h(y))h(x) + bf2(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 nding 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 nding 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 Modi cation of Piyavskii's Method

The method of solving problem (1.1) proposed in this paper is a modi cation 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 fφ (x; xi)g ! min; x 2 [ ; ]: 1 i k (4:1) After that, calculate the record fk+1 = minff (xi) : i = 1; :::; k + 1g, 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 2 [ ; ] 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 approximation 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 nding 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 multicriteria 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: Sequential 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 )

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 rst derivative . Optimization Letters 3 ( 2 ), 303 - 318 ( 2009 ).

16. Kvasov D.E. , Sergeyev Ya . D.: Univariate geometric Lipschitz global optimization algorithms . 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 Optimization . DOI: 10.1007/s10957-016-0947-5 ( 2016 )

18. Gergel , V.P.: A global optimization algorithm with derivatives . In: Dinamika sistem i optimizatsiya (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 rst derivatives . Journal of Global Optimization 10 , 257 - 281 ( 1997 )

20. Tuy H.: D.C. optimization: theory, methods and algorithms . In: Handbook of global optimization , 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 Feasible 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 . Comput. Maths. Math. Phys . 44 ( 9 ), 1473 - 1483 ( 2004 )

25. Piyavskii , S.A. : An algorithm for nding 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, revised and expanded. Marcel Dekker , New York, 489 pp. ( 2004 )

28. Griewank , A. , Walther , A. : Evaluating Derivatives: Principles and Techniques of Algorithmic 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 )