Rigorous Methods for Dynamic Optimization

Doctoral Dissertation

Abstract

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.

Attributes

Attribute NameValues
URN
  • etd-04182013-183418

Author Yao Zhao
Advisor Dr. Mark A. Stadtherr
Contributor Dr. Mark A. Stadtherr, Committee Chair
Contributor Dr. David Leighton , Committee Member
Contributor Dr. Jeffrey Kantor , Committee Member
Contributor Dr. Samuel Paolucci , Committee Member
Degree Level Doctoral Dissertation
Degree Discipline Chemical Engineering
Degree Name PhD
Defense Date
  • 2013-04-09

Submission Date 2013-04-18
Country
  • United States of America

Subject
  • Dynamic Load Balancing

  • Robust Optimization

  • Interval Analysis

  • Taylor Model

  • Dynamic Optimization

  • Verified Integration

Publisher
  • University of Notre Dame

Language
  • English

Record Visibility and Access Public
Content License
  • All rights reserved

Departments and Units

Files

Please Note: You may encounter a delay before a download begins. Large or infrequently accessed files can take several minutes to retrieve from our archival storage system.