(106b) A Block-Bordered Interior Point Approach for the Solution of Multiperiod Nonlinear Programs | AIChE

(106b) A Block-Bordered Interior Point Approach for the Solution of Multiperiod Nonlinear Programs

Authors 

Biegler, L. - Presenter, Carnegie Mellon University


Successful solution of large-scale nonlinear programs often relies on specialized software and algorithms that exploit problem specific structure. In this work, we present an interior point approach for efficient solution of large-scale nonlinear programs with block-bordered structure. In conjunction with IBM Research, we have recently released IPOPT 3.0.0 (www.coin-or.org), an object-oriented, interior point nonlinear programming code. This new implementation easily allows the creation of specialized approaches for exploiting problem specific structure without changes to the fundamental algorithm code. Using this framework, we have begun development of a general purpose nonlinear programming tool for efficient solution of block-bordered problems and use this tool to solve a source inversion problem under uncertainty.

In particular, we address multiperiod, or multiscenario optimization problems where the KKT system can be decomposed into a large, sparse, block diagonal upper left corner and relatively few linking variables between individual blocks (forming bands at the right and bottom edge). This structure is present in a number of applications, including robust optimization. In process design under uncertainty problems, each individual block comes from a different probabilistic scenario of the uncertain parameters and the design variables are the only link between scenarios. With spatial decomposition techniques, each individual block represents a particular spatial region and the common variables arise from the links between these regions. We make no assumption about the structure of individual blocks and allow efficient solutions for problems where the model structure may differ in each block.

Interior point optimization techniques like IPOPT remove the need for an active-set strategy by moving the inequality constraints into the objective in the form of a barrier term. With large multiscenario problems, there may be many active inequalities at the solution. Interior point methods remain efficient since they do not require a combinatorial identification of the active-set. Furthermore, these techniques are well-suited for solving specialized problems since the structure of the KKT system remains consistent from iteration to iteration regardless of the activity of inequality constraints. For the solution of multiscenario problems, we have augmented the IPOPT framework to include the specification of the problem structure. At each iteration of IPOPT, we then solve the block-bordered KKT system using a schur-complement technique, where individual blocks are factored and solved in parallel to form the small, dense schur-complement corresponding to the linking variables.

In previous work, we introduced a dynamic optimization approach for identifying contamination sources in large municipal drinking water networks given concentration measurements from a sparse sensor grid. A large-scale nonlinear program was formulated by discretizing the network model constraints and solving the differential water quality model simultaneously with the estimation problem. Using known water network flowrates, an origin tracking algorithm was used to approximate the pipe time delays, removing the need for a spatial discretization. While real-time solutions were possible with this simultaneous approach, it was assumed that the individual water demands were known or measured. In reality, these demands are only loosely characterized, and here, we propose a multiscenario optimization approach for solving the source inversion problem under uncertainty. We generate individual scenarios by sampling distributions for the water network demands and formulating the water quality model for each scenario. Including all of these scenarios in the estimation problem leads to a very large scale nonlinear program with the structure described above.

This work introduces a new object-oriented implementation of the reliable, open source, nonlinear programming tool, IPOPT. The multiperiod optimization framework is linked to the AMPL modeling language to allow simple interfacing of new problems. We show efficient solution of the block-bordered system in serial and continue development for a parallel version.