Abstract
The performance of interval analysis branch-and-bound global optimization algorithms strongly depends on the efficiency of selection, bounding, elimination, division, and termination rules used in their implementation. All the information obtained during the search process has to be taken into account in order to increase algorithm efficiency, mainly when this information can be obtained and elaborated without additional cost (in comparison with traditional approaches). In this paper a new way to calculate interval analysis support functions for multiextremal univariate functions is presented. The new support functions are based on obtaining the same kind of information used in interval analysis global optimization algorithms. The new support functions enable us to develop more powerful bounding, selection, and rejection criteria and, as a consequence, to significantly accelerate the search. Numerical comparisons made on a wide set of multiextremal test functions have shown that on average the new algorithm works almost two times faster than a traditional interval analysis global optimization method.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Calvin, J. and Žilinskas, A. (1999), On the convergence of the P-algorithm for one-dimensional global optimization of smooth functions. JOTA 102(3), 479-495.
Casado, L. G., García, I. and Sergeyev, Ya. D. (2000), Interval branch and bound algorithm for finding the First-Zero-Crossing-Point in one-dimensional functions. Reliable Computing 2(6), 179-191.
Daponte, P., Grimaldi, D., Molinaro, A. and Sergeyev, Ya. D. (1995), An algorithm for finding the zero crossing of time signals with Lipschitzeans derivatives. Measurements 16, 37-49.
Daponte, P., Grimaldi, D., Molinaro, A. and Sergeyev, Ya. D. (1996), Fast detection of the first zero-crossing in a measurement signal set. Measurements 19(1), 29-39.
Floudas, C. and Pardalos, P. (eds.) (1996), State of the Art in Global Optimization. Computational Methods and Applications, Vol. 7 of Nonconvex Optimization and its Applications. Kluwer Academic Publishers, Dordrecht.
Gergel, V. P. (1999), A global search algorithm using derivatives. In: Systems Dynamics and Optimization. N. Novgorod University Press, Norgood, pp. 161-178.
Hammer, R., Hocks, M., Kulisch, U. and Ratz, D. (1995), C++ Toolbox for Verified Computing I: Basic Numerical Problems: Theory, Algorithms, and Programs. Springer, Berlin.
Hansen, E. (1992), Global Optimization Using Interval Analysis, Vol. 165 of Pure and applied mathematics. Marcel Dekker, New York.
Hansen, E., Jaumard, B., and Lu, S.-H. (1992a), Global optimization of univariate Lipschitz functions: 1. Survey and properties. Math. Programming 55, 252-272.
Hansen, E., Jaumard, B. and Lu, S.-H. (1992b), Global optimization of univariate Lipschitz functions: 2. New algorithms and computational comparison. Math. Programming 55, 273-293.
Horst, R. and Pardalos, P. (eds.) (1995), Handbook of Global Optimization, Vol. 2 of Noncovex optimization and its applications. Kluwer Academic Publishers, Dordrecht.
Kalra, D. and Barr, A. H. (1989), Guaranteed ray intersections with implicit surfaces. Computer Graphics 23(3), 297-306.
Kearfott, R. B. (1996), Rigorous Global Search: Continuous Problems. Kluwer Academic Publishers, Dordrecht.
Lamar, B. (1999), A method for converting a class of univariate functions into d.c. functions’. Journal of Global Optimization 15, 55-71.
Liu, Y. and Teo, K. (1999), A bridging method for global optimization. Journal of Australian Mathematical Society, Series B 41, 41-57.
Locatelli, M. and Schoen, F. (1995), An adaptive stochastic global optimization algorithm for one-dimensional functions. Annals of Operations Research 58, 263-278.
MacLagan, D., Sturge T. and Baritompa, W. (1996), Equivalent methods for global optimization. In: Floudas, C. and Pardalos, P. (eds.) State of the Art in Global Optimization. Computational Methods and Applications, Kluwer Academic Publications, Dordrecht, pp. 201-212.
Mladineo, R. (1992), Convergence rates of a global optimization algorithm. Math. Programming 54, 223-232.
Moore, R. (1966), Interval analysis. Prentice-Hall, Englewood Cliffs, NJ.
Neumaier, A. (1990), Interval Methods for Systems of Equations. Cambridge University Press, Cambridge.
Pijavskii, S. A. (1972), An algorithm for finding the absolute extremum of a function’. USSR Maths. Math. Physics 12, 57-67.
Pintér, J. D. (1996), Global Optimization in Action, Vol. 6 of Noncovex Optimization and its Applications. Kluwer Academic Publishers, Dordrecht.
Ratschek, H. and Rokne, J. (1988), New Computer Methods for Global Optimization. Ellis Horwood Ltd., Chichester.
Ratz, D. (1998), Automatic Slope Computation and its Application in Nonsmooth Global Optimization. Shaker Verlag, Aachen.
Ratz, D. (1999), A nonsmooth global optimization technique using slopes: the one-dimensional case. Journal of Global Optimization 14(4), 365-393.
Sergeyev, Ya. D. (1995), A one-dimensional deterministic global minimization algorithm. Comput. Maths. Math. Phys 35(5), 705-717.
Sergeyev, Ya. D. (1998), Global one-dimensional optimization using smooth auxiliary functions’. Mathematical Programming 81(1), 127-146.
Sergeyev, Ya. D. (2000), Efficient strategy for adaptive partition of N-dimensional intervals in the framework of diagonal algorithms. Journal of Optimization Theory and Applications 107(1), 145-168.
Sergeyev, Ya. D., Daponte, P., Grimaldi, D. and Molinaro, A. (1999), Two methods for solving optimization problems arising in electronic measurement and electrical engineering. SIAM Journal on Optimization 10(1), 1-21.
Strongin, R. G. (1978), Numerical Methods on Multiextremal Problems. Nauka, Moscow.
Strongin, R. G. and Sergeyev, Ya. D. (2000), Global optimization with non-convex constraints: Sequential and parallel algorithms. Kluwer Academic Publishers, Dordrecht.
Wang, X. and Chang, T. (1996), An improved univariate global optimization algorithm with improved linear bounding functions. Journal of Global Optimization pp. 393-411.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Casado, L., MartÍnez, J., GarcÍa, I. et al. New Interval Analysis Support Functions Using Gradient Information in a Global Minimization Algorithm. Journal of Global Optimization 25, 345–362 (2003). https://doi.org/10.1023/A:1022512411995
Issue Date:
DOI: https://doi.org/10.1023/A:1022512411995