(627f) Parallel Decomposition of Nonlinear Dynamic Optimization Problems

Problems with block structure arise in a number of areas, including dynamic optimization, parameter estimation, and nonlinear stochastic programming.  While nonlinear programming has proven to be an effective tool for tackling these problems, the size of these problems can become prohibitively large for serial approaches on modern computer workstations due to both efficiency concerns and memory constraints.  To address these issues, tools and algorithms have been developed to exploit the block structure of these problems and solve the NLP in parallel.

The simultaneous approach for solution of dynamic optimization problems discretizes all the variables and includes the discretized model as constraints in a large-scale optimization problem.  These problems are very large, but they are sparse and inherently structured as a result of the discretization.  The inherent structure of these problems allows for problem decomposition to solve the linear KKT systems in parallel. Interior-point methods provide a framework for efficient solution of these problems since the linear systems that are solved to find the step maintain a consistent structure from iteration to iteration.

The KKT system solved at each inner iteration of the interior-point method has a block structure with coupling induced by the continuity equations resulting from the discretization. Through the addition of coupling variables, a Schur-complement decomposition approach can be used that decouples individual KKT blocks associated with portions of the time horizon. The individual KKT blocks have a structure that is consistent with the overall structure of the dynamic optimization problem. The Schur-complement can be efficiently formed in parallel and then solved in serial to find the step in the coupling variables and multipliers. The remaining step variables can be solved in parallel. In this strategy, the size of the Schur-complement increases with the number of processors used. Therefore, there is a trade-off between parallel speedup and the time required to factorize and solve the Schur-complement in serial. The approach shows very favorable speedup for problems with few state variables relative to the number of algebraic variables.

This parallel algorithm is currently being integrated with the existing Modelica/Optimica modeling framework. In this presentation, we will show timing results for constructed dynamic optimization problems to show the parallel speedup as a function of the ratio of state to algebraic variables. In addition, we will discuss current research into the use of iterative linear solvers for solution of the Schur-complement system.