New methods for calculating α BB-type underestimators

A1 Originalartikel i en vetenskaplig tidskrift (referentgranskad)


Interna författare/redaktörer


Publikationens författare: Anders Skjäl, Tapio Westerlund
Förläggare: SPRINGER
Publiceringsår: 2014
Tidskrift: Journal of Global Optimization
Tidskriftsakronym: J GLOBAL OPTIM
Volym: 58
Nummer: 3
Artikelns första sida, sidnummer: 411
Artikelns sista sida, sidnummer: 427
Antal sidor: 17
ISSN: 0925-5001
eISSN: 1573-2916


Abstrakt

Most branch-and-bound algorithms in global optimization depend on convex underestimators to calculate lower bounds of a minimization objective function. The BB methodology produces such underestimators for sufficiently smooth functions by analyzing interval Hessian approximations. Several methods to rigorously determine the BB parameters have been proposed, varying in tightness and computational complexity. We present new polynomial-time methods and compare their properties to existing approaches. The new methods are based on classical eigenvalue bounds from linear algebra and a more recent result on interval matrices. We show how parameters can be optimized with respect to the average underestimation error, in addition to the maximum error commonly used in BB methods. Numerical comparisons are made, based on test functions and a set of randomly generated interval Hessians. The paper shows the relative strengths of the methods, and proves exact results where one method dominates another.


Nyckelord

alpha BB, Convex relaxation, Global optimization, Nonconvex optimization

Senast uppdaterad 2019-09-12 vid 03:37