TY - JOUR
T1 - Bound constrained interval global optimization in the COCONUT Environment
AU - Markot, Mihaly
AU - Schichl, Hermann
N1 - Publisher Copyright:
© 2014, Springer Science+Business Media New York.
PY - 2014
Y1 - 2014
N2 - We introduce a new interval global optimization method for solving bound constrained problems. The method originates from a small standalone software and is implemented in the COCONUT Environment, a framework designed for the development of complex algorithms, containing numerous state-of-the-art methods in a common software platform. The original algorithm is enhanced by various new methods implemented in COCONUT, regarding both interval function evaluations (such as first and second order derivatives with backward automatic differentiation, slopes, slopes of derivatives, bicentered forms, evaluations on the Karush–John conditions, etc.) and algorithmic elements (inclusion/exclusion boxes, local search, constraint propagation). This resulted in a substantial performance increase as compared to the original code. During the selection of the best combination of options, we performed comparison tests that gave empirical answers to long-lasting algorithmic questions (such as whether to use interval gradients or use slopes instead), that have never been studied numerically in such detail before. The new algorithm, called coco_gop_ex, was tested against the prestigious BARON software on an extensive set of bound constrained problems. We found that in addition to accepting a wider class of bound constrained problems and providing more output information (by locating all global minimizers), coco_gop_ex is competitive with BARON in terms of the solution success rates (with the exception of a set of nonlinear least squares problems), and it often outperforms BARON in running time. In particular, coco_gop_ex was around 21 % faster on average over the set of problems solved by both software systems.
AB - We introduce a new interval global optimization method for solving bound constrained problems. The method originates from a small standalone software and is implemented in the COCONUT Environment, a framework designed for the development of complex algorithms, containing numerous state-of-the-art methods in a common software platform. The original algorithm is enhanced by various new methods implemented in COCONUT, regarding both interval function evaluations (such as first and second order derivatives with backward automatic differentiation, slopes, slopes of derivatives, bicentered forms, evaluations on the Karush–John conditions, etc.) and algorithmic elements (inclusion/exclusion boxes, local search, constraint propagation). This resulted in a substantial performance increase as compared to the original code. During the selection of the best combination of options, we performed comparison tests that gave empirical answers to long-lasting algorithmic questions (such as whether to use interval gradients or use slopes instead), that have never been studied numerically in such detail before. The new algorithm, called coco_gop_ex, was tested against the prestigious BARON software on an extensive set of bound constrained problems. We found that in addition to accepting a wider class of bound constrained problems and providing more output information (by locating all global minimizers), coco_gop_ex is competitive with BARON in terms of the solution success rates (with the exception of a set of nonlinear least squares problems), and it often outperforms BARON in running time. In particular, coco_gop_ex was around 21 % faster on average over the set of problems solved by both software systems.
KW - Bound constrained optimization
KW - Branch-and-bound
KW - Global optimization
KW - Interval arithmetic
UR - http://www.scopus.com/inward/record.url?scp=84920710854&partnerID=8YFLogxK
U2 - 10.1007/s10898-013-0139-x
DO - 10.1007/s10898-013-0139-x
M3 - Article
SN - 0925-5001
VL - 60
SP - 751
EP - 776
JO - Journal of Global Optimization
JF - Journal of Global Optimization
IS - 4
ER -