(278c) Generating Subgradients for Bounding in Global Dynamic Optimization

Global dynamic optimization problems arise in engineering applications such as parameter estimation, global optimal control, and worst-case uncertainty analysis. While state-of-the-art deterministic solvers including BARON and ANTIGONE are effective at solving nondynamic global optimization problems, current deterministic algorithms for global dynamic optimization can only solve problems on the order of tens of state variables and decision variables. Thus, improved techniques are sought to extend the scope of these algorithms to problems of practical interest.

A major computational bottleneck for global dynamic optimization is generating lower bounds for the globally optimal objective value. These bounds are typically supplied by minimizing convex relaxations for the solutions of parametric ordinary differential equations (ODEs) with respect to decision variables. In a state-of-the-art method [1] for generating ODE relaxations, relaxations are described as the solutions of an auxiliary ODE system. While this method has been shown to be effective for formulating tight ODE relaxations, there is thus far no established method for computing these relaxations’ subgradients, which would speed up the computation of lower bounds.

Hence, this presentation describes a new approach for generating subgradients for Scott—Barton relaxations [1]. This new approach describes valid subgradients as the solutions of another affine auxiliary ODE system, to be integrated simultaneously with the Scott—Barton ODE system. Unlike an established subgradient propagation approach [2] for convex ODEs, our new approach permits nonconvex right-hand sides of ODE relaxation systems, and thus is applicable to the Scott—Barton relaxations. Unlike an established approach [3] that propagates valid subgradients for nonsmooth systems, the new auxiliary right-hand sides are continuous with respect to state variables, and thus are easily integrated by off-the-shelf numerical ODE solvers. Moreover, unlike these existing approaches, the new subgradients may also be computed efficiently using adjoint sensitivity methods. Thus, this work essentially extends classical dynamic adjoint sensitivity analysis from differentiable systems to nonsmooth convex systems, which may help reduce computational effort for an overarching global dynamic optimization method. Numerical examples are presented, and further implications are discussed.

[1] J.K. Scott and P.I. Barton. Improved relaxations for the parametric solutions of ODEs using differential inequalities, Journal of Global Optimization, 57(1):143-176, 2013.

[2] K.A., Khan. Subtangent-based approaches for dynamic set propagation. In Proceedings of the 57^th IEEE Conference on Decision and Control, Miami Beach, FL, USA, 17 December 2018.

[3] K.A., Khan and P.I., Barton. Generalized derivatives for solutions of parametric ordinary differential equations with non-differentiable right-hand sides. Journal of Optimization Theory and Applications, 163(2): 355-386, 2014.