Non-linear Global Optimization Using Interval Arithmetic and Constraint Propagation

AbstractWe consider the problem of finding the global optimum, and the corresponding set of optimal points, of a nonlinear function f over a compact right parallelepiped D parallel to the coordinate axes. A new branch-and-bound type method is described. The method is an extension of the classical interval global optimization method originally given by Moore and Skelboe which iteratively investigates sub-boxes of D using monotonicity tests and interval Newton methods for reducing the set guaranteed to contain all solutions. The extension described uses constraint propagation (CP) in each iteration to further reduce this set, without losing solutions. This is done by applying CP for finding rigorous bounds for the set of stationary points, i.e., enclosing the solutions to the non-linear set of equations f'(x)=0.
KeywordsGlobal optimization, interval analysis, constraint propagation.
TypeBook [Chapter]
EditorsModels and Algorithms for Global Optimization
Year2007    Vol. 4    pp. 45-58
PublisherSpringer Verlag
SeriesSpringer Optimization and Its Applications
ISBN / ISSN13: 978-0-387-36720-0
Electronic version(s)[pdf]
BibTeX data [bibtex]
IMM Group(s)Scientific Computing