Introduction

This work is devoted to the interval methods of the solution of unconstrained global optimization problem. Use of the interval analysis as a base component of the methods gives some essential advantages. Such methods possess smaller computing complexity (it comes from the fact that methods work not with points but with sets) and they are less exacting to a statement of an initial problem (for example, there is no necessity to demand convexity of minimised function)

Method of dichotomy of direct image

First of all we evaluate the direct image of function on the search area and consider it as a target interval. Further on each iteration of method the target interval is divided by midpoint. Then we apply invertor to the first part. If invertor returns nonempty set, we check the accuracy condition. In case of its failure, the first part is considered as a new target interval and new iteration of the method starts. If the accuracy condition is fulfilled, than the returned by invertor set has box, which contains the global minima of function. If invertor returns empty set, the second part is considered as a new target interval and method begins new iteration.

Method of cutoff of virtual values

Strategy of this method is similar to strategy of the method of dichotomy of direct image. The only difference is in the presence of a stage of tightening of evaluation of direct image, which comes before iterative part of method. After an evaluation of direct image of function on the search area we apply the operator of compression to it, which deletes a part of virtual values from the evaluation. Then method works as a method of dichotomy of direct image. Described stage reduces target interval (if it is possible), which leads to faster convergence.

Method of stochastic cutoff

This method differs from method of cutoff of virtual values by the way its operator of compression works. Method uses stochastic approach concerning that virtual values in evaluation of direct image of function are arranged randomly.

Method of changing directions

Strategy of the given method consists in constant analysis of the best box and storage in memory all potential on rank of the best boxes. For exposition of work of the method it is necessary to introduce concept of the double buffer of memory. We will consider the double buffer of memory as a set of the ordered pairs “box”x”evaluation of a direct image of box”. The box is considered better than other, if it has less lower boundary and width of its evaluation of a direct image. On each iteration the best box (if there are more than one boxes approaching under definition of the “best”, the preference is given to the first), which becomes target box, is selected from the double buffer. Further the target box is divided by its midpoint. Then we evaluate direct images of newly organised boxes and restructure the double buffer. Method works while there is at least one box in double buffer that is not suitable for the accuracy parameters.

Efficiency analysis

Methods were not only theoretically substantiated and have their convergence proved. Besides, they were tested on benchmarks of unconstrained global optimization problems (global minimization of the De Jong’s, Schwefel’s, Rastrigin’s, Griewangk’s, Ackley’s, Langermann’s functions and etc.). All methods found the box which contained the point of global minima or was close enough to it according to accuracy parametres.

Software package

The methods have been implemented in the form of a software package. Programming language - C#, development environment - Microsoft Visual Studio 2010. For today software package has such features as:

• Solution of unconstrained global optimization problems.
• Drawing a contour plot for a function of two variables (for demonstration of a location of found box).
• Making chart of methods efficiency (helps to choose the most suitable method for a class of problems).
• Making graph which demonstrates how fast method converges to the analytic solution for the exact problem.

Conclusion

Thus, this work illustrates how interval analysis can be applied for the solution of unconstrained global optimization problems. The great advantage of these newly created methods is that trey are not heuristic, they are theoretically proved.

References

1. L. Jaulin, M. Kieffer, O. Didrit, E. Walter, Applied interval analysis, Springer-Verlag, London, 2001.
2. R.E. Moore, R.B. Kearfott, M.J. Cloud, Introduction to interval analysis, SIAM, Philadelphia, 2009.
3. S.P. Shary, The finite-dimensional interval analysis, XYZ, 2010.
4. G. Alefeld, J. Herzberger, Introduction to interval computations, New York, Academic Press, 1983.
5. V.N. Panovskiy, Application of the interval analysis for the search of the global extremum of functions, Trudi MAI, 51 (2012).