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 first-stage
decision, not on data. This has shown to
lead to drastic compression rates (and
solution times) of above 80%,
which cannot be achieved with data
compression alone (see Figure 1). 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
(see Figure 2). 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.

Zavala, V. M. Clustering-Based Interior-Point
Strategies for Stochastic Programs,
Preprint, 2013. [pdf]

Zavala, V. M. Stochastic Optimal Control Model
for Natural Gas Network Operations.
Under Review, 2013. [pdf][code]

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. Natural gas line-pack
management with deterministic PDE
optimal control. Note
that 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 3. Natural gas line-pack
management with stochastic PDE optimal
control. Demand
can be sustained in all scenarios in a
stable manner.