(607a) An Efficient Parallel Algorithm for Optimal Operation Under Uncertainty

Authors: 
Kang, J., Texas A&M University
Laird, C. D., Texas A&M University
Word, D., Texas A&M University



Nonlinear stochastic programming is an effective technique to formulate and solve optimal design and operations problems under uncertainty in many industries. These problems are often formulated as multi-scenario optimization problems, and in many cases, an optimal solution can be found using current off-the-shelf solvers. However, as the model rigor, system complexity increases, the size of these optimization problems often exceed the computational capabilities of a serial algorithm on a single workstation. Efficient solution demands the development of algorithms that allow parallel solution.

Nonlinear interior-point methods have proven to provide an effective framework for parallel solution of these problems. The dominant computational step in these algorithms is the solution of the linear augmented system, and the structure of this linear system remains constant from iteration to iteration, allowing for implementation of decomposition techniques. We have previously developed a Schur-complement decomposition technique that can exploit the multi-scenario problem structure in the linear solver and provide efficient parallel solution of these large-scale problems. With these explicit Schur-complement techniques, performance depends directly on the number of coupling or common variables. In many engineering design problems, the number of degrees of freedom is reasonably small, and these techniques can provide excellent parallel speedup. However, the computational expense of explicitly forming and solving the Schur-complement increases dramatically with the number of coupling variables. Furthermore, contrary to steady-state design problems, optimal operation problems include control or manipulated variables that depend on time. The time-discretized system can have significantly more degrees of freedom than a typical steady-state design problem, and explicit Schur-complement techniques may no longer be effective.

In this research, a new Schur-complement decomposition approach is presented that makes use of the preconditioned conjugate gradient method (an iterative technique) for solving the Schur-complement system. This implicit approach avoids explicit formation and factorization of the Schur-complement, overcoming the dominant computational bottleneck for problems with many common variables. The effectiveness is demonstrated on a dynamic optimization problem with uncertainty, and good weak and strong scaling are demonstrated.