
What is the optimal number of independent observations from which a sparse
Gaussian Graphical Model can be correctly recovered? Informationtheoretic
arguments provide a lower bound on the minimum number of samples necessary to
perfectly identify the support of any multivariate normal distribution as a
function of model parameters. For a model defined on a sparse graph with $p$
nodes, a maximum degree $d$ and minimum normalized edge strength $\kappa$, this
necessary number of samples scales at least as $d \log p/\kappa^2$. The sample
complexity requirements of existing methods for perfect graph reconstruction
exhibit dependency on additional parameters that do not enter in the lower
bound. The question of whether the lower bound is tight and achievable by a
polynomial time algorithm remains open. In this paper, we constructively answer
this question and propose an algorithm, termed DICE, whose sample complexity
matches the informationtheoretic lower bound up to a universal constant
factor. We also propose a related algorithm SLICE that has a slightly higher
sample complexity, but can be implemented as a mixed integer quadratic program
which makes it attractive in practice. Importantly, SLICE retains a critical
advantage of DICE in that its sample complexity only depends on quantities
present in the information theoretic lower bound. We anticipate that this
result will stimulate future search of computationally efficient sampleoptimal
algorithms.

In many engineered systems, optimization is used for decision making at
timescales ranging from realtime operation to longterm planning. This
process often involves solving similar optimization problems over and over
again with slightly modified input parameters, often under stringent time
requirements. We consider the problem of using the information available
through this solution process to directly learn the optimal solution as a
function of the input parameters, thus reducing the need of solving
computationally expensive largescale parametric programs in real time. Our
proposed method is based on learning relevant sets of active constraints, from
which the optimal solution can be obtained efficiently. Using active sets as
features preserves information about the physics of the system, enables more
interpretable learning policies, and inherently accounts for relevant safety
constraints. Further, the number of relevant active sets is finite, which make
them simpler objects to learn. To learn the relevant active sets, we propose a
streaming algorithm backed up by theoretical results. Through extensive
experiments on benchmarks of the Optimal Power Flow problem, we observe that
often only a few active sets are relevant in practice, suggesting that this is
the appropriate level of abstraction for a learning algorithm to target.

The optimal power flow problem plays an important role in the market clearing
and operation of electric power systems. However, with increasing uncertainty
from renewable energy operation, the optimal operating point of the system
changes more significantly in realtime. In this paper, we aim at developing
control policies that are able to track the optimal setpoint with high
probability. The approach is based on the observation that the OPF solution
corresponding to a certain uncertainty realization is a basic feasible
solution, which provides an affine control policy. The optimality of this basis
policy is restricted to uncertainty realizations that share the same set of
active constraints. We propose an ensemble control policy that combines several
basis policies to improve performance. Although the number of possible bases is
exponential in the size of the system, we show that only a few of them are
relevant to system operation. We adopt a statistical learning approach to learn
these important bases, and provide theoretical results that validate our
observations. For most systems, we observe that efficient ensemble policies
constructed using as few as ten bases, are able to obtain optimal solutions
with high probability.

Reconstruction of structure and parameters of an Ising model from binary
samples is a problem of practical importance in a variety of disciplines,
ranging from statistical physics and computational biology to image processing
and machine learning. The focus of the research community shifted towards
developing universal reconstruction algorithms which are both computationally
efficient and require the minimal amount of expensive data. We introduce a new
method, Interaction Screening, which accurately estimates the model parameters
using local optimization problems. The algorithm provably achieves perfect
graph structure recovery with an informationtheoretically optimal number of
samples, notably in the lowtemperature regime which is known to be the hardest
for learning. The efficacy of Interaction Screening is assessed through
extensive numerical tests on synthetic Ising models of various topologies with
different types of interactions, as well as on a real data produced by a DWave
quantum computer. This study shows that the Interaction Screening method is an
exact, tractable and optimal technique universally solving the inverse Ising
problem.

This paper outlines an optimization framework for choosing fast and reliable
control actions in a transmission grid emergency situation. We consider
contractual load shedding and generation redispatch as exemplary emergency
actions. To achieve computational efficiency and scalability, this novel
formulation of the robust corrective action optimization is stated in terms of
voltages and currents, as opposed to standard formulation in terms of power
flows and voltages. The currentvoltage formulation is natural for expressing
voltage and thermal transmission line constraints, and its major advantage is
in the linearity of the power flow equations. The complexity of the
currentvoltage formulation, which is mainly related to the transformation of
voltages and currents into active and reactive power injections, can be largely
avoided by stating the cost function directly in terms of currents and using
linearized or robust estimates for load and generation constraints. The paper
considers five different optimization problem formulations, including the full
currentvoltage formulation, as well as two convex and two linear approximation
to the problem. In a case study on an illustrative case study for the IEEE
RTS96 system, we demonstrate pros and cons of the different formulations based
on simulations for both normal and contingency operation.

As renewable wind energy penetration rates continue to increase, one of the
major challenges facing grid operators is the question of how to control
transmission grids in a reliable and a costefficient manner. The stochastic
nature of wind forces an alteration of traditional methods for solving
dayahead and lookahead unit commitment and dispatch. In particular, the
variability of wind generation increases the risk of unexpected overloads and
cascading events. To address these questions, we present an N1 Security and
ChanceConstrained Unit Commitment (SCCUC) that includes models of generation
reserves that respond to wind fluctuations and models of tertiary reserves that
respond to single component outages. We formulate the SCCUC as a mixedinteger,
secondorder cone problem that limits the probability of failure. We develop a
modified Benders decomposition algorithm to solve the problem to optimality and
present detailed case studies on the IEEE RTS96 threearea and the IEEE 300
NESTA test systems. The case studies assess the economic impacts of
contingencies and various degrees of wind power penetration and demonstrate the
effectiveness and scalability of the algorithm.

In this manuscript we review new ideas and first results on application of
the Graphical Models approach, originated from Statistical Physics, Information
Theory, Computer Science and Machine Learning, to optimization problems of
network flow type with additional constraints related to the physics of the
flow. We illustrate the general concepts on a number of enabling examples from
power system and natural gas transmission (continental scale) and distribution
(district scale) systems.

We consider the problem of learning the underlying graph of an unknown Ising
model on p spins from a collection of i.i.d. samples generated from the model.
We suggest a new estimator that is computationally efficient and requires a
number of samples that is nearoptimal with respect to previously established
informationtheoretic lowerbound. Our statistical estimator has a physical
interpretation in terms of "interaction screening". The estimator is consistent
and is efficiently implemented using convex optimization. We prove that with
appropriate regularization, the estimator recovers the underlying graph using a
number of samples that is logarithmic in the system size p and exponential in
the maximum couplingintensity and maximum nodedegree.

Higher shares of electricity generation from renewable energy sources and
market liberalization is increasing uncertainty in power systems operation. At
the same time, operation is becoming more flexible with improved control
systems and new technology such as phase shifting transformers (PSTs) and high
voltage direct current connections (HVDC). Previous studies have shown that the
use of corrective control in response to outages contributes to a reduction in
operating cost, while maintaining N1 security. In this work, we propose a
method to extend the use of corrective control of PSTs and HVDCs to react to
uncertainty. We characterize the uncertainty as continuous random variables,
and define the corrective control actions through affine control policies. This
allows us to efficiently model control reactions to a large number of
uncertainty sources. The control policies are then included in a chance
constrained optimal power flow formulation, which guarantees that the system
constraints are enforced with a desired probability. By applying an analytical
reformulation of the chance constraints, we obtain a secondorder cone problem
for which we develop an efficient solution algorithm. In a case study for the
IEEE 118 bus system, we show that corrective control for uncertainty leads to a
decrease in operational cost, while maintaining system security. Further, we
demonstrate the scalability of the method by solving the problem for the IEEE
300 bus and the Polish system test cases.

We derive conditions for the propagation of monotone ordering properties for
a class of nonlinear parabolic partial differential equation (PDE) systems on
metric graphs. For such systems, PDE equations with a general nonlinear
dissipation term define evolution on each edge, and balance laws create
KirchhoffNeumann boundary conditions at the vertices. Initial conditions, as
well as timevarying parameters in the coupling conditions at vertices, provide
an initial value problem (IVP). We first prove that ordering properties of the
solution to the IVP are preserved when the initial conditions and timevarying
coupling law parameters at vertices are appropriately ordered. In addition, we
prove that when monotone ordering is not preserved, the first crossing of
solutions occurs at a graph vertex. We consider the implications for robust
optimal control formulations and realtime monitoring involving uncertain
dynamic flows on networks, and discuss application to subsonic compressible
fluid flow with energy dissipation on physical networks.

Optimal power flow (OPF) is the central optimization problem in electric
power grids. Although solved routinely in the course of power grid operations,
it is known to be strongly NPhard in general, and weakly NPhard over tree
networks. In this paper, we formulate the optimal power flow problem over tree
networks as an inference problem over a treestructured graphical model where
the nodal variables are lowdimensional vectors. We adapt the standard dynamic
programming algorithm for inference over a treestructured graphical model to
the OPF problem. Combining this with an interval discretization of the nodal
variables, we develop an approximation algorithm for the OPF problem. Further,
we use techniques from constraint programming (CP) to perform interval
computations and adaptive bound propagation to obtain practically efficient
algorithms. Compared to previous algorithms that solve OPF with optimality
guarantees using convex relaxations, our approach is able to work for arbitrary
distribution networks and handle mixedinteger optimization problems. Further,
it can be implemented in a distributed messagepassing fashion that is scalable
and is suitable for "smart grid" applications like control of distributed
energy resources. We evaluate our technique numerically on several benchmark
networks and show that practical OPF problems can be solved effectively using
this approach.

Many products and innovations become wellknown and widely adopted through
the social interactions of individuals in a population. The Bass diffusion
model has been widely used to model the temporal evolution of adoption in such
social systems. In the model, the likelihood of a new adoption is proportional
to the number of previous adopters, implicitly assuming a global (or
homogeneous) interaction among all individuals in the network. Such global
interactions do not exist in many large social networks, however. Instead,
individuals typically interact with a small part of the larger population. To
quantify the growth rate (or equivalently the adoption timing) in networks with
limited interactions, we study a stochastic adoption process where the
likelihood that each individual adopts is proportional to the number of
adopters among the small group of persons he/she interacts with (and not the
entire population of adopters). When the underlying network of interactions is
a random $k$regular graph, we compute the sample path limit of the fraction of
adopters. We show the limit coincides with the solution of a differential
equation which can viewed as a generalization of the Bass diffusion model. When
the degree $k$ is bounded, we show the adoption curve differs significantly
from the one corresponds to the Bass diffusion model. In particular, the
adoption grows more slowly than what the Bass model projects. In addition, the
adoption curve is asymmetric, unlike that of the Bass diffusion model. Such
asymmetry has important consequences for the estimation of market potential.
Finally, we calculate the timing of early adoptions at finer scales, e.g.,
logarithmic in the population size.

We derive a monotonicity property for general, transient flows of a commodity
transferred throughout a network, where the flow is characterized by density
and mass flux dynamics on the edges with density continuity and mass balance
conditions at the nodes. The dynamics on each edge are represented by a general
system of partial differential equations that approximates subsonic
compressible fluid flow with energy dissipation. The transferred commodity may
be injected or withdrawn at any of the nodes, and is propelled throughout the
network by nodally located compressors. These compressors are controllable
actuators that provide a means to manipulate flows through the network, which
we therefore consider as a control system. A canonical problem requires
compressor control protocols to be chosen such that timevarying nodal
commodity withdrawal profiles are delivered and the density remains within
strict limits while an economic or operational cost objective is optimized. In
this manuscript, we consider the situation where each nodal commodity
withdrawal profile is uncertain, but is bounded within known maximum and
minimum timedependent limits. We introduce the monotone parameterized control
system property, and prove that general dynamic dissipative network flows
possess this characteristic under certain conditions. This property facilitates
very efficient formulation of optimal control problems for such systems in
which the solutions must be robust with respect to commodity withdrawal
uncertainty. We discuss several applications in which such control problems
arise and where monotonicity enables simplified characterization of system
behavior.

We consider the problem of reconstructing a low rank matrix from a subset of
its entries and analyze two variants of the socalled Alternating Minimization
algorithm, which has been proposed in the past. We establish that when the
underlying matrix has rank $r=1$, has positive bounded entries, and the graph
$\mathcal{G}$ underlying the revealed entries has bounded degree and diameter
which is at most logarithmic in the size of the matrix, both algorithms succeed
in reconstructing the matrix approximately in polynomial time starting from an
arbitrary initialization. We further provide simulation results which suggest
that the second algorithm which is based on the message passing type updates,
performs significantly better.

As renewable wind energy penetration rates continue to increase, one of the
major challenges facing grid operators is the question of how to control
transmission grids in a reliable and a costefficient manner. The stochastic
nature of wind forces an alteration of traditional methods for solving
dayahead and lookahead unit commitment and dispatch. In particular,
uncontrollable wind generation increases the risk of random component failures.
To address these questions, we present an N1 Security and ChanceConstrained
Unit Commitment (SCCUC) that includes the modeling of generation reserves that
respond to wind fluctuations and tertiary reserves to account for single
component outages. The basic formulation is reformulated as a mixedinteger
secondorder cone problem to limit the probability of failure. We develop three
different algorithms to solve the problem to optimality and present a detailed
case study on the IEEE RTS96 single area system. The case study assesses the
economic impacts due to contingencies and various degrees of wind power
penetration into the system and also corroborates the effectiveness of the
algorithms.

Over the past years, the share of electricity production from wind power
plants has increased to significant levels in several power systems across
Europe and the United States. In order to cope with the fluctuating and
partially unpredictable nature of renewable energy sources, transmission system
operators (TSOs) have responded by increasing their reserve capacity
requirements and by requiring wind power plants to be capable of providing
reserves or following active power setpoint signals. This paper addresses the
issue of efficiently incorporating these new types of wind power control in the
dayahead operational planning. We review the technical requirements the wind
power plants must fulfill, and propose a mathematical framework for modeling
wind power control. The framework is based on an optimal power flow formulation
with weighted chance constraints, which accounts for the uncertainty of wind
power forecasts and allows us to limit the risk of constraint violations. In a
case study based on the IEEE 118 bus system, we use the developed method to
assess the effectiveness of different types of wind power control in terms of
operational cost, system security and wind power curtailment.

The development of hydraulic fracturing technology has dramatically increased
the supply and lowered the cost of natural gas in the United States, driving an
expansion of natural gasfired generation capacity in several electrical
interconnections. Gasfired generators have the capability to ramp quickly and
are often utilized by grid operators to balance intermittency caused by wind
generation. The timevarying output of these generators results in timevarying
natural gas consumption rates that impact the pressure and linepack of the gas
network. As gas system operators assume nearly constant gas consumption when
estimating pipeline transfer capacity and for planning operations, such
fluctuations are a source of risk to their system. Here, we develop a new
method to assess this risk. We consider a model of gas networks with
consumption modeled through two components: forecasted consumption and small
spatiotemporarily varying consumption due to the gasfired generators being
used to balance wind. While the forecasted consumption is globally balanced
over longer time scales, the fluctuating consumption causes pressure
fluctuations in the gas system to grow diffusively in time with a diffusion
rate sensitive to the steady but spatiallyinhomogeneous forecasted
distribution of mass flow. To motivate our approach, we analyze the effect of
fluctuating gas consumption on a model of the Transco gas pipeline that extends
from the Gulf of Mexico to the Northeast of the United States.

We consider balanced flows in a natural gas transmission network and discuss
computationally hard problems such as establishing if solution of the
underlying nonlinear gas flow equations exists, if it is unique, and finding
the solution. Particular topologies, e.g. trees, are known to be easy to solve
based on a variational description of the gas flow equations, but these
approaches do not generalize. In this paper, we show that the gas flow problem
can be solved efficiently using the tools of monotone operator theory, provided
that we look for solution within certain monotonicity domains. We characterize
a family of monotonicity domains, described in terms of Linear Matrix
Inequalities (LMI) in the state variables, each containing at most one
solution. We also develop an efficient algorithm to choose a particular
monotonicity domain, for which the LMI based condition simplifies to a bound on
the flows. Performance of the technique is illustrated on exemplary gas
networks.

We consider a dissipative flow network that obeys the standard linear nodal
flow conservation, and where flows on edges are driven by potential difference
between adjacent nodes. We show that in the case when the flow is a
monotonically increasing function of the potential difference, solution of the
network flow equations is unique and can be equivalently recast as the solution
of a strictly convex optimization problem. We also analyze the maximum
throughput problem on such networks seeking to maximize the amount of flow that
can be delivered to the loads while satisfying bounds on the node potentials.
When the dissipation function is differentiable we develop a representation of
the maximum throughput problem in the form of a twice differentiable biconvex
optimization problem exploiting the variational representation of the network
flow equations. In the process we prove a special case of a certain
monotonicity property of dissipative flow networks. When the dissipation
function follows a power law with exponent greater than one, we suggest a mixed
integer convex relaxation of the maximum throughput problem. Finally, we
illustrate application of these general results to balanced, i.e. steady,
natural gas networks also validating the theory results through simulations on
a test case.

We consider general, steady, balanced flows of a commodity over a network
where an instance of the network flow is characterized by edge flows and nodal
potentials. Edge flows in and out of a node are assumed to be conserved, thus
representing standard network flow relations. The remaining freedom in the flow
distribution over the network is constrained by potentials so that the
difference of potentials at the head and the tail of an edge is expressed as a
nonlinear function of the edge flow. We consider networks with nodes divided
into three categories: sources that inject flows into the network for a certain
cost, terminals which buy the flow at a fixed price and "internal" customers
each withdrawing an uncertain amount of flow, which has a priority and thus it
is not priced. Our aim is to operate the network such that the profit, i.e.
amount of flow sold to terminals minus cost of injection, is maximized, while
maintaining the potentials within prescribed bounds. We also require that the
operating point is robust with respect to the uncertainty of customers'
withdrawals. In this setting we prove that potentials are monotonic functions
of the withdrawals. This observation enables us to replace in the maximum
profit optimization infinitely many nodal constraints, each representing a
particular value of withdrawal uncertainty, by only two constraints
representing the cases where all nodes with uncertainty consume their minimum
and maximum amounts respectively. We illustrate this general result on example
of the natural gas transmission network. In this enabling example gas
withdrawals by consumers are assumed uncertain, the potentials are gas
pressures squared, the potential drop functions are bilinear in the flow and
its intensity with an added tunable factor representing compression.

Due to the increasing amount of electricity generated from renewable sources,
uncertainty in power system operation will grow. This has implications for
tools such as Optimal Power Flow (OPF), an optimization problem widely used in
power system operations and planning, which should be adjusted to account for
this uncertainty. One way to handle the uncertainty is to formulate a Chance
Constrained OPF (CCOPF) which limits the probability of constraint violation
to a predefined value. However, existing CCOPF formulations and solutions are
not immune to drawbacks. On one hand, they only consider affine policies for
generation control, which are not always realistic and may be suboptimal. On
the other hand, the standard CCOPF formulations do not distinguish between
large and small violations, although those might carry significantly different
risk. In this paper, we introduce the Weighted CCOPF (WCCOPF) that can handle
general control policies while preserving convexity and allowing for efficient
computation. The weighted chance constraints account for the size of violations
through a weighting function, which assigns a higher risk to a higher
overloads. We prove that the problem remains convex for any convex weighting
function, and for very general generation control policies. In a case study, we
compare the performance of the new WCCOPF and the standard CCOPF and
demonstrate that WCCOPF effectively reduces the number of severe overloads.
Furthermore, we compare an affine generation control policy with a more general
policy, and show that the additional flexibility allow for a lower cost while
maintaining the same level of risk.

Modelbased compressed sensing refers to compressed sensing with extra
structure about the underlying sparse signal known a priori. Recent work has
demonstrated that both for deterministic and probabilistic models imposed on
the signal, this extra information can be successfully exploited to enhance
recovery performance. In particular, weighted $\ell_1$minimization with
suitable choice of weights has been shown to improve performance in the so
called nonuniform sparse model of signals. In this paper, we consider a full
generalization of the nonuniform sparse model with very mild assumptions. We
prove that when the measurements are obtained using a matrix with i.i.d
Gaussian entries, weighted $\ell_1$minimization successfully recovers the
sparse signal from its measurements with overwhelming probability. We also
provide a method to choose these weights for any general signal model from the
nonuniform sparse class of signal models.

Natural gas transmission pipelines are complex systems whose flow
characteristics are governed by challenging nonlinear physical behavior. These
pipelines extend over hundreds and even thousands of miles. Gas is typically
injected into the system at a constant rate, and a series of compressors are
distributed along the pipeline to boost the gas pressure to maintain system
pressure and throughput. These compressors consume a portion of the gas, and
one goal of the operator is to control the compressor operation to minimize
this consumption while satisfying pressure constraints at the gas load points.
The optimization of these operations is computationally challenging. Many
pipelines simply rely on the intuition and prior experience of operators to
make these decisions. Here, we present a new geometric programming approach for
optimizing compressor operation in natural gas pipelines. Using models of real
natural gas pipelines, we show that the geometric programming algorithm
consistently outperforms approaches that mimic existing state of practice.

We study the problem of the existence of a giant component in a random
multipartite graph. We consider a random multipartite graph with $p$ parts
generated according to a given degree sequence $n_i^{\mathbf{d}}(n)$ which
denotes the number of vertices in part $i$ of the multipartite graph with
degree given by the vector $\mathbf{d}$. We assume that the empirical
distribution of the degree sequence converges to a limiting probability
distribution. Under certain mild regularity assumptions, we characterize the
conditions under which, with high probability, there exists a component of
linear size. The characterization involves checking whether the
PerronFrobenius norm of the matrix of means of a certain associated
edgebiased distribution is greater than unity. We also specify the size of the
giant component when it exists. We use the exploration process of Molloy and
Reed combined with techniques from the theory of multidimensional GaltonWatson
processes to establish this result.

The property of spatial mixing and strong spatial mixing in spin systems has
been of interest because of its implications on uniqueness of Gibbs measures on
infinite graphs and efficient approximation of counting problems that are
otherwise known to be #P hard. In the context of coloring, strong spatial
mixing has been established for regular trees when $q \geq \alpha^{*} \Delta +
1$ where $q$ the number of colors, $\Delta$ is the degree and $\alpha^* =
1.763..$ is the unique solution to $xe^{1/x} = 1$. It has also been
established for bounded degree lattice graphs whenever $q \geq \alpha^* \Delta
 \beta$ for some constant $\beta$, where $\Delta$ is the maximum vertex degree
of the graph. The latter uses a technique based on recursively constructed
coupling of Markov chains whereas the former is based on establishing decay of
correlations on the tree. We establish strong spatial mixing of list colorings
on arbitrary bounded degree trianglefree graphs whenever the size of the list
of each vertex $v$ is at least $\alpha \Delta(v) + \beta$ where $\Delta(v)$ is
the degree of vertex $v$ and $\alpha > \alpha ^*$ and $\beta$ is a constant
that only depends on $\alpha$. We do this by proving the decay of correlations
via recursive contraction of the distance between the marginals measured with
respect to a suitably chosen error function.