(194d) Reachability Bounds for Global and Robust Optimization of Parametric ODEs Via Implicit Methods

Enclosures of the set of reachable solutions of parametric ordinary differential equation systems (pODEs) have multiple applications in robust model predictive control [1], set-based fault detection [2], and optimal control [3]. In a global optimization context, these enclosures are used to construct relaxations required to compute valid lower bounds on the optimal solution value [4]. Multiple different approaches have been taken to create these enclosures; recently, a number have incorporated the use of McCormick arithmetic to produce tight bounds [5,6]. These approaches include the differential-inequality approach [7], a discretized-and-relax scheme [8], and the use of a Taylor -McCormick models [9]. In each case, these approaches rely on a series of sequential calculations using explicit expressions for intermediate terms.

We present a novel approach to calculating relaxations of the set of solutions of ordinary differential equations subject to parametric uncertainty and uncertain initial values. This approach allows for the relaxation of pODE solution sets via parametric linear multistep methods, constructed in a sequential-block fashion. Each block is relaxed via the implicit method developed in [10]. We show that this algorithm exhibits partition convergence. As a consequence of this result, our method exhibits the favorable properties inherent to generalized McCormick relaxations: tightness of the relaxations, enhanced convergence speed [11], and a propensity to avoid clustering about global minima [12].

The relaxations developed herein have been implemented as an extension to the EAGO software package in Julia [13, 14]. A performance assessment was made using a series of examples common in the extant literature. In multiple cases, these new techniques allow for an improved solution time when used within a deterministic global optimization context. As a further result, we show that this new approach can be readily applied to semi-infinite programs using the approach presented in [15]. Finally, we solve select worst-case design problems with pODE constraints.

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

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

[3] Houska, B., et al. Branch-and-lift algorithm for deterministic global optimization in nonlinear optimal control. J. Optim. Theor. Appl. 162(1), 208-248, 2014.

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

[5] Mitsos, A., Chachuat, B., and Barton, P.I. McCormick-Based Relaxations of Algorithms. SIAM J. Optim. 20(2): 573-601.

[6] Scott, J.K., Stuber, M.D., and Barton, P.I. Generalized McCormick Relaxations. J Global Optim, 51:569-606, 2011.

[7] A.B. Singer, P.I. Barton, Bounding the solutions of parameter dependent nonlinear ordinary differential equations, SIAM J. Sci. Comput. 27 (2006) 2167–2182.

[8] 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.

[9] 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.

[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] Bompadre, A. and Mitsos, A. Convergence rate of McCormick relaxations. J Global Optim, 52:1-28, 2012.

[12] Wechsung, A., Schaber, S.D., and Barton, P.I., The cluster problem revisited. J Global Optim, 58(3):429-438, 2014.

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

[14] 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.

[15] Stuber, M.D., and Barton, P.I. Semi-Infinite Optimization with Implicit Functions. Ind. Eng. Chem. Res., 54:307-317, 2015.