(463d) Convergence Rate of Taylor Model-Based Estimators in Global Optimization

We analyze the convergence of Taylor and McCormick-Taylor model estimators, which have been used, e.g., in enclosing the solutions of nonlinear differential equations [1,2]. Both estimators propagate a multivariate polynomial part symbolically that matches the Taylor expansion of the estimated function up to a specified order, together with an estimator of the Taylor remainder. The latter consists of an interval estimator in a Taylor model and of a pair of convex/concave McCormick relaxations [3] in a McCormick-Taylor model.

The concept of convergence order of an estimator finds its origins in interval extensions and compares the rates of convergence of the estimation error and of the range of the estimated function. Recently, Bompadre and Mitsos [4] applied and extended this concept to McCormick relaxations. Building upon this work (and refining some of their results), we determine how the convergence orders of the remainder estimators propagate through 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 sharper bounds or even result in a higher convergence rate.

References:

1. Lin Y, Stadtherr MA (2007) Validated solutions of initial value problems for parametric ODEs. Appl Numer Math 57(10):1145–1162
2. Sahlodin AM, Chachuat B (2011) Convex/concave relaxations of parametric ODEs using Taylor models. Comput Chem Eng 35(5):844–857
3. McCormick GP (1976) Computability of global solutions to factorable nonconvex programs: Part I – Convex underestimating problems. Math Program 10:147–175
4. Bompadre A, Mitsos A (2012) Convergence rate of McCormick relaxations. J Global Optim 52(1):1-28