Convergence analysis of Taylor models and McCormick-Taylor models
File(s)
Accepted version
Author(s)
Bompadre, A
Mitsos, A
Chachuat, B
Type
Journal Article
Abstract
This article presents an analysis of the convergence order of Taylor models and McCormick-Taylor models, namely Taylor models with McCormick relaxations as the remainder bounder, for factorable functions. Building upon the analysis of McCormick relaxations by Bompadre and Mitsos (J Glob Optim 52(1):1–28, 2012), convergence bounds are established for the addition, multiplication and composition operations. It is proved that the convergence orders of both qth-order Taylor models and qth-order McCormick-Taylor models are at least q + 1, under relatively mild assumptions. Moreover, it is verified through simple numerical examples that these bounds are sharp. A consequence of this analysis is that, unlike McCormick relaxations over natural interval extensions, McCormick-Taylor models do not result in increased order of convergence over Taylor models in general. As demonstrated by the numerical case studies however, McCormick-Taylor models can provide tighter bounds or even result in a higher convergence rate.
Date Issued
2012-10-25
Date Acceptance
2012-10-12
Citation
Journal of Global Optimization, 2012, 57 (1), pp.75-114
ISSN
1573-2916
Publisher
Springer Verlag (Germany)
Start Page
75
End Page
114
Journal / Book Title
Journal of Global Optimization
Volume
57
Issue
1
Copyright Statement
© Springer Science+Business Media New York 2012. The final publication is available at Springer via http://dx.doi.org/10.1007/s10898-012-9998-9
Sponsor
Engineering & Physical Science Research Council (EPSRC)
Identifier
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000323741700004&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=1ba7043ffcc86c417c072aa74d649202
Grant Number
EP/J006572/1
Subjects
Science & Technology
Technology
Physical Sciences
Operations Research & Management Science
Mathematics, Applied
Mathematics
Nonconvex optimization
Global optimization
Convex relaxations
McCormick relaxations
Taylor models
McCormick-Taylor models
Interval extensions
Convergence rate
Operations Research
Applied Mathematics
Numerical And Computational Mathematics
0802 Computation Theory And Mathematics
Publication Status
Published