(200b) Parallel Solution of Large-Scale, Block-Structured, Nonlinear Programming Problems with Significant Coupling

Efficient solution of parameter estimation problems is important to all fields of science and engineering where decisions are made based on results from simulation. When describing the physics of extensive engineering and biological problems, we observe that these large-scale nonlinear parameter estimation problems frequently possess block angular structure or can be transformed to such a structure. The dominant computational expense in an interior-point based NLP solver is the solution of a linear set of equations arising from the application of a modified Newton’s method to the first-order optimality conditions. The structure of the parameter estimation problem induces structure in this linear system, and one can exploit this structure to obtain more efficient solutions of the nonlinear parameter estimation problem in parallel.

In previous work, we have developed a nonlinear interior-point algorithm with a parallel Schur-complement decomposition approach that is designed to allow parallel block-based linear algebra operations to exploit the problem structure. However, as the number of coupling variables increases, this approach becomes less competitive as the Schur-complement increases in size, and the number of backsolves required to form the Schur-complement increases. In our current work, we show that this bottleneck can be overcome and solve the Schur-complement equations using a preconditioned conjugate gradient method. This new algorithm avoids forming and factorizing the Schur-complement explicitly. The parallel scalability of this approach is demonstrated on randomly generated parameter estimation problems. Furthermore, significant parallel speedup is possible on two parameter estimation problems over large-scale water distribution networks. The performance of this approach is significantly affected by the choice of preconditioner. We test this technique with different preconditioning approaches and demonstrate that significant speed improvement is possible compared with previous approaches.

Finally, we have interfaced this parallel solver to the python-based PYOMO modeling language. This approach allows for straightforward formulation of the structured problem, and provides parallel evaluation of the problem objective, constraints, gradients, and hessians.