Structured
Solvers for Large-Scale Optimization back

Motivation:

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.

Research:

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
strategyfor 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.

Cao, Y.; Laird. C.D. and Zavala, V. M.
Clustering-Based Preconditioning
for Stochastic Programs. Under
Review, 2014. [pdf]

Chiang, N. and Zavala, V. M. An Inertia-Free Filter Line-Search
Algorithm for Large-Scale Nonlinear
Programming. Under Review,
2014. [pdf]

Zavala, V. M. Stochastic Optimal Control Model
for Natural Gas Network Operations.
Computers & Chemical Engineering,
64(1), pp. 103-113, 2014. [pdf][code]

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.