(612f) Validated Integration of Nonlinear ODEs Using Taylor Models and Ellipsoidal Calculus

The computation of tight enclosures for the solutions of nonlinear ordinary differential equations (ODEs) are the basis for many rigorous methods in a variety of research fields, including  reachability analysis for control systems, global optimization of dynamic systems, and uncertainty analysis for nonlinear dynamic processes and robust optimal control; see, e.g., [1-4]. Existing methods can be classified into either continuous-time enclosure techniques or time-discretization techniques. In the former class, an auxiliary differential equation is formulated, the solution of which yields an enclosure of the original ODE solutions at any time. The focus in this presentation is on the second class, also known as first-discretize-then-bound approach.

Many such validated integration methods for nonlinear ODEs go back to the original work by Moore [5], who presented a simple test for checking the existence and uniqueness of ODE solutions over a finite time step using interval analysis. This test was later used in an algorithm that discretizes the integration horizon into finite steps and proceeds in two phases at each step [6]: (i) determine a step-size and an a priori enclosure of the ODE solutions over this step; then, (ii) propagate a tightened enclosure until the end of the step. In particular, the second phase relies on a high-order Taylor expansion of the ODE solutions in time, which can be evaluated in interval arithmetic or in Taylor model arithmetic [7,8]. The propagation of convex/concave bounds, using either McCormick relaxations or McCormick-Taylor models, has also been proposed [9,10].

We present a new algorithm for bounding the reachable set of parametric nonlinear ODEs, which is based on a first-discretize-then-bound approach and accounting for truncation errors that are inherent to the discretization. The main novelty of this algorithm is that it reverses the classical two-phase approach of validated integration by first constructing a predictor of the enclosure function and then determining a step-size for which this predictor is valid. This reversed approach leads to a natural step-size control mechanism, which no longer relies on the availability of an a priori enclosure. Another principal contribution is the introduction of a new bounder for vector-valued functions, namely Taylor models with ellipsoidal remainders. We illustrate the performance of the stability of the new algorithm with numerical case studies.

References:

1. F. Blanchini and S. Miani. Set-Theoretic Methods in Control. Birkhäuser, 2008.
2. A.B. Kurzhanski, and P. Valyi. Ellipsoidal Calculus for Estimation and Control. Birkhäuser, 1997.
3. B. Chachuat, A.B. Singer, and P.I. Barton. Global methods for dynamic optimization and mixed-integer dynamic optimization. Industrial & Engineering Chemistry Research, 45(25), 8373-8392, 2006.
4. B. Houska. Robust Optimization of Dynamic Systems. PhD thesis, KU Leuven, September 2011.
5. R.E. Moore, F. Bierbaum. Methods and Applications of Interval Analysis. SIAM, 1979.
6. N.S. Nedialkov, K.R. Jackson, and G.F. Corliss. Validated solutions of initial value problems for ordinary differential equations. Applied Mathematics & Computation, 105(1):21-368, 1999.
7. M. Berz, and K. Makino. Performance of Taylor model methods for validated integration of ODEs. Lecture Notes in Computer Science, 3732:65-74, 2006.
8. Y. Lin, and M.A. Stadtherr. Validated solutions of initial value problems for parametric ODEs. Applied Numerical Mathematics, 57:1145-1162, 2007.
9. A.M. Sahlodin, and B. Chachuat. Discretize-then-relax approach for convex/concave relaxations of the solutions of parametric ODEs. Applied Numerical Mathematics, 61:803-820, 2011.
10. A.M. Sahlodin, and B. Chachuat. Convex/concave relaxations of parametric ODEs using Taylor models. Computers & Chemical Engineering, 35:844-857, 2011.