(278b) Guaranteed Relaxations and Bounds on the Solution Sets of Parametric ODEs Via Implicit Linear Multistep Methods

Valid enclosures of the set of reachable solutions of parametric ordinary differential equation systems (pODEs) play a central role in numerous applications ranging from set-based fault detection [1] to robust model predictive control [2]. These enclosures may be computed by a number of approaches including interval arithmetic [3], interval-Taylor arithmetic [4], differential-inequality approach [5], a discretized-and-relax scheme [6], and the use of a Taylor-McCormick models [7]. In each case, these approaches rely on a series of sequential calculations using explicit expressions for intermediate terms. In a global optimization context, these enclosures are used to construct relaxations required to compute valid lower bounds on the optimal solution value [8].

In this paper, we extend our prior work on calculating state relaxations of pODEs by means of parametric implicit linear multistep methods, first presented in [9]. This contribution consists of three substantial modifications to the prior approach. First, explicit accounting of the truncation error is conducted, resulting in bounds and relaxations that are guaranteed to enclose the entire solution set rather than a discrete approximation of it. Secondly, the mean-value forms of the residual are used to construct relaxations with the property that they are non-necessarily expansive with respect to time. We evaluate the role of different approaches to computing these bounds and relaxations using direct application of parametric implicit function theories [10,11]. As part of our third modification, we consider propagating these bounds and relaxations via parallelepiped-based enclosure via a novel semi-explicit update. In either case, these relaxations may be computed in an expedient fashion via a block-sequential approach.

Time complexity and tightness of the relaxations are compared with the existing higher-order enclosure [12], Lohner’s method [13], and Hermite-Obreshkoff method [14]. An analysis of the linear stability of these set-valued methods and estimation order is discussed along with comparisons to existing methods. The utility of these method for computing bounds and relaxations is demonstrated via a number of literatures examples. Additionally, we provide initial numerical results on using these relaxations and bounds in global optimization using a software extension to the EAGO software package in Julia [15, 16].

[1] Raimondo, D., et al. Closed-loop input design for guaranteed fault diagnosis using set-valued observers. Automatica 74, 107-117, 2005.

[2] Limon, et al. Robust MPC of constrained nonlinear systems based on interval arithmetic. IEEE Proceedings Control Theory and Applications. 152 (3), 325-332.

[3] R.E. Moore, Methods and Applications of Interval Analysis, SIAM, Philadelphia, PA, 1979.

[4] M. Berz, K. Makino, Verified integration of ODEs and flows using differential algebraic methods on high-order Taylor series, Reliab. Comput. 4: 361–369, (1998).

[5] JK Scott, PI Barton. Improved relaxations for the parametric solutions of ODEs using differential inequalities. Journal of Global Optimization 57: 143–176, 2013).

[6] Ali M. Sahlodin and Benoît Chachuat. Discretize-then-relax approach for convex/concave relaxations of the solutions of parametric ODEs. Applied Numerical Mathematics 61:803-820, 2011.

[7] Ali M. Sahlodin and Benoit Chachaut. Convex/concave relaxations of parametric ODEs using Taylor models. Computers and Chemical Engineering 35:5(11) 844-857, 2011.

[8] Lin, Y., Stadtherr, M.A. 2007a. Deterministic global optimization of nonlinear dynamic systems. AIChE Journal, 53(4) 866-875, 2007.

[9] ME Wilhelm, AV Le, MD Stuber. Global Optimization of Stiff Dynamical Systems, AIChE Journal, 65 (12).

[10] Stuber, M.D., Scott, J.K., and P.I. Barton. Convex and Concave Relaxations of Implicit Functions. Optimization Methods and Software. 30(3), 424-460, 2014.

[11] MD Stuber, Evaluation of process systems operating envelopes, Massachusetts Institute of Technology.

[12] N.S. Nedialkov, K.R. Jackson, G.F. Corliss, Validated solution of initial value problems for ordinary differential equations, Appl. Math. Comput. 105: 21–68 (1999).

[13] R.J. Lohner, Computation of guaranteed enclosures for the solutions of ordinary initial and boundary value problems, in: J.R. Cash, I. Gladwell (Eds.), Computational Ordinary Differential Equations, vol. 1, Clarendon Press, 425–436, 1992.

[14] Nedialkov, N.S. and Jackson, K.R. An interval Hermite-Obreschkoff method for computing rigorous bounds on the solution of an initial value problem for an ordinary differential equation. Reliable Computing 5(3), 289—310, 1999.

[15] Bezanson, J. et al. Julia: A fresh approach to numerical computing. SIAM Review. 59, 65-98, 2017.

[16] Wilhelm, M. and Stuber, M. Easy Advanced Global Optimization (EAGO): An Open-Source Platform for Robust and Global Optimization in Julia. AIChE Annual Meeting 2017.