On lower bounds using additively separable terms in interval B&B

J.L. Berenguel, L.G. Casado, I. García, E.M.T. Hendrix

Research output: Chapter in Book/Report/Conference proceedingConference paperAcademicpeer-review

Abstract

Interval Branch-and-Bound (B&B) algorithms are powerful methods which aim for guaranteed solutions of Global Optimisation problems. Lower bounds for a function in a given interval can be obtained directly with Interval Arithmetic. The use of lower bounds based on Taylor forms show a faster convergence to the minimum with decreasing size of the search interval. Our research focuses on one dimensional functions that can be decomposed into several terms (sub-functions). The question is whether using this characteristic leads to sharper bounds when based on bounds of the sub-functions. This paper deals with functions that are an addition of two sub-functions, also called additively separable functions. The use of the separability is investigated for the so-called Baumann form and Lower Bound Value Form (LBVF). It is proven that using the separability in the LBVF form may lead to a combination of linear minorants that are sharper than the original one. Numerical experiments confirm this improving behaviour and also show that not all separable methods do always provide sharper lower bounds.
Original languageEnglish
Title of host publicationProceedings of the 12th International Conference, 18-21 June 2012, Salvador de Bahia, Brazil, Proceedings Part III
EditorsB. Murgante, G. Osvaldo, S. Misra
Place of PublicationHeidelberg
Pages119-132
DOIs
Publication statusPublished - 2012

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume7335
ISSN (Print)0302-9743

Fingerprint Dive into the research topics of 'On lower bounds using additively separable terms in interval B&B'. Together they form a unique fingerprint.

Cite this