Tuesday, November 6, 2007 - 9:45 AM

Efficient Parallel Solution of Dae Constrained Optimization Problems with Loosely Coupled Algebraic Components

Carl D. Laird1, Victor M. Zavala2, and Lorenz T. Biegler2. (1) Chemical Engineering, Texas A&M University, 3122 TAMU, College Station, TX 77843, (2) Department of Chemical Engineering, Carnegie Mellon University, 5000 Forbes Ave., Pittsburgh, PA 15213

Many large-scale nonlinear programming (NLP) problems result from repeated sets of common mathematical expressions [1]. While these large-scale NLPs may seem intractable due to the incorporation of many variables and constraints, they are inherently structured.

Traditional decomposition approaches like Generalized Benders Decomposition or Lagrangean Decomposition techniques use problem-level reformulations. As an alternative, we focus instead on the fundamental steps of the nonlinear programming algorithm. Here, we use an Internal Linear-Algebra Decomposition approach that has shown to be efficient in the solution of large, structured problems in parallel computer architectures. IPOPT [2], a primal-dual, interior-point nonlinear programming solver has been recently redesigned in order to accommodate this type of decomposition strategies [3,4]. The dominant cost at each iteration of this algorithm is the solution of a large linear system (the augmented KKT system) arising from modified Newton steps of the primal-dual optimality conditions.

One example of a structured optimization problem arises from DAE constrained optimization where, using a simultaneous approach, the discretized dynamic and algebraic equations form a large, structured set of constraints. With this type of structure, the differential blocks in time are coupled through pass-on variables, while the algebraic blocks are not coupled with each other, but instead coupled with each of the corresponding differential blocks.

In this work, we specifically consider the dynamic optimization of a low density polyethylene plant [4,5], where we model the plant dynamics along with a pseudo steady state plug-flow model of the polymerization reactor. This reactor exhibits extremely fast dynamics as a result of the particular reaction kinetics along with multiple reaction and cooling zones. The spatially discretized reactor model is included as a large set of algebraic constraints with the dynamic plant model. This gives a problem structure where the differential blocks arising from the plant dynamics are coupled with each other in time but only loosely coupled to the large set of algebraic constraints produced by the reactor model. This type of structure is not specific to this application but also arises in general dynamic systems with separable time-scales, dynamic models with complex thermodynamic routines, among others.

For this class of problem, we have developed a decomposition approach which exploits the loose coupling of the algebraic reactor model with the differential components. Using an Internal Linear Decomposition technique, we have developed specialized linear algebra code to efficiently solve the structured KKT system at each iteration of the IPOPT algorithm. This approach does not modify the fundamental steps of the algorithm and, therefore, does not alter the favorable convergence properties of the original IPOPT algorithm. Furthermore, this decomposition can be solved in parallel, making use of affordable cluster-based computing resources for efficient solution. We show parallel scale-up results for this problem as the number of available processors is increased.

[1] J. Gondzio and A. Grothey. Exploiting structure in parallel implementation of interior point methods for optimization. Technical report, School of Mathematics, The University of Edinburgh, July 2005. Technical Report MS-04-004.

[2] A. Waachter and L. T. Biegler. "On the Implementation of a Primal-Dual Interior Point Filter Line Search Algorithm for Large-Scale Nonlinear Programming", Mathematical Programming, 106(1):25–57, 2006.

[3] Laird, C. D., Biegler, L. T., “Large-Scale Nonlinear Programming for Multi-scenario Optimization”, accepted for publication in proceedings of the International Conference on High Performance Scientific Computing, Hanoi, Vietnam, 2006.

[4] Zavala, V.M., Laird, C.D., Biegler, L.T. “Interior-Point Decomposition Approaches for Parallel Solution of Large-Scale Nonlinear Parameter Estimation Problems”, accepted in Chemical Engineering Science, 2007.

[5] Bokis, C. P., "Physical Properties, Reactor Modeling, and Polymerization Kinetics in the Low-Density Polyethylene Tubular Reactor Process", Ind. eng. chem. Res. 2001, 41,1017-1030.