Entry Date:
April 28, 2004

Convex Relaxations for Dynamic Optimization Problems

Principal Investigator Paul Barton


The time dependent (or dynamic) behavior of many systems of practical interest can be modeled with ordinary differential equations (ODEs) or differential-algebraic equations (DAEs). It is often desirable to find the optimal way to design or operate such systems over time, as measured by some appropriate metric. This optimization can be done rigorously and automatically by solving mathematical programming problems with these ODE and DAE models embedded. In most realistic applications, these dynamic optimization problems will be nonconvex and a consequence of this is that current algorithms cannot guarantee that they will always find the (global) optimal solution. This project is developing algorithms and software that can guarantee finding the global optimal solution of nonconvex dynamic optimization problems.

The key contribution of this research has been to develop a theory for constructing convex relaxations of nonconvex functionals with ODEs embedded, which is a convex functional that underestimates the nonconvex functional on the set of interest. With these convex relaxations it is then possible to apply existing deterministic global optimization algorithms such as branch-and-bound and nonconvex outer approximation to solve dynamic optimization problems. We are currently exploring the performance and implementation of our convex relaxation theory for realistic engineering problems.