Abstract
In this paper, we propose modifications to a prototypical branch and bound algorithm for nonlinear optimization so that the algorithm efficiently handles constrained problems with constant bound constraints. The modifications involve treating subregions of the boundary identically to interior regions during the branch and bound process, but using reduced gradients for the interval Newton method. The modifications also involve preconditioners for the interval Gauss-Seidel method which are optimal in the sense that their application selectively gives a coordinate bound of minimum width, a coordinate bound whose left endpoint is as large as possible, or a coordinate bound whose right endpoint is as small as possible. We give experimental results on a selection of problems with different properties.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Alefeld Götz and Jürgen Herzberger (1983), Introduction to Interval Computations, Academic Press, New York.
Conn Andrew R., Nicholas I. M. Gould and Philippe L. Toint (1988), Testing a Class of Methods for Solving Minimization Problems with Simple Bounds on the Variables, Math. Comp. 50 (182), 399–430.
Floudas C. A. and P. M. Pardalos (1990), A Collection of Test Problems for Constrained Global Optimization Algorithms, Springer-Verlag, New York.
Hansen E. (1980), Global Optimization Using Interval Analysis—the Multi-Dimensional Case, Numer. Math. 34 (3), 247–270.
Hansen E. (1988), An Overview of Global Optimization Using Interval Analysis, in Reliability in Computing, Academic Press, New York, pp. 289–308.
Hu, C.-Y. (1990), Preconditioners for Interval Newton Methods, Ph.D. dissertation, University of Southwestern Louisiana.
Kearfott R. B. (1987), Abstract Generalized Bisection and a Cost Bound, Math. Comp. 49 (179), 187–202.
Kearfott R. B. (1990), Interval Newton/Generalized Bisection When There are Singularities near Roots, Annals of Operations Research, 25, 181–196.
Kearfott R. B. (1990), Interval Arithmetic Techniques in the Computational Solution of Nonlinear Systems of Equations: Introduction, Examples, and Comparisons, in Computational Solution of Nonlinear Systems of Equations (Lectures in Applied Mathematics, volume 26), American Mathematical Society, Providence, RI, pp. 337–358.
Kearfott R. B. (1990), Preconditioners for the Interval Gauss-Seidel Method, SIAM J. Numer. Anal. 27 (3), 804–822.
Kearfott R. B., C. Y. Hu and M. Novoa III (1991), A Review of Preconditioners for the Interval Gauss—Seidel Method, Interval Computations 1, (1), 59–85.
Kearfott R.B. and M. Novoa (1990), INTBIS, A Portable Interval Newton/Bisection Package, ACM. Trans. Math. Softwave 16 (2), 152–157.
Levy A. V. and S. Gomez (1984), The Tunneling Method Applied to Global Optimization, in Numerical Optimization 1984, SIAM, Philadelphia, pp. 213–44.
Moore Ramon E. (1979), Methods and Applications of Interval Analysis, SIAM, Philadelphia.
Neumaier A. (1990), Interval Methods for Systems of Equations, Cambridge University Press, Cambridge, England.
Novoa, M., Linear Programming Preconditioners for the Interval Gauss-Seidel Method and their Implementation in Generalized Bisection, Ph.D. dissertation, University of Southwestern Louisiana, to appear.
Pardalos P. M. and J. B. Rosen (1987), Constrained Global Optimization: Algorithms and Applications, Springer-Verlag, New York.
Ratschek H. (1985), Inclusion Functions and Global Optimization, Math. Programming 33 (3), 300–317.
Ratschek H. and J. G. Rokne (1987), Efficiency of a Global Optimization Algorithm, SIAM J. Numer. Anal. 24 (5), 1191–1201.
Ratschek H. and J. Rokne (1987), New Computer Methods for Global Optimization, Wiley, New York.
Walster, G. W., E. R. Hansen and S. Sengupta (1985), Test Results for a Global Optimization Algorithm, in Numerical Optimization 1984, SIAM, pp. 272–287.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Kearfott, R.B. An interval branch and bound algorithm for bound constrained optimization problems. J Glob Optim 2, 259–280 (1992). https://doi.org/10.1007/BF00171829
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF00171829