1996 | OriginalPaper | Buchkapitel
Accelerating Convergence of Branch-and-Bound Algorithms For Quadratically Constrained Optimization Problems
verfasst von : Tim Van Voorhis, Faiz Al-Khayyal
Erschienen in: State of the Art in Global Optimization
Verlag: Springer US
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We consider methods for finding global solutions to quadratically constrained programs. We present a branch-and-bound algorithm which solves a sequence of linear programs, each of which approximates the original problem over a hyperrectangular region. Tightening the bounds produces arbitrarily tight approximations as the volume of the hyperrectangle decreases. Computational experiments are given which relate the efficiency of the algorithm to the input parameters. In order to reduce the amount of work necessary to isolate global solutions within a small region, local optimization techniques are embedded within the branch-and-bound scheme. In particular, the use of the interval Newton method applied to the KKT system is discussed and shown to be computationally beneficial. Extensions are considered which allow the branch-and- bound algorithm to process more general nonlinear functions than quadratic.