(288g) Global Dynamic Optimization: Convergence Order of Relaxations

Chemical engineering processes are routinely modeled using ordinary differential equations (ODEs).  Two examples are (i) processes run in batch mode, whose time-varying behavior can be simulated using ODEs and (ii) plug-flow reactors, which obey ODEs at steady state.  So-called dynamic optimization is used to solve optimization problems with an underlying ODE model.  In chemical engineering, estimating model parameters (such as rate constants) and maximizing the performance of dynamic processes are two of the most common modes in which dynamic optimization is used.  Dynamic optimization problems typically have many suboptimal local minima; global minima are often very difficult to locate using local optimization methods.  Global dynamic optimization (GDO) techniques can rigorously guarantee finding one of the best possible solutions within some user-specified tolerance.  The GDO approach studied here generates lower and upper bounds [1,2], as well as convex and concave relaxations [3,4], of the solutions of parameterized ODEs for ranges of initial conditions and parameters.  It employs a shooting, or partial discretization, approach in which an auxiliary ODE system is numerically integrated to yield bounds and relaxations of the solutions of the parameterized ODEs.

In the present work, we derive convergence order results for the aforementioned bounds and relaxations, following the work of [5,6].  More specifically, we show how their tightness depends on the time horizon and the size of the decision space.  We use these convergence order results to explain why two relaxation methods [3,4] both obey a second-order convergence bound yet can have vastly different computational costs in practice.

Looking forward, this framework informs the design of new bounding and relaxation methods.  By enabling analysis of shooting-based bounding and relaxation methods for dynamic optimization problems, it sheds light on the design of next-generation methods for better convergence properties and computational efficiency.

[1] Singer, A.B.; Barton, P.I., “Bounding the solutions of parameter dependent nonlinear ordinary differential equations,” SIAM Journal on Scientific Computing 27(6), 2167-2182, 2006.

[2] Scott, J.K.; Barton, P.I., “Bounds on the reachable sets of nonlinear control systems,” Automatica 49(1), 93-100, 2013.

[3] Scott, J.K.; Chachuat, B.; Barton, P.I., “Nonlinear convex and concave relaxations for the solutions of parametric ODEs,” Optimal Control Applications and Methods 34(2), 145-163, 2013.

[4] Scott, J.K.; Barton, P.I., “Improved relaxations for the parametric solutions of ODEs using differential inequalities,” Journal of Global Optimization, published online 2012, DOI: 10.1007/s10898-012-9909-0.

[5] Bompadre, A; Mitsos, A. "Convergence rate of McCormick relaxations," Journal of Global Optimization 52, 1-28, 2012.

[6] Bompadre, A; Mitsos, A; Chachuat, B. "Convergence analysis of Taylor models and McCormick-Taylor models," Journal of Global Optimization, published online 2012, DOI: 10.1007/s10898-012-9998-9.