Structured Solvers for Large-Scale Optimization back


Advances in algorithms for stochastic optimization (SO) and uncertainty quantification (UQ) are critical for the efficient design and real-time optimization of national infrastructures. Anticipating and mitigating uncertainty of weather, demands, and contingencies in a more integrated environment is necessary to address market volatility and prevent cascading failures that can ultimately lead to catastrophic shortages of supply. The integrated monitoring and optimization of infrastructures systems will generate huge amounts of data that cannot be possibly processed without exploiting underlying probabilistic structures (e.g., sparsity in spatio-temporal correlation patterns) and without exploiting the properties of the particular decision-making objective at hand (e.g., stochastic, PDEs). It is thus at the heart of our current research the philosophy that a structure-oriented and integrated approach to UQ/SO is necessary.


Sponsored by a Department of Energy (DOE) Early Career Award, we are currently developing new algorithms for UQ/SO that have a holistic view of the entire data-modeling-optimization process. A particular example of such algorithms is a new clustering-based interior-point strategy for stochastic programs in which scenarios are compressed based on their influence on the problem and not on the data alone. This has shown to lead to drastic compression rates (and solution times) of above 85%, which cannot be achieved with data compression alone. The compression is done adaptively, at the linear algebra level, by looking at the different contributions of the scenarios on the Schur complement.

We are also currently developing new interior-point algorithms for nonconvex structured optimization capable of dealing with complex multi-scale physics (typically involving large networks of partial differential equations) and stochastic components. These problems arise, for instance, from natural gas inventory (line-pack) management.  This requires of a redesign of existing algorithms and modeling environments capable of conveying problem structure down to the linear algebra kernels. In addition, hybrid linear algebra kernels need to be designed to exploit different structural facets. Problems with billions of variables are being targeted. 


Illinois Gas (red) and Electric (gray) networks.

KKT Matrix Structure of Gas Line-Pack Problem
  1. Cao, Y.; Laird. C.D. and Zavala, V. M. Clustering-Based Preconditioning for Stochastic Programs. Under Review,  2014. [pdf]
  2. Chiang, N. and Zavala, V. M. An Inertia-Free Filter Line-Search Algorithm for Large-Scale Nonlinear Programming. Under Review,  2014. [pdf]
  3. Zavala, V. M. Stochastic Optimal Control Model for Natural Gas Network Operations. Computers & Chemical Engineering,  64(1), pp. 103-113, 2014. [pdf][code]
  4. Chiang, N. Petra, C. and Zavala, V. M.  Structured Nonconvex Optimization of Large-Scale Energy Systems using PIPS-NLP. 18th Power Systems Computation Conference, 2014. [pdf]

Figure 1. Data for Wind Power Scenarios (left) and contribution of each scenario on first-stage decision (right). Note that even if the data are dispersed, the decision remains almost invariant to it. This is manifested in the formation of 3 strong clusters. This illustrates that much more compression potential exists than that suggested by the data alone.
Figure 2 (left). Natural gas line-pack management with deterministic PDE optimal control. The control policy sustains demand in low (left panel) and medium (center panel)  scenarios at the end of the pipeline (at 1500 km). The policy, however, cannot sustain demand in the high scenario (right panel). This manifests in high volatility of the flow profile with shocks propagating upstream the pipeline. 
Figure 2 (right). Natural gas line-pack management with stochastic PDE optimal control.
Demand can be sustained in all scenarios in a stable manner.