Rigorous Methods for Dynamic Optimization

Interval analysis and related verified solution methods provide mathematically and computationally guaranteed solution enclosures that bound all the possible solutions of dynamic systems with uncertainties. This provides a foundation for rigorous deterministic global optimization and continuous satisfaction of path constraints. Based on this methodology, we present here new algorithms for two types of problem: dynamic global optimization (DGO) subject to inequality path constraints (IPC) and robust design and global optimization with uncertain parameters.

The DGO method is based on techniques developed for the verified solution of parametric systems of ordinary differential equations. These techniques provide rigorous interval bounds on the state variables, and thus on the constraints and objective function in the DGO problem. These techniques also provide explicit analytic representations (Taylor models) of these bounds in terms of the decision variables. This facilitates the use of constraint propagation techniques that can greatly reduce the domain to be searched for the global optimum. Since IPCs are often related to safety concerns, we adopt a conservative approach to constraint satisfaction. Through this approach, the search for the global optimum is restricted to a space in which continuous satisfaction of the IPCs is rigorously guaranteed, and an ε -global optimum within this space is determined.

We then extend the DGO method and adopt a bi-level branch and reduce structure to address robust design and global optimization with uncertain parameters. Within the framework, we implement a heuristic subregion management procedure to achieve more efficient decisions. This approach provides guaranteed-feasible decision variable regions for robust design problems and locates an ε -global optimum over a confirmed feasible region for robust optimization problems.

Solving dynamic optimization problems with a rigorous approach can be computationally challenging. Therefore, another major goal here is to discuss how to tackle this challenge with parallel programming techniques. A general dynamic load balancing framework is designed, implemented using Message Passing Interface (MPI) and Posix multi-threads, and tested on a multi-core server. The effects of virtual networks and communication schemes are discussed.

Examples and comparative results for several problems are presented to demonstrate the potential of the methods presented and their computational performance.