Unified framework for the propagation of continuous-time enclosures for parametric nonlinear ODEs. (English) Zbl 1320.49013
Summary: This paper presents a framework for constructing and analyzing enclosures of the reachable set of nonlinear ordinary differential equations using continuous-time set-propagation methods. The focus is on convex enclosures that can be characterized in terms of their support functions. A generalized differential inequality is introduced, whose solutions describe such support functions for a convex enclosure of the reachable set under mild conditions. It is shown that existing continuous-time bounding methods that are based on standard differential inequalities or ellipsoidal set propagation techniques can be recovered as special cases of this generalized differential inequality. A way of extending this approach for the construction of nonconvex enclosures is also described, which relies on Taylor models with convex remainder bounds. This unifying framework provides a means for analyzing the convergence properties of continuous-time enclosure methods. The enclosure techniques and convergence results are illustrated with numerical case studies throughout the paper, including a six-state dynamic model of anaerobic digestion.
MSC:
| 49L20 | Dynamic programming in optimal control and differential games |
| 49M37 | Numerical methods based on nonlinear programming |
| 34A40 | Differential inequalities involving functions of a single real variable |
| 93B03 | Attainable sets, reachability |
| 90C26 | Nonconvex programming, global optimization |
Keywords:
ordinary differential equations; reachable sets; differential inequalities; dynamic optimization; global optimization; convergence analysis; interval analysis; ellipsoidal calculus; Taylor modelsReferences:
| [1] | Adjiman, C.S., Dallwig, S., Floudas, C.A., Neumaier, A.: A global optimization method, \[ \alpha\] αBB, for general twice-differentiable constrained NLPs—I. Theoretical advances. Comput. Chem. Eng. 22(9), 1137-1158 (1998) · doi:10.1016/S0098-1354(98)00027-1 |
| [2] | Alamo, T., Bravo, J.M., Camacho, E.F.: Guaranteed state estimation by zonotopes. Automatica 41(6), 1035-1043 (2005) · Zbl 1091.93038 · doi:10.1016/j.automatica.2004.12.008 |
| [3] | Althoff, M., Stursberg, O., Buss, M.: Reachability analysis of nonlinear systems with uncertain parameters using conservative linearization. In: 47th IEEE Conference on Decision and Control, 2008. CDC 2008, pp 4042-4048 (2008) · Zbl 1107.90035 |
| [4] | Aubin, J.P.: Viability Theory. Birkhauser, Boston (1991) · Zbl 0755.93003 |
| [5] | Aubin, J.P., Cellina, A.: Differential Inclusions: Set-Valued Maps and Viability Theory. Grundlehren der mathematischen Wissenschaften, #264. Springer, Berlin (1984) · Zbl 0538.34007 · doi:10.1007/978-3-642-69512-4 |
| [6] | Azagra, D., Ferrera, J.: Every closed convex set is the set of minimizers of some \[{C}^\infty C\]∞-smooth function. Proc. Am. Math. Soc. 130(12), 3687-3692 (2002) · Zbl 1028.49003 · doi:10.1090/S0002-9939-02-06695-9 |
| [7] | Bernard, O., Hadj-Sadok, Z., Dochain, D., Genovesi, A., Steyer, J.P.: Dynamical model development and parameter identification for an anaerobic wastewater treatment process. Biotechnol. Bioeng. 75(4), 424-438 (2001) · doi:10.1002/bit.10036 |
| [8] | Berz, M., Makino, K.: Verified integration of ODEs and flows using differential algebraic methods on high-order Taylor series. Reliab. Comput. 4, 361-369 (1998) · Zbl 0976.65061 · doi:10.1023/A:1024467732637 |
| [9] | Berz, M., Makino, K.: Performance of taylor model methods for validated integration of ODEs. Lect. Notes Comput. Sci. 3732, 65-74 (2006) |
| [10] | Blanchini, F., Miani, S.: Set-Theoretic Methods in Control. Birkhäuser, Basel (2008) · Zbl 1140.93001 |
| [11] | Bompadre, A., Mitsos, A.: Convergence rate of McCormick relaxations. J. Global Optim. 52(1), 1-28 (2012) · Zbl 1257.90077 · doi:10.1007/s10898-011-9685-2 |
| [12] | Bompadre, A., Mitsos, A., Chachuat, B.: Convergence analysis of Taylor and McCormick-Taylor models. J. Global Optim. 57(1), 75-114 (2013) · Zbl 1295.90052 · doi:10.1007/s10898-012-9998-9 |
| [13] | Chachuat, B.; Latifi, MA; Floudas, CA (ed.); Pardalos, PM (ed.), A new approach in deterministic global optimization of problems with ordinary differential equations, No. 74, 83-108 (2003), Dordrecht · Zbl 1165.90686 · doi:10.1007/978-1-4613-0251-3_5 |
| [14] | Chachuat, B.; Villanueva, ME; Bogle, IDL (ed.); Fairweather, M. (ed.), Bounding the solutions of parametric ODEs: when Taylor models meet differential inequalities, No. 30, 1307-1311 (2012), Amsterdam · doi:10.1016/B978-0-444-59520-1.50120-2 |
| [15] | Chachuat, B., Singer, A.B., Barton, P.I.: Global methods for dynamic optimization and mixed-integer dynamic optimization. Ind. Eng. Chem. Res. 45(25), 8373-8392 (2006) · Zbl 1035.81024 · doi:10.1021/ie0601605 |
| [16] | Chutinan, A., Krogh, B.H.: Verification of polyhedral-invariant hybrid automata using polygonal flow pipe approximations. In: Vaandrager, F.W., van Schuppen, J.H. (eds.) Hybrid Systems: Computation and Control, no. 1569 in Lecture Notes in Computer Science, Springer, Berlin, pp 76-90 (1999) · Zbl 0954.93020 |
| [17] | Clarke, F.H.: Generalized gradients and applications. Trans. Am. Math. Soc. 205, 247-262 (1975) · Zbl 0307.26012 · doi:10.1090/S0002-9947-1975-0367131-6 |
| [18] | Coddington, E.A., Levinson, N.: Theory of Ordinary Differential Equations. McGraw-Hill, New York (1955) · Zbl 0064.33002 |
| [19] | Corliss, GF; Rihm, R.; Alefeld, G. (ed.); Frommer, A. (ed.); Lang, B. (ed.), Validating an a priori enclosure using high-order Taylor series, 228-238 (1996), Berlin · Zbl 0851.65054 |
| [20] | Du, K., Kearfott, R.B.: The cluster problem in multivariate global optimization. J. Global Optim. 5(3), 253-265 (1994) · Zbl 0824.90121 · doi:10.1007/BF01096455 |
| [21] | Eijgenraam, P.: The solution of initial value problems using interval arithmetic: formulation and analysis of an algorithm, Mathmematical Centre tracts, vol. 144. Mathematisch Centrum (1981) · Zbl 0471.65043 |
| [22] | Fiacco, A.V.: Introduction to Sensitivity and Stability Analysis in Nonlinear Programming, Mathematics in Science and Engineering, vol. 165. Academic Press, New York (1983) · Zbl 0543.90075 |
| [23] | Friedrichs, K.: The identity of weak and strong extensions of differential operators. Trans. Am. Math. Soc. 55(1), 132-151 (1944) · Zbl 0061.26201 · doi:10.2307/1990143 |
| [24] | Gronwall, T.H.: Note on the derivatives with respect to a parameter of the solutions of a system of differential equations. Ann. Math. 20(2), 292-296 (1919) · JFM 47.0399.02 · doi:10.2307/1967124 |
| [25] | Hairer, E., Nørsett, S.P., Wanner, G.: Solving Ordinary Differential Equations I: Nonstiff Problems, 2nd edn. Springer, Berlin (1993) · Zbl 0789.65048 |
| [26] | Houska, B., Logist, F., Van Impe, J., Diehl, M.: Robust optimization of nonlinear dynamic systems with application to a jacketed tubular reactor. J. Process Control 22, 1152-1160 (2012) · doi:10.1016/j.jprocont.2012.03.008 |
| [27] | Jaulin, L.: Nonlinear bounded-error state estimation of continuous-time systems. Automatica 38(6), 1079-1082 (2002) · Zbl 1026.93015 · doi:10.1016/S0005-1098(01)00284-9 |
| [28] | Kieffer, M., Walter, E., Simeonov, I.: Guaranteed nonlinear parameter estimation for continuous-time dynamical models. In: Ninness, B., Hjalmarsson, H. (eds.) Proceeding of the 14th IFAC Symposium on System Identification (SYSID), pp. 843-848 (2006) · Zbl 1026.93015 |
| [29] | Kurzhanski, A.B.: Comparison principle for equations of the Hamilton-Jacobi type in control theory. Proc. Steklov Inst. Math. 253(1), S185-S195 (2006) · Zbl 1129.49035 · doi:10.1134/S0081543806050130 |
| [30] | Kurzhanski, A.B., Varaiya, P.: Reachability analysis for uncertain systems—the ellipsoidal technique. Dyn. Contin. Discret. Impuls. Syst. Ser. B 9(3), 347,368 (2002) · Zbl 1017.34064 |
| [31] | Lakshmikantham, V., Leela, S.: Differential and Integral Inequalities, Theory and Applications: Volume I, Ordinary Differential Equations. Academic Press, New York (1969) · Zbl 0177.12403 |
| [32] | Limon, D., Bravo, J.M., Alamo, T., Camacho, E.F.: Robust MPC of constrained nonlinear systems based on interval arithmetic. IEE Proc. Control Theory Appl. 152(3), 325-332 (2005) · doi:10.1049/ip-cta:20040480 |
| [33] | Lin, Q., Rokne, J.G.: Methods for bounding the range of a polynomial. J. Comput. Appl. Math. 58, 193-199 (1995) · Zbl 0833.65011 · doi:10.1016/0377-0427(93)E0270-V |
| [34] | Lin, Y., Stadtherr, M.A.: Deterministic global optimization of nonlinear dynamic systems. AIChE J. 53(4), 866-875 (2007a) · Zbl 1167.90335 · doi:10.1002/aic.11101 |
| [35] | Lin, Y., Stadtherr, M.A.: Validated solutions of initial value problems for parametric ODEs. Appl. Numer. Math. 57(10), 1145-1162 (2007b) · Zbl 1121.65084 · doi:10.1016/j.apnum.2006.10.006 |
| [36] | Lin, Y., Stadtherr, M.A.: Rigorous model-based safety analysis for nonlinear continuous-time systems. Comput. Chem. Eng. 33(2), 493-502 (2009) · doi:10.1016/j.compchemeng.2008.11.010 |
| [37] | Lohner, RJ; Cash, JR (ed.); Gladwell, I. (ed.), Computation of guaranteed enclosures for the solutions of ordinary initial and boundary value problems, No. 1, 425-436 (1992), Oxford · Zbl 0767.65069 |
| [38] | Lygeros, J.: On reachability and minimum cost optimal control. Automatica 40(6), 917-927 (2004) · Zbl 1068.93011 · doi:10.1016/j.automatica.2004.01.012 |
| [39] | Makino, K., Berz, M.: Efficient control of the dependency problem based on Taylor model methods. Reliab. Comput. 5(1), 3-12 (1999) · Zbl 0936.65073 · doi:10.1023/A:1026485406803 |
| [40] | Maranas, C.D., Floudas, C.A.: Global minimum potential energy conformations of small molecules. J. Global Optim. 4, 135-170 (1994) · Zbl 0797.90114 · doi:10.1007/BF01096720 |
| [41] | McCormick, G.P.: Computability of global solutions to factorable nonconvex programs: part I—convex underestimating problems. Math. Program. 10, 147-175 (1976) · Zbl 0349.90100 · doi:10.1007/BF01580665 |
| [42] | Mitchell, I.M., Bayen, A.M., Tomlin, C.J.: A time-dependent Hamilton-Jacobi formulation of reachable sets for continuous dynamic games. IEEE Trans. Autom. Control 50(7), 947-957 (2005) · Zbl 1366.91022 · doi:10.1109/TAC.2005.851439 |
| [43] | Mitsos, A., Chachuat, B., Barton, P.L.: McCormick-based relaxations of algorithms. SIAM J. Optim. 20(2), 573-601 (2009) · Zbl 1192.65083 · doi:10.1137/080717341 |
| [44] | Nedialkov, N.S., 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. Reliab. Comput. 5(3), 289-310 (1999) · Zbl 0947.65081 · doi:10.1023/A:1009936607335 |
| [45] | Nedialkov, N.S., Jackson, K.R., Corliss, G.: Validated solutions of initial value problems for ordinary differential equations. Appl. Math. Comput. 105, 21-68 (1998) · Zbl 0934.65073 · doi:10.1016/S0096-3003(98)10083-8 |
| [46] | Nedialkov, N.S., Jackson, K.R., Pryce, J.D.: An effective high-order interval method for validating existence and uniqueness of the solution of an IVP for an ODE. Reliab. Comput. 7, 449-465 (2001) · Zbl 1003.65077 · doi:10.1023/A:1014798618404 |
| [47] | Neher, M., Jackson, K.R., Nedialkov, N.S.: On Taylor model based integration of ODEs. SIAM J. Numer. Anal. 45, 236-262 (2007) · Zbl 1141.65056 · doi:10.1137/050638448 |
| [48] | Neumaier, A.: Taylor forms—use and limits. Reliab. Comput. 9(1), 43-79 (2002) · Zbl 1071.65070 · doi:10.1023/A:1023061927787 |
| [49] | Papamichail, I., Adjiman, C.S.: A rigorous global optimization algorithm for problems with ordinary differential equations. J. Global Optim. 24(1), 1-33 (2002) · Zbl 1026.90071 · doi:10.1023/A:1016259507911 |
| [50] | Papamichail, I., Adjiman, C.S.: Global optimization of dynamic systems. Comput. Chem. Eng. 28(3), 403-415 (2004) · doi:10.1016/S0098-1354(03)00195-9 |
| [51] | Ramdani, N., Meslem, N., Candau, Y.: A hybrid bounding method for computing an over-approximation for the reachable set of uncertain nonlinear systems. IEEE Trans. Autom. Control 54(10), 2352-2364 (2009) · Zbl 1367.93063 · doi:10.1109/TAC.2009.2028974 |
| [52] | Rauh, A., Hofer, E.P., Auer, E.: VALENCIA-IVP: A comparison with other initial value problem solvers. In: Proceedings of the 12th GAMM-IMACS International Symposium on Scientific Computing, Computer Arithmetic and Validated Numerics (SCAN’2006), Duisburg, Germany (2006) |
| [53] | Rauh, A., Westphal, R., Aschemann, H.: Verified simulation of control systems with interval parameters using an exponential state enclosure technique. In: 2013 18th International Conference on Methods and Models in Automation and Robotics (MMAR), pp. 241-246 (2013) |
| [54] | Sahlodin, A.M.: Global Optimization of Dynamic Process Systems Using Complete Search Methods. PhD Thesis, McMaster University, Ontario, Canada (2012) · Zbl 1003.65077 |
| [55] | Sahlodin, A.M., Chachuat, B.: Convex/concave relaxations of parametric ODEs using Taylor models. Comput. Chem. Eng. 35(5), 844-857 (2011a) · doi:10.1016/j.compchemeng.2011.01.031 |
| [56] | Sahlodin, A.M., Chachuat, B.: Discretize-then-relax approach for convex/concave relaxations of the solutions of parametric ODEs. Appl. Numer. Math. 61, 803-820 (2011b) · Zbl 1214.65041 · doi:10.1016/j.apnum.2011.01.009 |
| [57] | Scott, J.K., Barton, P.I.: Bounds on the reachable sets of nonlinear control systems. Automatica 49(1), 93-100 (2013a) · Zbl 1257.93015 · doi:10.1016/j.automatica.2012.09.020 |
| [58] | Scott, J.K., Barton, P.I.: Improved relaxations for the parametric solutions of ODEs using differential inequalities. J. Global Optim. 57(1), 143-176 (2013b) · Zbl 1273.49034 · doi:10.1007/s10898-012-9909-0 |
| [59] | Scott, J.K., Stuber, M., Barton, P.I.: Generalized McCormick relaxations. J. Global Optim. 51(4), 569-606 (2011) · Zbl 1232.49033 · doi:10.1007/s10898-011-9664-7 |
| [60] | Scott, J.K., Chachuat, B., Barton, P.I.: Nonlinear convex and concave relaxations for the solutions of parametric ODEs. Opt. Control Appl. Methods 34(2), 145-163 (2013) · Zbl 1273.93089 · doi:10.1002/oca.2014 |
| [61] | Singer, A.B., Barton, P.I.: Global solution of optimization problems with parameter-embedded linear dynamic systems. J. Optim. Theory Appl. 121(3), 613-646 (2004) · Zbl 1107.90035 · doi:10.1023/B:JOTA.0000037606.79050.a7 |
| [62] | Singer, A.B., Barton, P.I.: Bounding the solutions of parameter dependent nonlinear ordinary differential equations. SIAM J. Sci. Comput. 27(6), 2167-2182 (2006) · Zbl 1111.34030 · doi:10.1137/040604388 |
| [63] | Tomlin, C.J.: Verification and control of hybrid systems using reachability analysis. In: 19th Mediterranean Conference on Control and Automation (MED), Corfu, Greece (2011) · Zbl 1121.65084 |
| [64] | Tomlin, C.J., Mitchell, I., Bayen, A.M., Oishi, M.: Computational techniques for the verification of hybrid systems. Proc. IEEE 91(7), 986-1001 (2003) · doi:10.1109/JPROC.2003.814621 |
| [65] | Varaiya, P., Kurzhanski, A.B.: Ellipsoidal methods for dynamics and control. Part I. J. Math. Sci. 139(5), 6863-6901 (2006) · Zbl 1131.93020 · doi:10.1007/s10958-006-0397-y |
| [66] | Villanueva, ME; Paulen, R.; Houska, B.; Chachuat, B.; Kraslawski, A. (ed.); Turunen, I. (ed.), Enclosing the reachable set of parametric ODEs using taylor models and ellipsoidal calculus, No. 31 (2013), Amsterdam |
| [67] | Walter, W.: Differential and Integral Inequalities. Springer, Berlin (1970) · Zbl 0252.35005 · doi:10.1007/978-3-642-86405-6 |
| [68] | Wechsung, A., Schaber, S.D., Barton, P.I.: The cluster problem revisited. J. Global Optim. doi:10.1007/s10898-013-0059-9 · Zbl 1297.49046 |
| [69] | Zhou, T.S., Zhang, J.J., Yuan, Z.J., Chen, L.N.: Synchronization of genetic oscillators. Chaos 18(3), 037,126 (2008) · doi:10.1063/1.2978183 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
