Abstract
In this paper the kite inclusion function is presented for branch-and-bound type interval global optimization using at least gradient information. The basic idea comes from the simultaneous usage of the centered forms and the linear boundary value forms. We will show that the new technique is not worse and usually considerably better than these two. The best choice for the center of the kite inclusion will be given. The isotonicity and at least quadratical convergence hold and there is a pruning effect of the kite which is derived from the construction of the inclusion, thus more function evaluations are not needed to use it. A numerical investigation on large standard multiextremal test functions has been done to show the performance.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Alefeld, G. and Herzberger, J. (1983), Introduction to Interval Computations, Academic Press, New York.
Baumann, E. (1988), Optimal centered forms, BIT, 28(1), 80–87.
Casado, L.G., García, I., Martínez, J.A. and Sergeyev, Ya.D. (2003), New interval analysis support functions using gradient information in a global minimization algorithm, J. Global Optimization, 25(4), 345–362.
Csallner, A.E., Csendes, T. and Markót, M.Cs. (2000), Multisection in interval branch-and-bound methods for global optimization - I. Theoretical results, J. Global Optimization, 16(4), 371–392.
Csendes, T. (2001), New subinterval selection criteria for interval global optimization, J. Global Optimization, 19(3), 307–327.
Csendes, T. and Ratz, D. (1997), Subdivision direction selection in interval methods for global optimization, SIAM J. Numerical Anal., 34(3), 922–938.
Hammer, R., Hocks, M., Kulisch, U. and Ratz, D. (1995), C++ Toolbox for Verified Computing I: Basic Numerical Problems: Theory, Algorithms, and Programs, Springer-Verlag, Berlin.
Hansen, E.R. (1992), Global Optimization Using Interval Analysis, Marcel Dekker, New York.
Kearfott, R.B. (1996), Rigorous Global Search: Continuous Problems, Kluwer, Boston.
Klatte, R., Kulisch, U., Wiethoff, A., Lawo, C. and Rauch, M. (1993), C-XSC; A C++ Class Library for Extended Scientific Computing, Springer-Verlag, New York.
Krawczyk R. and Nickel, K. (1982), The centered form in interval arithmetics:Quadratic convergence and inclusion isotonicity, Computing, 28(2), 117–137.
Lagouanelle, J.-L. (2000), Kite algorithm: A new global interval method from linear evaluations. In: Dietrich, S., Facius, A. and Bierlox, N. (eds.) Abstracts of the SCAN2000 Conference, p. 126. Karlsruhe.
Lagouanelle, J.-L. and Messine, F. (1998), Algorithme d’encadrement de l’optimum global d’une fonction différentiable, C. R. Acad. Sci. Paris Sér. I Math., 326(5), 629–632.
Messine, F. and Lagouanelle, J.-L. (1998), Enclosure methods for multivariate differentiable functions and application to global optimization, J.UCS: J. Universal Comput. Sci., 4(6), 589–603.
Moore, R.E. (1979), Methods and Applications of Interval Analysis, SIAM, Philadelphia.
Moore, R.E. (1996), Interval Analysis, Prentice-Hall, Englewood Cliffs.
Neumaier, A. (1990), Interval Methods for Systems of Equations, Cambridge University Press, Cambridge.
Ratschek, H. and Rokne, J. (1984), Computer Methods for the Range of Functions, Ellis Horwood, Chichester.
Ratschek, H. and Rokne, J. (1988), New Computer Methods for Global Optimization, Ellis Horwood, Chichester.
Ratz, D. (1999), A nonsmooth global optimization technique using slopes—the one dimensional case, J. Global Optimization, 14(4), 365–393.
Sotiropoulos, D.G. and Grapsa, T.N. (2001), A branch-and-prune method for global optimization. In: Kraemer, W. and Gudenberg, J.W.V. (eds). Scientific Computing, Validated Numerics, Interval Methods, Kluwer, Boston, p. 215–226.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Vinkó, T., Lagouanelle, JL. & Csendes, T. A New Inclusion Function for Optimization: Kite – The One Dimensional Case. J Glob Optim 30, 435–456 (2004). https://doi.org/10.1007/s10898-004-8430-5
Issue Date:
DOI: https://doi.org/10.1007/s10898-004-8430-5