(125c) Efficient Linear Underestimators for Dynamic Process Systems

Khan, K. A., McMaster University
Established methods for deterministic global optimization typically compute useful global bounding information by constructing and minimizing convex underestimators of process models. However, generating useful convex underestimators for dynamic systems is difficult; dynamics obscure our intuition about the dependence of a model on its parameters, and any discrepancy between a dynamic model and its convex underestimator may well grow exponentially with system time. Nevertheless, there is room for improvement; supplying tighter convex underestimators for dynamic models would broaden the class of dynamic optimization problems that can be solved to global optimality with given computational resources, as would reducing the computational effort required for subgradient evaluations.

This presentation combines and extends several recent results to obtain an efficient technique for constructing useful affine underestimators for optimization problems with embedded systems of parametric ordinary differential equations (ODEs). Differentiable relaxations are constructed for the ODE right-hand side using a method [1] developed in the “multivariate McCormick” framework [3]. These are then substituted into a description [2] of efficient ODE relaxations as an auxiliary hybrid discrete/continuous system. It may be shown that various properties of the relaxations of [1] prevent the discrete behavior of this hybrid system from manifesting, yielding an auxiliary ODE system that describes convex relaxations. Standard adjoint sensitivity analysis techniques may be applied to this system to compute affine underestimators for the overarching optimization problem efficiently using standard ODE solvers. Implications and examples are discussed.


[1] KA Khan, HAJ Watson, and PI Barton, Differentiable McCormick relaxations, J. Glob. Optim., 67:687-729, 2017.

[2] JK Scott and PI Barton, Improved relaxations for the parametric solutions of ODEs using differential inequalities, J. Glob. Optim., 57:143-176, 2013.

[3] A Tsoukalas and A Mitsos, Multivariate McCormick relaxations, J. Glob. Optim., 59:633-662, 2014.