Deterministic Global Optimization with Differential-Algebraic Equations Embedded

A fully deterministic method is proposed for the global solution of optimization problems with nonlinear, semi-explicit, index-one differential-algebraic equations (DAEs) embedded. Detailed models of a wide variety dynamic chemical processes, which may include material and energy balances, chemical reaction kinetics, thermodynamic relationships, and semi-empirical process models, are naturally described by systems of nonlinear DAEs. Accordingly, many important process engineering problems take the form of optimization problems with DAEs embedded, including determination of optimal operating conditions and/or control profiles, as well as safety verification problems. Another important application is parameter estimation for differential-algebraic models, which takes the form of a least-squares minimization  with DAEs embedded.

Research on dynamic optimization in the chemical engineering literature alone has produced a number of representative examples which are nonconvex and display multiple suboptimal local minima. Moreover, the absence of an analytical solution to the embedded dynamic system in all but trivial cases makes it extremely difficult to determine whether a given problem is convex or not.  These considerations motivate the development of global optimization algorithms for problems with dynamic systems embedded. This need is further compounded by the observation that local optima do not provide meaningful information for many important applications, including safety verification problems and parameter estimation problems in the context of model falsification.

Previous literature has primarily treated optimization problems with DAEs embedded using local methods or stochastic global methods which cannot guarantee global optimality. Another simple approach is to discretize the embedded DAEs  in order to reduce the original dynamic optimization problem to a standard nonlinear program, which can be solved to global optimality using existing methods. However, an accurate representation of the embedded dynamics requires a fine discretization, which results in the addition of too many variables for practical global optimization, even for very simple problems.  A more customized approach, which does not require discretization, uses a branch-and-bound optimization strategy in conjunction with a theory for constructing convex underestimating programs using second order sensitivities of the embedded DAEs.  Though this method appears to produce the global solution for simple test cases, it employs a sampling procedure to obtain global information about the second order sensitivities, and hence cannot guarantee global optimality in the general case.

The method presented in this work uses recent extensions of McCormick's relaxation theory to construct convex and concave relaxations of the solutions of nonlinear systems of DAEs. Using these relaxations, existing techniques can be used to construct convex underestimating programs, which in turn enables the use of branch-and-bound global optimization techniques. Because no discretization is required, the proposed algorithm operates in the original decision space, without the introduction of additional variables. Moreover, global information concerning solutions of the dynamic system is obtained via the proposed relaxation theory, rather than through sampling. Accordingly, the proposed algorithm is fully deterministic.

This presentation describes the proposed algorithm, with particular focus on the construction of convex and concave relaxations of the solutions of the embedded DAEs, and performance is analyzed through chemical engineering examples.