Catalog footprint

What is connected

84works
34topics
4close collaborators

Actions

Connect this record

Log in to claim

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

84 published item(s)

preprint2026arXiv

Analytic Bridge Diffusions for Controlled Path Generation

Most modern bridge-diffusion methods achieve finite-time transport by specifying an interpolation, Schrödinger-bridge, or stochastic-control objective and then learning the associated score or drift field with a neural network. In contrast, we identify a restricted but sufficiently broad and analytically solvable class in which the score, intermediate marginals, and protocol gradients are available in closed form without inner stochastic simulation loops and without neural networks in the optimization loop. We recast the classical linear--quadratic--Gaussian (LQG) stochastic-control structure as a transport problem of the Path Integral Diffusion (PID) type. In classical LQG control, linear dynamics, Gaussian noise, and quadratic costs lead to Riccati equations and closed-form optimal feedback. In LQ-GM-PID, we retain the linear--quadratic stochastic-control backbone, but replace terminal state regulation by a prescribed terminal probability density and allow both the initial and terminal laws to be Gaussian Mixtures (GM). Moreover, LQ-GM-PID turns bridge diffusion from a tool for terminal target matching alone into a tool for path shaping. We demonstrate this on a 2D corridor task, a 2D multi-entrance transport task, and a high-dimensional scaling study with $d=32$ and $M=16$ Gaussian-mixture terminal modes, all with sub-50\,ms analytic precompute on a laptop. We position LQ-GM-PID as an analytically solvable reference model for the state-of-the-art neural bridge-diffusion and generative-transport methods: a controlled setting in which neural approximations, score estimates, path-shaping objectives, and protocol-learning procedures can be tested against exact quantities.

preprint2022arXiv

Lagrangian Large Eddy Simulations via Physics Informed Machine Learning

High Reynolds Homogeneous Isotropic Turbulence is fully described within the Navier-Stokes (NS) equations, which are notoriously difficult to solve numerically. Engineers, interested primarily in describing turbulence at a reduced range of resolved scales, have designed heuristics, known as Large Eddy Simulation (LES). LES is described in terms of the temporally evolving Eulerian velocity field defined over a spatial grid with the mean-spacing correspondent to the resolved scale. This classic Eulerian LES depends on assumptions about effects of sub-grid scales on the resolved scales. Here, we take an alternative approach and design novel LES heuristics stated in terms of Lagrangian particles moving with the flow. Our Lagrangian LES, thus L-LES, is described by equations generalizing the weakly compressible Smoothed Particle Hydrodynamics formulation with extended parametric and functional freedom, which is then resolved via Machine Learning training on Lagrangian data from Direct Numerical Simulations of the NS equations. The L-LES model includes physics-informed parameterization and functional form, by combining physics-based parameters and physics-inspired Neural Networks to describe the evolution of turbulence within the resolved range of scales. The sub-grid scale contributions are modeled separately with physical constraints to account for the effects from un-resolved scales. We build the resulting model under the Differentiable Programming framework to facilitate efficient training. We experiment with loss functions of different types, including physics-informed ones accounting for statistics of Lagrangian particles. We show that our Lagrangian LES model is capable of reproducing Eulerian and unique Lagrangian turbulence structures and statistics over a range of turbulent Mach numbers.

preprint2022arXiv

Machine Learning for Electricity Market Clearing

This paper seeks to design a machine learning twin of the optimal power flow (OPF) optimization, which is used in market-clearing procedures by wholesale electricity markets. The motivation for the proposed approach stems from the need to obtain the digital twin, which is much faster than the original, while also being sufficiently accurate and producing consistent generation dispatches and locational marginal prices (LMPs), which are primal and dual solutions of the OPF optimization, respectively. Availability of market-clearing tools based on this approach will enable computationally tractable evaluation of multiple dispatch scenarios under a given unit commitment. Rather than direct solution of OPF, the Karush-Kuhn-Tucker (KKT) conditions for the OPF problem in question may be written, and in parallel the LMPs of generators and loads may be expressed in terms of the OPF Lagrangian multipliers. Also, taking advantage of the practical fact that many of the Lagrangian multipliers associated with lines will be zero (thermal limits are not binding), we build and train an ML scheme which maps flexible resources (loads and renewables) to the binding lines, and supplement it with an efficient power-grid aware linear map to optimal dispatch and LMPs. The scheme is validated and illustrated on IEEE models. We also report a trade of analysis between quality of the reconstruction and number of samples needed to train the model.

preprint2022arXiv

Prediction and Prevention of Pandemics via Graphical Model Inference and Convex Programming

Hard-to-predict bursts of COVID-19 pandemic revealed significance of statistical modeling which would resolve spatio-temporal correlations over geographical areas, for example spread of the infection over a city with census tract granularity. In this manuscript, we provide algorithmic answers to the following two inter-related public health challenges. (1) Inference Challenge: assuming that there are $N$ census blocks (nodes) in the city, and given an initial infection at any set of nodes, what is the probability for a subset of census blocks to become infected by the time the spread of the infection burst is stabilized? (2) Prevention Challenge: What is the minimal control action one can take to minimize the infected part of the stabilized state footprint? To answer the challenges, we build a Graphical Model of pandemic of the attractive Ising (pair-wise, binary) type, where each node represents a census track and each edge factor represents the strength of the pairwise interaction between a pair of nodes. We show that almost all attractive Ising Models on dense graphs result in either of the two modes for the most probable state: either all nodes which were not infected initially became infected, or all the initially uninfected nodes remain uninfected. This bi-modal solution of the Inference Challenge allows us to re-state the Prevention Challenge as the following tractable convex programming: for the bare Ising Model with pair-wise and bias factors representing the system without prevention measures, such that the MAP state is fully infected for at least one of the initial infection patterns, find the closest, in $l_1$ norm, set of factors resulting in all the MAP states of the Ising model, with the optimal prevention measures applied, to become safe.

preprint2022arXiv

Statistical Mechanics of Thermostatically Controlled Multi-Zone Buildings

We study the collective phenomena and constraints associated with the aggregation of individual cooling units from a statistical mechanics perspective. These units are modelled as Thermostatically Controlled Loads (TCLs) and represent zones in a large commercial or residential building. Their energy input is centralized and controlled by a collective unit -- the Air Handling Unit (AHU) -- delivering cool air to all TCLs, thereby coupling them together. Aiming to identify representative qualitative features of the AHU-to-TCL coupling, we build a realistic but also sufficiently simple model and analyze it in two distinct regimes: the Constant Supply Temperature (CST) and the Constant Power Input (CPI) regimes. In both cases, we center our analysis on the relaxation dynamics of individual TCL temperatures to a statistically steady state. We observe that while the dynamics are relatively fast in the CST regime, resulting in all TCLs evolving around the control setpoint, the CPI regime reveals emergence of a \emph{bi-modal probability distribution and two, possibly strongly separated, time scales}. We observe that the two modes in the CPI regime are associated with all TCLs being in the same low and high-temperature states, respectively, with occasional (and therefore possibly rare) collective transition between the modes akin in the Kramer's phenomenon of statistical physics. To the best of our knowledge, this phenomenon was overlooked in the context of the multi-zone energy building engineering, even thought it has direct implications on the operations of centralized cooling systems in buildings. It teaches us that a balance needs to be struck between occupational comfort -- related to variations in the individual temperatures -- and power output predictability -- the main focus of the DR schemes.

preprint2022arXiv

Towards Model Reduction for Power System Transients with Physics-Informed PDE

This manuscript reports the first step towards building a robust and efficient model reduction methodology to capture transient dynamics in a transmission level electric power system. Such dynamics is normally modeled on seconds-to-tens-of-seconds time scales by the so-called swing equations, which are ordinary differential equations defined on a spatially discrete model of the power grid. Following Seymlyen (1974) and Thorpe, Seyler, and Phadke (1999), we suggest to map the swing equations onto a linear, inhomogeneous Partial Differential Equation (PDE) of parabolic type in two space and one time dimensions with time-independent coefficients and properly defined boundary conditions. We illustrate our method on the synchronous transmission grid of continental Europe. We show that, when properly coarse-grained, i.e., with the PDE coefficients and source terms extracted from a spatial convolution procedure of the respective discrete coefficients in the swing equations, the resulting PDE reproduces faithfully and efficiently the original swing dynamics. We finally discuss future extensions of this work, where the presented PDE-based modeling will initialize a physics-informed machine learning approach for real-time modeling, $n-1$ feasibility assessment and transient stability analysis of power systems.

preprint2021arXiv

Message Passing Descent for Efficient Machine Learning

We propose a new iterative optimization method for the {\bf Data-Fitting} (DF) problem in Machine Learning, e.g. Neural Network (NN) training. The approach relies on {\bf Graphical Model} (GM) representation of the DF problem, where variables are fitting parameters and factors are associated with the Input-Output (IO) data. The GM results in the {\bf Belief Propagation} Equations considered in the {\bf Large Deviation Limit} corresponding to the practically important case when the number of the IO samples is much larger than the number of the fitting parameters. We suggest the {\bf Message Passage Descent} algorithm which relies on the piece-wise-polynomial representation of the model DF function. In contrast with the popular gradient descent and related algorithms our MPD algorithm rely on analytic (not automatic) differentiation, while also (and most importantly) it descents through the rugged DF landscape by \emph{making non local updates of the parameters} at each iteration. The non-locality guarantees that the MPD is not trapped in the local-minima, therefore resulting in better performance than locally-updated algorithms of the gradient-descent type. We illustrate superior performance of the algorithm on a Feed-Forward NN with a single hidden layer and a piece-wise-linear activation function.

preprint2021arXiv

Neural Particle Image Velocimetry

In the past decades, great progress has been made in the field of optical and particle-based measurement techniques for experimental analysis of fluid flows. Particle Image Velocimetry (PIV) technique is widely used to identify flow parameters from time-consecutive snapshots of particles injected into the fluid. The computation is performed as post-processing of the experimental data via proximity measure between particles in frames of reference. However, the post-processing step becomes problematic as the motility and density of the particles increases, since the data emerges in extreme rates and volumes. Moreover, existing algorithms for PIV either provide sparse estimations of the flow or require large computational time frame preventing from on-line use. The goal of this manuscript is therefore to develop an accurate on-line algorithm for estimation of the fine-grained velocity field from PIV data. As the data constitutes a pair of images, we employ computer vision methods to solve the problem. In this work, we introduce a convolutional neural network adapted to the problem, namely Volumetric Correspondence Network (VCN) which was recently proposed for the end-to-end optical flow estimation in computer vision. The network is thoroughly trained and tested on a dataset containing both synthetic and real flow data. Experimental results are analyzed and compared to that of conventional methods as well as other recently introduced methods based on neural networks. Our analysis indicates that the proposed approach provides improved efficiency also keeping accuracy on par with other state-of-the-art methods in the field. We also verify through a-posteriori tests that our newly constructed VCN schemes are reproducing well physically relevant statistics of velocity and velocity gradients.

preprint2021arXiv

Physics-Informed Graphical Neural Network for Parameter & State Estimations in Power Systems

Parameter Estimation (PE) and State Estimation (SE) are the most wide-spread tasks in the system engineering. They need to be done automatically, fast and frequently, as measurements arrive. Deep Learning (DL) holds the promise of tackling the challenge, however in so far, as PE and SE in power systems is concerned, (a) DL did not win trust of the system operators because of the lack of the physics of electricity based, interpretations and (b) DL remained illusive in the operational regimes were data is scarce. To address this, we present a hybrid scheme which embeds physics modeling of power systems into Graphical Neural Networks (GNN), therefore empowering system operators with a reliable and explainable real-time predictions which can then be used to control the critical infrastructure. To enable progress towards trustworthy DL for PE and SE, we build a physics-informed method, named Power-GNN, which reconstructs physical, thus interpretable, parameters within Effective Power Flow (EPF) models, such as admittances of effective power lines, and NN parameters, representing implicitly unobserved elements of the system. In our experiments, we test the Power-GNN on different realistic power networks, including these with thousands of loads and hundreds of generators. We show that the Power-GNN outperforms vanilla NN scheme unaware of the EPF physics.

preprint2021arXiv

Super-relaxation of space-time-quantized ensemble of energy loads to curtail their synchronization after demand response perturbation

Ensembles of thermostatically controlled loads (TCL) provide a significant demand response reserve for the system operator to balance power grids. However, this also results in the parasitic synchronization of individual devices within the ensemble leading to long post-demand-response oscillations in the integrated energy consumption of the ensemble. The synchronization is eventually destructed by fluctuations, thus leading to the (pre-demand response) steady state; however, this natural desynchronization, or relaxation to a statistically steady state, is too long. A resolution of this problem consists in measuring the ensemble's instantaneous consumption and using it as a feedback to stochastic switching of the ensemble's devices between on- and off- states. A simplified continuous-time model showed that carefully tuned nonlinear feedback results in a fast (super-) relaxation of the ensemble energy consumption. Since both state information and control signals are discrete, the actual TCL devices operation is space-time quantized, and this must be considered for realistic TCL ensemble modelling. Here, assuming that states are characterized by indoor temperature (quantifying comfort) and air conditioner regime (on, off), we construct a discrete model based on the probabilistic description of state transitions. We demonstrate that super-relaxation holds in such a more realistic setting, and that while it is stable against randomness in the stochastic matrix of the quantized model, it remains sensitive to the time discretization scheme. Aiming to achieve a balance between super-relaxation and customer's comfort, we analyze the dependence of super-relaxation on details of the space-time quantization, and provide a simple analytical criterion to avoid undesirable oscillations in consumption.

preprint2020arXiv

A Hierarchical Approach to Multi-Energy Demand Response: From Electricity to Multi-Energy Applications

Due to proliferation of energy efficiency measures and availability of the renewable energy resources, traditional energy infrastructure systems (electricity, heat, gas) can no longer be operated in a centralized manner under the assumption that consumer behavior is inflexible, i.e. cannot be adjusted in return for an adequate incentive. To allow for a less centralized operating paradigm, consumer-end perspective and abilities should be integrated in current dispatch practices and accounted for in switching between different energy sources not only at the system but also at the individual consumer level. Since consumers are confined within different built environments, this paper looks into an opportunity to control energy consumption of an aggregation of many residential, commercial and industrial consumers, into an ensemble. This ensemble control becomes a modern demand response contributor to the set of modeling tools for multi-energy infrastructure systems.

preprint2020arXiv

Data-Driven Learning and Load Ensemble Control

Demand response (DR) programs aim to engage distributed small-scale flexible loads, such as thermostatically controllable loads (TCLs), to provide various grid support services. Linearly Solvable Markov Decision Process (LS-MDP), a variant of the traditional MDP, is used to model aggregated TCLs. Then, a model-free reinforcement learning technique called Z-learning is applied to learn the value function and derive the optimal policy for the DR aggregator to control TCLs. The learning process is robust against uncertainty that arises from estimating the passive dynamics of the aggregated TCLs. The efficiency of this data-driven learning is demonstrated through simulations on Heating, Cooling & Ventilation (HVAC) units in a testbed neighborhood of residential houses.

preprint2020arXiv

Embedding Hard Physical Constraints in Neural Network Coarse-Graining of 3D Turbulence

In the recent years, deep learning approaches have shown much promise in modeling complex systems in the physical sciences. A major challenge in deep learning of PDEs is enforcing physical constraints and boundary conditions. In this work, we propose a general framework to directly embed the notion of an incompressible fluid into Convolutional Neural Networks, and apply this to coarse-graining of turbulent flow. These physics-embedded neural networks leverage interpretable strategies from numerical methods and computational fluid dynamics to enforce physical laws and boundary conditions by taking advantage the mathematical properties of the underlying equations. We demonstrate results on three-dimensional fully-developed turbulence, showing that this technique drastically improves local conservation of mass, without sacrificing performance according to several other metrics characterizing the fluid flow.

preprint2020arXiv

Gauges, Loops, and Polynomials for Partition Functions of Graphical Models

Graphical models represent multivariate and generally not normalized probability distributions. Computing the normalization factor, called the partition function, is the main inference challenge relevant to multiple statistical and optimization applications. The problem is of an exponential complexity with respect to the number of variables. In this manuscript, aimed at approximating the PF, we consider Multi-Graph Models where binary variables and multivariable factors are associated with edges and nodes, respectively, of an undirected multi-graph. We suggest a new methodology for analysis and computations that combines the Gauge Function technique with the technique from the field of real stable polynomials. We show that the Gauge Function has a natural polynomial representation in terms of gauges/variables associated with edges of the multi-graph. Moreover, it can be used to recover the Partition Function through a sequence of transformations allowing appealing algebraic and graphical interpretations. Algebraically, one step in the sequence consists in application of a differential operator over gauges associated with an edge. Graphically, the sequence is interpreted as a repetitive elimination of edges resulting in a sequence of models on decreasing in size graphs with the same Partition Function. Even though complexity of computing factors in the sequence models grow exponentially with the number of eliminated edges, polynomials associated with the new factors remain bi-stable if the original factors have this property. Moreover, we show that Belief Propagation estimations in the sequence do not decrease, each low-bounding the Partition Function.

preprint2020arXiv

Graphical Models in Meshed Distribution Grids: Topology estimation, change detection and limitations

Graphical models are a succinct way to represent the structure in probability distributions. This article analyzes the graphical model of nodal voltages in non-radial power distribution grids. Using algebraic and structural properties of graphical models, algorithms exactly determining topology and detecting line changes for distribution grids are presented along with their theoretical limitations. We show that if distribution grids have cycles/loops of size greater than three, then nodal voltages are sufficient for efficient topology estimation without additional assumptions on system parameters. In contrast, line failure or change detection using nodal voltages does not require any structural assumption. Under noisy measurements, we provide the first non-trivial bounds on the maximum noise that the system can tolerate for asymptotically correct topology recovery. The performance of the designed algorithms is validated with nonlinear AC power flow samples generated by Matpower on test grids, including scenarios with injection correlations and system noise.

preprint2020arXiv

Joint Estimation of Topology and Injection Statistics in Distribution Grids with Missing Nodes

Optimal operation of distribution grid resources relies on accurate estimation of its state and topology. Practical estimation of such quantities is complicated by the limited presence of real-time meters. This paper discusses a theoretical framework to jointly estimate the operational topology and statistics of injections in radial distribution grids under limited availability of nodal voltage measurements. In particular we show that our proposed algorithms are able to provably learn the exact grid topology and injection statistics at all unobserved nodes as long as they are not adjacent. The algorithm design is based on novel ordered trends in voltage magnitude fluctuations at node groups, that are independently of interest for radial physical flow networks. The complexity of the designed algorithms is theoretically analyzed and their performance validated using both linearized and non-linear AC power flow samples in test distribution grids.

preprint2020arXiv

Learning with End-Users in Distribution Grids: Topology and Parameter Estimation

Efficient operation of distribution grids in the smart-grid era is hindered by the limited presence of real-time nodal and line meters. In particular, this prevents the easy estimation of grid topology and associated line parameters that are necessary for control and optimization efforts in the grid. This paper studies the problems of topology and parameter estimation in radial balanced distribution grids where measurements are restricted to only the leaf nodes and all intermediate nodes are unobserved/hidden. To this end, we propose two exact learning algorithms that use balanced voltage and injection measured only at the end-users. The first algorithm requires time-stamped voltage samples, statistics of nodal power injections and permissible line impedances to recover the true topology. The second and improved algorithm requires only time-stamped voltage and complex power samples to recover both the true topology and impedances without any additional input (e.g., number of grid nodes, statistics of injections at hidden nodes, permissible line impedances). We prove the correctness of both learning algorithms for grids where unobserved buses/nodes have a degree greater than three and discuss extensions to regimes where that assumption doesn't hold. Further, we present computational and, more importantly, the sample complexity of our proposed algorithm for joint topology and impedance estimation. We illustrate the performance of the designed algorithms through numerical experiments on the IEEE and custom power distribution models.

preprint2020arXiv

MCMC assisted by Belief Propagation

Markov Chain Monte Carlo (MCMC) and Belief Propagation (BP) are the most popular algorithms for computational inference in Graphical Models (GM). In principle, MCMC is an exact probabilistic method which, however, often suffers from exponentially slow mixing. In contrast, BP is a deterministic method, which is typically fast, empirically very successful, however in general lacking control of accuracy over loopy graphs. In this paper, we introduce MCMC algorithms correcting the approximation error of BP, i.e., we provide a way to compensate for BP errors via a consecutive BP-aware MCMC. Our framework is based on the Loop Calculus (LC) approach which allows expressing the BP error as a sum of weighted generalized loops. Although the full series is computationally intractable, it is known that a truncated series, summing up all 2-regular loops, is computable in polynomial-time for planar pair-wise binary GMs and it also provides a highly accurate approximation empirically. Motivated by this, we first propose a polynomial-time approximation MCMC scheme for the truncated series of general (non-planar) pair-wise binary models. Our main idea here is to use the Worm algorithm, known to provide fast mixing in other (related) problems, and then design an appropriate rejection scheme to sample 2-regular loops. Furthermore, we also design an efficient rejection-free MCMC scheme for approximating the full series. The main novelty underlying our design is in utilizing the concept of cycle basis, which provides an efficient decomposition of the generalized loops. In essence, the proposed MCMC schemes run on transformed GM built upon the non-trivial BP solution, and our experiments show that this synthesis of BP and MCMC outperforms both direct MCMC and bare BP schemes.

preprint2020arXiv

Mean Field Control for Efficient Mixing of Energy Loads

We pose an engineering challenge of controlling an Ensemble of Energy Devices via coordinated, implementation-light and randomized on/off switching as a problem in Non-Equilibrium Statistical Mechanics. We show that Mean Field Control} with nonlinear feedback on the cumulative consumption, assumed available to the aggregator via direct physical measurements of the energy flow, allows the ensemble to recover from its use in the Demand Response regime, i.e. transition to a statistical steady state, significantly faster than in the case of the fixed feedback. Moreover when the nonlinearity is sufficiently strong, one observes the phenomenon of "super-relaxation" -- where the total instantaneous energy consumption of the ensemble transitions to the steady state much faster than the underlying probability distribution of the devices over their state space, while also leaving almost no devices outside of the comfort zone.

preprint2018arXiv

Bucket Renormalization for Approximate Inference

Probabilistic graphical models are a key tool in machine learning applications. Computing the partition function, i.e., normalizing constant, is a fundamental task of statistical inference but it is generally computationally intractable, leading to extensive study of approximation methods. Iterative variational methods are a popular and successful family of approaches. However, even state of the art variational methods can return poor results or fail to converge on difficult instances. In this paper, we instead consider computing the partition function via sequential summation over variables. We develop robust approximate algorithms by combining ideas from mini-bucket elimination with tensor network and renormalization group methods from statistical physics. The resulting "convergence-free" methods show good empirical performance on both synthetic and real-world benchmark models, even for difficult instances.

preprint2016arXiv

Chance Constrained Optimal Power Flow with Curtailment and Reserves from Wind Power Plants

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 set-point signals. This paper addresses the issue of efficiently incorporating these new types of wind power control in the day-ahead 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.

preprint2016arXiv

Estimating Distribution Grid Topologies: A Graphical Learning based Approach

Distribution grids represent the final tier in electric networks consisting of medium and low voltage lines that connect the distribution substations to the end-users. Traditionally, distribution networks have been operated in a radial topology that may be changed from time to time. Due to absence of a significant number of real-time line monitoring devices in the distribution grid, estimation of the topology is a problem critical for its observability and control. This paper develops a novel graphical learning based approach to estimate the radial operational grid structure using voltage measurements collected from the grid loads. The learning algorithm is based on conditional independence tests for continuous variables over chordal graphs and has wide applicability. It is proven that the scheme can be used for several power flow laws (DC or AC approximations) and more importantly is independent of the specific probability distribution controlling individual bus power usage. The complexity of the algorithm is discussed and its performance is demonstrated by simulations on distribution test cases.

preprint2016arXiv

Graphical Models for Optimal Power Flow

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 NP-hard in general, and weakly NP-hard over tree networks. In this paper, we formulate the optimal power flow problem over tree networks as an inference problem over a tree-structured graphical model where the nodal variables are low-dimensional vectors. We adapt the standard dynamic programming algorithm for inference over a tree-structured 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 mixed-integer optimization problems. Further, it can be implemented in a distributed message-passing 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.

preprint2016arXiv

Learning Topology of Distribution Grids using only Terminal Node Measurements

Distribution grids include medium and low voltage lines that are involved in the delivery of electricity from substation to end-users/loads. A distribution grid is operated in a radial/tree-like structure, determined by switching on or off lines from an underling loopy graph. Due to the presence of limited real-time measurements, the critical problem of fast estimation of the radial grid structure is not straightforward. This paper presents a new learning algorithm that uses measurements only at the terminal or leaf nodes in the distribution grid to estimate its radial structure. The algorithm is based on results involving voltages of node triplets that arise due to the radial structure. The polynomial computational complexity of the algorithm is presented along with a detailed analysis of its working. The most significant contribution of the approach is that it is able to learn the structure in certain cases where available measurements are confined to only half of the nodes. This represents learning under minimum permissible observability. Performance of the proposed approach in learning structure is demonstrated by experiments on test radial distribution grids.

preprint2016arXiv

Learning Topology of the Power Distribution Grid with and without Missing Data

Distribution grids refer to the part of the power grid that delivers electricity from substations to the loads. Structurally a distribution grid is operated in one of several radial/tree-like topologies that are derived from an original loopy grid graph by opening switches on some lines. Due to limited presence of real-time switch monitoring devices, the operating structure needs to be estimated indirectly. This paper presents a new learning algorithm that uses only nodal voltage measurements to determine the operational radial structure. The algorithm is based on the key result stating that the correct operating structure is the optimal solution of the minimum-weight spanning tree problem over the original loopy graph where weights on all permissible edges/lines (open or closed) is the variance of nodal voltage difference at the edge ends. Compared to existing work, this spanning tree based approach has significantly lower complexity as it does not require information on line parameters. Further, a modified learning algorithm is developed for cases when the input voltage measurements are limited to only a subset of the total grid nodes. Performance of the algorithms (with and without missing data) is demonstrated by experiments on test cases.

preprint2016arXiv

Linear PDEs and eigenvalue problems corresponding to ergodic stochastic optimization problems on compact manifolds

We consider long term average or `ergodic' optimal control poblems with a special structure: Control is exerted in all directions and the control costs are proportional to the square of the norm of the control field with respect to the metric induced by the noise. The long term stochastic dynamics on the manifold will be completely characterized by the long term density $ρ$ and the long term current density $J$. As such, control problems may be reformulated as variational problems over $ρ$ and $J$. We discuss several optimization problems: the problem in which both $ρ$ and $J$ are varied freely, the problem in which $ρ$ is fixed and the one in which $J$ is fixed. These problems lead to different kinds of operator problems: linear PDEs in the first two cases and a nonlinear PDE in the latter case. These results are obtained through through variational principle using infinite dimensional Lagrange multipliers. In the case where the initial dynamics are reversible we obtain the result that the optimally controlled diffusion is also symmetrizable. The particular case of constraining the dynamics to be reversible of the optimally controlled process leads to a linear eigenvalue problem for the square root of the density process.

preprint2016arXiv

Monotone Order Properties for Control of Nonlinear Parabolic PDE on Graphs

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 Kirchhoff-Neumann boundary conditions at the vertices. Initial conditions, as well as time-varying 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 time-varying 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 real-time monitoring involving uncertain dynamic flows on networks, and discuss application to subsonic compressible fluid flow with energy dissipation on physical networks.

preprint2016arXiv

Monotonicity of Actuated Flows on Dissipative Transport Networks

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 time-varying 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 time-dependent 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.

preprint2016arXiv

Operator Splitting Method for Simulation of Dynamic Flows in Natural Gas Pipeline Networks

We develop an operator splitting method to simulate flows of isothermal compressible natural gas over transmission pipelines. The method solves a system of nonlinear hyperbolic partial differential equations (PDEs) of hydrodynamic type for mass flow and pressure on a metric graph, where turbulent losses of momentum are modeled by phenomenological Darcy-Weisbach friction. Mass flow balance is maintained through the boundary conditions at the network nodes, where natural gas is injected or withdrawn from the system. Gas flow through the network is controlled by compressors boosting pressure at the inlet of the adjoint pipe. Our operator splitting numerical scheme is unconditionally stable and it is second order accurate in space and time. The scheme is explicit, and it is formulated to work with general networks with loops. We test the scheme over range of regimes and network configurations, also comparing its performance with performance of two other state of the art implicit schemes.

preprint2016arXiv

Tractable Structure Learning in Radial Physical Flow Networks

Physical Flow Networks are different infrastructure networks that allow the flow of physical commodities through edges between its constituent nodes. These include power grid, natural gas transmission network, water pipelines etc. In such networks, the flow on each edge is characterized by a function of the nodal potentials on either side of the edge. Further the net flow in and out of each node is conserved. Learning the structure and state of physical networks is necessary for optimal control as well as to quantify its privacy needs. We consider radial flow networks and study the problem of learning the operational network from a loopy graph of candidate edges using statistics of nodal potentials. Based on the monotonic properties of the flow functions, the key result in this paper shows that if variance of the difference of nodal potentials is used to weight candidate edges, the operational edges form the minimum spanning tree in the loopy graph. Under realistic conditions on the statistics of nodal injection (consumption or production), we provide a greedy structure learning algorithm with quasilinear computational complexity in the number of candidate edges in the network. Our learning framework is very general due to two significant attributes. First it is independent of the specific marginal distributions of nodal potentials and only uses order properties in their second moments. Second, the learning algorithm is agnostic to exact flow functions that relate edge flows to corresponding potential differences and is applicable for a broad class of networks with monotonic flow functions. We demonstrate the efficacy of our work through realistic simulations on diverse physical flow networks and discuss possible extensions of our work to other regimes.

preprint2015arXiv

A differential analysis of the power flow equations

The AC power flow equations are fundamental in all aspects of power systems planning and operations. They are routinely solved using Newton-Raphson like methods. However, there is little theoretical understanding of when these algorithms are guaranteed to find a solution of the power flow equations or how long they may take to converge. Further, it is known that in general these equations have multiple solutions and can exhibit chaotic behavior. In this paper, we show that the power flow equations can be solved efficiently provided that the solution lies in a certain set. We introduce a family of convex domains, characterized by Linear Matrix Inequalities, in the space of voltages such that there is at most one power flow solution in each of these domains. Further, if a solution exists in one of these domains, it can be found efficiently, and if one does not exist, a certificate of non-existence can also be obtained efficiently. The approach is based on the theory of monotone operators and related algorithms for solving variational inequalities involving monotone operators. We validate our approach on IEEE test networks and show that practical power flow solutions lie within an appropriately chosen convex domain.

preprint2015arXiv

Convexity of Energy-Like Functions: Theoretical Results and Applications to Power System Operations

Power systems are undergoing unprecedented transformations with the incorporation of larger amounts of renewable energy sources, distributed generation and demand response. All these changes, while potentially making power grids more responsive, efficient and resilient, also pose significant implementation challenges. In particular, operating the new power grid will require new tools and algorithms capable of predicting if the current state of the system is operationally safe. In this paper we study and generalize the so-called energy function as a tool to design algorithms to test if a high-voltage power transmission system is within the allowed operational limits. In the past the energy function technique was utilized primarily to access the power system transient stability. In this manuscript, we take a new look at energy functions and focus on an aspect that has previously received little attention: Convexity. We characterize the domain of voltage magnitudes and phases within which the energy function is convex. We show that the domain of the energy function convexity is sufficiently large to include most operationally relevant and practically interesting cases. We show how the energy function convexity can be used to analyze power flow equations, e.g. to certify solution uniqueness or non-existence within the domain of convexity. This and other useful features of the generalized energy function are described and illustrated on IEEE 14 and 118 bus models.

preprint2015arXiv

Extreme value statistics of work done in stretching a polymer in a gradient flow

We analyze the statistics of work generated by a gradient flow to stretch a nonlinear polymer. We obtain the Large Deviation Function (LDF) of the work in the full range of appropriate parameters by combining analytical and numerical tools. The LDF shows two distinct asymptotes: "near tails" are linear in work and dominated by coiled polymer configurations, while "far tails" are quadratic in work and correspond to preferentially fully stretched polymers. We find the extreme value statistics of work for several singular elastic potentials, as well as the mean and the dispersion of work near the coil-stretch transition. The dispersion shows a maximum at the transition.

preprint2015arXiv

Learning Planar Ising Models

Inference and learning of graphical models are both well-studied problems in statistics and machine learning that have found many applications in science and engineering. However, exact inference is intractable in general graphical models, which suggests the problem of seeking the best approximation to a collection of random variables within some tractable family of graphical models. In this paper, we focus on the class of planar Ising models, for which exact inference is tractable using techniques of statistical physics. Based on these techniques and recent methods for planarity testing and planar embedding, we propose a simple greedy algorithm for learning the best planar Ising model to approximate an arbitrary collection of binary random variables (possibly from sample data). Given the set of all pairwise correlations among variables, we select a planar graph and optimal planar Ising model defined on this graph to best approximate that set of correlations. We demonstrate our method in simulations and for the application of modeling senate voting records.

preprint2015arXiv

Maximum Throughput Problem in Dissipative Flow Networks with Application to Natural Gas Systems

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.

preprint2015arXiv

Minimum Weight Perfect Matching via Blossom Belief Propagation

Max-product Belief Propagation (BP) is a popular message-passing algorithm for computing a Maximum-A-Posteriori (MAP) assignment over a distribution represented by a Graphical Model (GM). It has been shown that BP can solve a number of combinatorial optimization problems including minimum weight matching, shortest path, network flow and vertex cover under the following common assumption: the respective Linear Programming (LP) relaxation is tight, i.e., no integrality gap is present. However, when LP shows an integrality gap, no model has been known which can be solved systematically via sequential applications of BP. In this paper, we develop the first such algorithm, coined Blossom-BP, for solving the minimum weight matching problem over arbitrary graphs. Each step of the sequential algorithm requires applying BP over a modified graph constructed by contractions and expansions of blossoms, i.e., odd sets of vertices. Our scheme guarantees termination in O(n^2) of BP runs, where n is the number of vertices in the original graph. In essence, the Blossom-BP offers a distributed version of the celebrated Edmonds' Blossom algorithm by jumping at once over many sub-steps with a single BP. Moreover, our result provides an interpretation of the Edmonds' algorithm as a sequence of LPs.

preprint2015arXiv

Monotonicity of Dissipative Flow Networks Renders Robust Maximum Profit Problem Tractable: General Analysis and Application to Natural Gas Flows

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.

preprint2015arXiv

Natural Gas Flow Solutions with Guarantees: A Monotone Operator Theory Approach

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.

preprint2015arXiv

Optimal Control of Transient Flow in Natural Gas Networks

We outline a new control system model for the distributed dynamics of compressible gas flow through large-scale pipeline networks with time-varying injections, withdrawals, and control actions of compressors and regulators. The gas dynamics PDE equations over the pipelines, together with boundary conditions at junctions, are reduced using lumped elements to a sparse nonlinear ODE system expressed in vector-matrix form using graph theoretic notation. This system, which we call the reduced network flow (RNF) model, is a consistent discretization of the PDE equations for gas flow. The RNF forms the dynamic constraints for optimal control problems for pipeline systems with known time-varying withdrawals and injections and gas pressure limits throughout the network. The objectives include economic transient compression (ETC) and minimum load shedding (MLS), which involve minimizing compression costs or, if that is infeasible, minimizing the unfulfilled deliveries, respectively. These continuous functional optimization problems are approximated using the Legendre-Gauss-Lobatto (LGL) pseudospectral collocation scheme to yield a family of nonlinear programs, whose solutions approach the optima with finer discretization. Simulation and optimization of time-varying scenarios on an example natural gas transmission network demonstrate the gains in security and efficiency over methods that assume steady-state behavior.

preprint2015arXiv

Optimal Power Flow with Weighted Chance Constraints and General Policies for Generation Control

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 (CC-OPF) which limits the probability of constraint violation to a predefined value. However, existing CC-OPF 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 sub-optimal. On the other hand, the standard CC-OPF formulations do not distinguish between large and small violations, although those might carry significantly different risk. In this paper, we introduce the Weighted CC-OPF (WCC-OPF) 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 WCC-OPF and the standard CC-OPF and demonstrate that WCC-OPF 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.

preprint2015arXiv

Solving the power flow equations: a monotone operator approach

The AC power flow equations underlie all operational aspects of power systems. They are solved routinely in operational practice using the Newton-Raphson method and its variants. These methods work well given a good initial "guess" for the solution, which is always available in normal system operations. However, with the increase in levels of intermittent generation, the assumption of a good initial guess always being available is no longer valid. In this paper, we solve this problem using the theory of monotone operators. We show that it is possible to compute (using an offline optimization) a "monotonicity domain" in the space of voltage phasors. Given this domain, there is a simple efficient algorithm that will either find a solution in the domain, or provably certify that no solutions exist in it. We validate the approach on several IEEE test cases and demonstrate that the offline optimization can be performed tractably and the computed "monotonicity domain" includes all practically relevant power flow solutions.

preprint2015arXiv

Structure Learning and Statistical Estimation in Distribution Networks - Part I

Traditionally power distribution networks are either not observable or only partially observable. This complicates development and implementation of new smart grid technologies, such as those related to demand response, outage detection and management, and improved load-monitoring. In this two part paper, inspired by proliferation of metering technology, we discuss estimation problems in structurally loopy but operationally radial distribution grids from measurements, e.g. voltage data, which are either already available or can be made available with a relatively minor investment. In Part I, the objective is to learn the operational layout of the grid. Part II of this paper presents algorithms that estimate load statistics or line parameters in addition to learning the grid structure. Further, Part II discusses the problem of structure estimation for systems with incomplete measurement sets. Our newly suggested algorithms apply to a wide range of realistic scenarios. The algorithms are also computationally efficient -- polynomial in time -- which is proven theoretically and illustrated computationally on a number of test cases. The technique developed can be applied to detect line failures in real time as well as to understand the scope of possible adversarial attacks on the grid.

preprint2015arXiv

Structure Learning and Statistical Estimation in Distribution Networks - Part II

Part I of this paper discusses the problem of learning the operational structure of the grid from nodal voltage measurements. In this work (Part II), the learning of the operational radial structure is coupled with the problem of estimating nodal consumption statistics and inferring the line parameters in the grid. Based on a Linear-Coupled (LC) approximation of AC power flows equations, polynomial time algorithms are designed to complete these tasks using the available nodal complex voltage measurements. Then the structure learning algorithm is extended to cases with missing data, where available observations are limited to a fraction of the grid nodes. The efficacy of the presented algorithms are demonstrated through simulations on several distribution test cases.

preprint2015arXiv

Uncertainty Sets For Wind Power Generation

As penetration of wind power generation increases, system operators must account for its stochastic nature in a reliable and cost-efficient manner. These conflicting objectives can be traded-off by accounting for the variability and uncertainty of wind power generation. This letter presents a new methodology to estimate uncertainty sets for parameters of probability distributions that capture wind generation uncertainty and variability.

preprint2014arXiv

Approximate inference on planar graphs using Loop Calculus and Belief Propagation

We introduce novel results for approximate inference on planar graphical models using the loop calculus framework. The loop calculus (Chertkov and Chernyak, 2006b) allows to express the exact partition function Z of a graphical model as a finite sum of terms that can be evaluated once the belief propagation (BP) solution is known. In general, full summation over all correction terms is intractable. We develop an algorithm for the approach presented in Chertkov et al. (2008) which represents an efficient truncation scheme on planar graphs and a new representation of the series in terms of Pfaffians of matrices. We analyze in detail both the loop series and the Pfaffian series for models with binary variables and pairwise interactions, and show that the first term of the Pfaffian series can provide very accurate approximations. The algorithm outperforms previous truncation schemes of the loop series and is competitive with other state-of-the-art methods for approximate inference.

preprint2014arXiv

Cascading of Fluctuations in Interdependent Energy Infrastructures: Gas-Grid Coupling

The revolution of hydraulic fracturing has dramatically increased the supply and lowered the cost of natural gas in the United States driving an expansion of natural gas-fired generation capacity in many electrical grids. Unrelated to the natural gas expansion, lower capital costs and renewable portfolio standards are driving an expansion of intermittent renewable generation capacity such as wind and photovoltaic generation. These two changes may potentially combine to create new threats to the reliability of these interdependent energy infrastructures. Natural gas-fired generators are often used to balance the fluctuating output of wind generation. However, the time-varying output of these generators results in time-varying natural gas burn rates that impact the pressure in interstate transmission pipelines. Fluctuating pressure impacts the reliability of natural gas deliveries to those same generators and the safety of pipeline operations. We adopt a partial differential equation model of natural gas pipelines and use this model to explore the effect of intermittent wind generation on the fluctuations of pressure in natural gas pipelines. The mean square pressure fluctuations are found to grow linearly in time with points of maximum deviation occurring at the locations of flow reversals.

preprint2014arXiv

Efficient Synchronization Stability Metrics for Fault Clearing

Direct methods can provide rapid screening of the dynamical security of large numbers fault and contingency scenarios by avoiding extensive time simulation. We introduce a computationally-efficient direct method based on optimization that leverages efficient cutting plane techniques. The method considers both unstable equilibrium points and the effects of additional relay tripping on dynamical security\cite{01SH}. Similar to other direct methods, our approach yields conservative results for dynamical security, however, the optimization formulation potentially lends itself to the inclusion of additional constraints to reduce this conservatism.

preprint2014arXiv

Fault Induced Delayed Voltage Recovery in a Long Inhomogeneous Power Distribution Feeder

We analyze the dynamics of a distribution circuit loaded with many induction motor and subjected to sudden changes in voltage at the beginning of the circuit. As opposed to earlier work \cite{13DCB}, the motors are disordered, i.e. the mechanical torque applied to the motors varies in a random manner along the circuit. In spite of the disorder, many of the qualitative features of a homogenous circuit persist, e.g. long-range motor-motor interactions mediated by circuit voltage and electrical power flows result in coexistence of the spatially-extended and propagating normal and stalled phases. We also observed a new phenomenon absent in the case without inhomogeneity/disorder. Specifically, transition front between the normal and stalled phases becomes somewhat random, even when the front is moving very slowly or is even stationary. Motors within the blurred domain appears in a normal or stalled state depending on the local configuration of the disorder. We quantify effects of the disorder and discuss statistics of distribution dynamics, e.g. the front position and width, total active/reactive consumption of the feeder and maximum clearing time.

preprint2014arXiv

Optimal compression in natural gas networks: a geometric programming approach

Natural gas transmission pipelines are complex systems whose flow characteristics are governed by challenging non-linear 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.

preprint2014arXiv

Optimal Distributed Control of Reactive Power via the Alternating Direction Method of Multipliers

We formulate the control of reactive power generation by photovoltaic inverters in a power distribution circuit as a constrained optimization that aims to minimize reactive power losses subject to finite inverter capacity and upper and lower voltage limits at all nodes in the circuit. When voltage variations along the circuit are small and losses of both real and reactive powers are small compared to the respective flows, the resulting optimization problem is convex. Moreover, the cost function is separable enabling a distributed, on-line implementation with node-local computations using only local measurements augmented with limited information from the neighboring nodes communicated over cyber channels. Such an approach lies between the fully centralized and local policy approaches previously considered. We explore protocols based on the dual ascent method and on the Alternating Direction Method of Multipliers (ADMM) and find that the ADMM protocol performs significantly better.

preprint2014arXiv

Optimal Sizing of Voltage Control Devices for Distribution Circuit with Intermittent Load

We consider joint control of a switchable capacitor and a D-STATCOM for voltage regulation in a distribution circuit with intermittent load. The control problem is formulated as a two-timescale optimal power flow problem with chance constraints, which minimizes power loss while limiting the probability of voltage violations due to fast changes in load. The control problem forms the basis of an optimization problem which determines the sizes of the control devices by minimizing sum of the expected power loss cost and the capital cost. We develop computationally efficient heuristics to solve the optimal sizing problem and implement real-time control. Numerical experiments on a circuit with high-performance computing (HPC) load show that the proposed sizing and control schemes significantly improve the reliability of voltage regulation on the expense of only a moderate increase in cost.

preprint2013arXiv

Belief Propagation for Linear Programming

Belief Propagation (BP) is a popular, distributed heuristic for performing MAP computations in Graphical Models. BP can be interpreted, from a variational perspective, as minimizing the Bethe Free Energy (BFE). BP can also be used to solve a special class of Linear Programming (LP) problems. For this class of problems, MAP inference can be stated as an integer LP with an LP relaxation that coincides with minimization of the BFE at ``zero temperature". We generalize these prior results and establish a tight characterization of the LP problems that can be formulated as an equivalent LP relaxation of MAP inference. Moreover, we suggest an efficient, iterative annealing BP algorithm for solving this broader class of LP problems. We demonstrate the algorithm's performance on a set of weighted matching problems by using it as a cutting plane method to solve a sequence of LPs tightened by adding ``blossom'' inequalities.

preprint2013arXiv

Chance Constrained Optimal Power Flow: Risk-Aware Network Control under Uncertainty

When uncontrollable resources fluctuate, Optimum Power Flow (OPF), routinely used by the electric power industry to re-dispatch hourly controllable generation (coal, gas and hydro plants) over control areas of transmission networks, can result in grid instability, and, potentially, cascading outages. This risk arises because OPF dispatch is computed without awareness of major uncertainty, in particular fluctuations in renewable output. As a result, grid operation under OPF with renewable variability can lead to frequent conditions where power line flow ratings are significantly exceeded. Such a condition, which is borne by simulations of real grids, would likely resulting in automatic line tripping to protect lines from thermal stress, a risky and undesirable outcome which compromises stability. Smart grid goals include a commitment to large penetration of highly fluctuating renewables, thus calling to reconsider current practices, in particular the use of standard OPF. Our Chance Constrained (CC) OPF corrects the problem and mitigates dangerous renewable fluctuations with minimal changes in the current operational procedure. Assuming availability of a reliable wind forecast parameterizing the distribution function of the uncertain generation, our CC-OPF satisfies all the constraints with high probability while simultaneously minimizing the cost of economic re-dispatch. CC-OPF allows efficient implementation, e.g. solving a typical instance over the 2746-bus Polish network in 20 seconds on a standard laptop.

preprint2013arXiv

Loop Calculus and Bootstrap-Belief Propagation for Perfect Matchings on Arbitrary Graphs

This manuscript discusses computation of the Partition Function (PF) and the Minimum Weight Perfect Matching (MWPM) on arbitrary, non-bipartite graphs. We present two novel problem formulations - one for computing the PF of a Perfect Matching (PM) and one for finding MWPMs - that build upon the inter-related Bethe Free Energy, Belief Propagation (BP), Loop Calculus (LC), Integer Linear Programming (ILP) and Linear Programming (LP) frameworks. First, we describe an extension of the LC framework to the PM problem. The resulting formulas, coined (fractional) Bootstrap-BP, express the PF of the original model via the BFE of an alternative PM problem. We then study the zero-temperature version of this Bootstrap-BP formula for approximately solving the MWPM problem. We do so by leveraging the Bootstrap-BP formula to construct a sequence of MWPM problems, where each new problem in the sequence is formed by contracting odd-sized cycles (or blossoms) from the previous problem. This Bootstrap-and-Contract procedure converges reliably and generates an empirically tight upper bound for the MWPM. We conclude by discussing the relationship between our iterative procedure and the famous Blossom Algorithm of Edmonds '65 and demonstrate the performance of the Bootstrap-and-Contract approach on a variety of weighted PM problems.

preprint2013arXiv

Sparsity-Promoting Optimal Wide-Area Control of Power Networks

Inter-area oscillations in bulk power systems are typically poorly controllable by means of local decentralized control. Recent research efforts have been aimed at developing wide- area control strategies that involve communication of remote signals. In conventional wide-area control, the control structure is fixed a priori typically based on modal criteria. In contrast, here we employ the recently-introduced paradigm of sparsity- promoting optimal control to simultaneously identify the optimal control structure and optimize the closed-loop performance. To induce a sparse control architecture, we regularize the standard quadratic performance index with an l1-penalty on the feedback matrix. The quadratic objective functions are inspired by the classic slow coherency theory and are aimed at imitating homogeneous networks without inter-area oscillations. We use the New England power grid model to demonstrate that the proposed combination of the sparsity-promoting control design with the slow coherency objectives performs almost as well as the optimal centralized control while only making use of a single wide-area communication link. In addition to this nominal performance, we also demonstrate that our control strategy yields favorable robustness margins and that it can be used to identify a sparse control architecture for control design via alternative means.

preprint2013arXiv

Synchronization-Aware and Algorithm-Efficient Chance Constrained Optimal Power Flow

One of the most common control decisions faced by power system operators is the question of how to dispatch generation to meet demand for power. This is a complex optimization problem that includes many nonlinear, non convex constraints as well as inherent uncertainties about future demand for power and available generation. In this paper we develop convex formulations to appropriately model crucial classes of nonlinearities and stochastic effects. We focus on solving a nonlinear optimal power flow (OPF) problem that includes loss of synchrony constraints and models wind-farm caused fluctuations. In particular, we develop (a) a convex formulation of the deterministic phase-difference nonlinear Optimum Power Flow (OPF) problem; and (b) a probabilistic chance constrained OPF for angular stability, thermal overloads and generation limits that is computationally tractable.

preprint2012arXiv

DistFlow ODE: Modeling, Analyzing and Controlling Long Distribution Feeder

We consider a linear feeder connecting multiple distributed loads and generators to the sub-station. Voltage is controlled directly at the sub-station, however, voltage down the line shifts up or down, in particular depending on if the feeder operates in the power export regime or power import regime. Starting from this finite element description of the feeder, assuming that the consumption/generation is distributed heterogeneously along the feeder, and following the asymptotic homogenization approach, we derive simple low-parametric ODE model of the feeder. We also explain how the homogeneous ODE modeling is generalized to account for other distributed effects, e.g. for inverter based and voltage dependent control of reactive power. The resulting system of the DistFlow-ODEs, relating homogenized voltage to flows of real and reactive power along the lines, admits computationally efficient analysis in terms of the minimal number of the feeder line "media" parameters, such as the ratio of the inductance-to-resistance densities. Exploring the space of the media and control parameters allows us to test and juxtapose different measures of the system performance, in particular expressed in terms of the voltage drop along the feeder, power import/export from the feeder line as the whole, power losses within the feeder, and critical (with respect to possible voltage collapse) length of the feeder. Our most surprising funding relates to performance of a feeder rich on PhotoVoltaic (PV) systems during a sunny day. We observe that if the feeder is sufficiently long the DistFlow-ODEs may have multiple stable solutions. The multiplicity may mean troubles for successful recovery of the feeder after a very short, few periods long, fault at the head of the line.

preprint2012arXiv

Distributed Control of Generation in a Transmission Grid with a High Penetration of Renewables

Deviations of grid frequency from the nominal frequency are an indicator of the global imbalance between genera- tion and load. Two types of control, a distributed propor- tional control and a centralized integral control, are cur- rently used to keep frequency deviations small. Although generation-load imbalance can be very localized, both controls primarily rely on frequency deviation as their in- put. The time scales of control require the outputs of the centralized integral control to be communicated to distant generators every few seconds. We reconsider this con- trol/communication architecture and suggest a hybrid ap- proach that utilizes parameterized feedback policies that can be implemented in a fully distributed manner because the inputs to these policies are local observables at each generator. Using an ensemble of forecasts of load and time-intermittent generation representative of possible fu- ture scenarios, we perform a centralized off-line stochas- tic optimization to select the generator-specific feedback parameters. These parameters need only be communi- cated to generators once per control period (60 minutes in our simulations). We show that inclusion of local power flows as feedback inputs is crucial and reduces frequency deviations by a factor of ten. We demonstrate our con- trol on a detailed transmission model of the Bonneville Power Administration (BPA). Our findings suggest that a smart automatic and distributed control, relying on ad- vanced off-line and system-wide computations commu- nicated to controlled generators infrequently, may be a viable control and communication architecture solution. This architecture is suitable for a future situation when generation-load imbalances are expected to grow because of increased penetration of time-intermittent generation.

preprint2012arXiv

Learning Price-Elasticity of Smart Consumers in Power Distribution Systems

Demand Response is an emerging technology which will transform the power grid of tomorrow. It is revolutionary, not only because it will enable peak load shaving and will add resources to manage large distribution systems, but mainly because it will tap into an almost unexplored and extremely powerful pool of resources comprised of many small individual consumers on distribution grids. However, to utilize these resources effectively, the methods used to engage these resources must yield accurate and reliable control. A diversity of methods have been proposed to engage these new resources. As opposed to direct load control, many methods rely on consumers and/or loads responding to exogenous signals, typically in the form of energy pricing, originating from the utility or system operator. Here, we propose an open loop communication-lite method for estimating the price elasticity of many customers comprising a distribution system. We utilize a sparse linear regression method that relies on operator-controlled, inhomogeneous minor price variations, which will be fair to all the consumers. Our numerical experiments show that reliable estimation of individual and thus aggregated instantaneous elasticities is possible. We describe the limits of the reliable reconstruction as functions of the three key parameters of the system: (i) ratio of the number of communication slots (time units) per number of engaged consumers; (ii) level of sparsity (in consumer response); and (iii) signal-to-noise ratio.

preprint2012arXiv

Synchronization in Complex Oscillator Networks and Smart Grids

The emergence of synchronization in a network of coupled oscillators is a fascinating topic in various scientific disciplines. A coupled oscillator network is characterized by a population of heterogeneous oscillators and a graph describing the interaction among them. It is known that a strongly coupled and sufficiently homogeneous network synchronizes, but the exact threshold from incoherence to synchrony is unknown. Here we present a novel, concise, and closed-form condition for synchronization of the fully nonlinear, non-equilibrium, and dynamic network. Our synchronization condition can be stated elegantly in terms of the network topology and parameters, or equivalently in terms of an intuitive, linear, and static auxiliary system. Our results significantly improve upon the existing conditions advocated thus far, they are provably exact for various interesting network topologies and parameters, they are statistically correct for almost all networks, and they can be applied equally to synchronization phenomena arising in physics and biology as well as in engineered oscillator networks such as electric power networks. We illustrate the validity, the accuracy, and the practical applicability of our results in complex networks scenarios and in smart grid applications.

preprint2012arXiv

Tail-Constraining Stochastic Linear-Quadratic Control: Large Deviation and Statistical Physics Approach

Standard definition of the stochastic Risk-Sensitive Linear-Quadratic (RS-LQ) control depends on the risk parameter, which is normally left to be set exogenously. We reconsider the classical approach and suggest two alternatives resolving the spurious freedom naturally. One approach consists in seeking for the minimum of the tail of the Probability Distribution Function (PDF) of the cost functional at some large fixed value. Another option suggests to minimize the expectation value of the cost functional under constraint on the value of the PDF tail. Under assumption of the resulting control stability, both problems are reduced to static optimizations over stationary control matrix. The solutions are illustrated on the examples of scalar and 1d chain (string) systems. Large Deviation self-similar asymptotic of the cost functional PDF is analyzed.

preprint2011arXiv

Controlled Tripping of Overheated Lines Mitigates Power Outages

We study the evolution of fast blackout cascades in the model of the Polish (transmission) power grid (2700 nodes and 3504 transmission lines). The cascade is initiated by a sufficiently severe initial contingency tripping. It propagates via sequential trippings of many more overheated lines, islanding loads and generators and eventually arriving at a fixed point with the surviving part of the system being power-flow-balanced and the rest of the system being outaged. Utilizing an improved form of the quasi-static model for cascade propagation introduced in our earlier study (Statistical Classification of Cascading Failures in Power Grids, IEEE PES GM 2011), we analyze how the severity of the cascade depends on the order of tripping overheated lines. Our main observation is that the order of tripping has a tremendous effect on the size of the resulting outage. Finding the "best" tripping, defined as causing the least damage, constitutes a difficult dynamical optimization problem, whose solution is most likely computationally infeasible. Instead, here we study performance of a number of natural heuristics, resolving the next switching decision based on the current state of the grid. Overall, we conclude that controlled intentional tripping is advantageous in the situation of a fast developing extreme emergency, as it provides significant mitigation of the resulting damage.

preprint2011arXiv

Exact and Efficient Algorithm to Discover Extreme Stochastic Events in Wind Generation over Transmission Power Grids

In this manuscript we continue the thread of [M. Chertkov, F. Pan, M. Stepanov, Predicting Failures in Power Grids: The Case of Static Overloads, IEEE Smart Grid 2011] and suggest a new algorithm discovering most probable extreme stochastic events in static power grids associated with intermittent generation of wind turbines. The algorithm becomes EXACT and EFFICIENT (polynomial) in the case of the proportional (or other low parametric) control of standard generation, and log-concave probability distribution of the renewable generation, assumed known from the wind forecast. We illustrate the algorithm's ability to discover problematic extreme events on the example of the IEEE RTS-96 model of transmission with additions of 10%, 20% and 30% of renewable generation. We observe that the probability of failure may grow but it may also decrease with increase in renewable penetration, if the latter is sufficiently diversified and distributed.

preprint2011arXiv

Linear Programming based Detectors for Two-Dimensional Intersymbol Interference Channels

We present and study linear programming based detectors for two-dimensional intersymbol interference channels. Interesting instances of two-dimensional intersymbol interference channels are magnetic storage, optical storage and Wyner's cellular network model. We show that the optimal maximum a posteriori detection in such channels lends itself to a natural linear programming based sub-optimal detector. We call this the Pairwise linear program detector. Our experiments show that the Pairwise linear program detector performs poorly. We then propose two methods to strengthen our detector. These detectors are based on systematically enhancing the Pairwise linear program. The first one, the Block linear program detector adds higher order potential functions in an {\em exhaustive} manner, as constraints, to the Pairwise linear program detector. We show by experiments that the Block linear program detector has performance close to the optimal detector. We then develop another detector by {\em adaptively} adding frustrated cycles to the Pairwise linear program detector. Empirically, this detector also has performance close to the optimal one and turns out to be less complex then the Block linear program detector.

preprint2011arXiv

Polytope of Correct (Linear Programming) Decoding and Low-Weight Pseudo-Codewords

We analyze Linear Programming (LP) decoding of graphical binary codes operating over soft-output, symmetric and log-concave channels. We show that the error-surface, separating domain of the correct decoding from domain of the erroneous decoding, is a polytope. We formulate the problem of finding the lowest-weight pseudo-codeword as a non-convex optimization (maximization of a convex function) over a polytope, with the cost function defined by the channel and the polytope defined by the structure of the code. This formulation suggests new provably convergent heuristics for finding the lowest weight pseudo-codewords improving in quality upon previously discussed. The algorithm performance is tested on the example of the Tanner [155, 64, 20] code over the Additive White Gaussian Noise (AWGN) channel.

preprint2011arXiv

Smart Finite State Devices: A Modeling Framework for Demand Response Technologies

We introduce and analyze Markov Decision Process (MDP) machines to model individual devices which are expected to participate in future demand-response markets on distribution grids. We differentiate devices into the following four types: (a) optional loads that can be shed, e.g. light dimming; (b) deferrable loads that can be delayed, e.g. dishwashers; (c) controllable loads with inertia, e.g. thermostatically-controlled loads, whose task is to maintain an auxiliary characteristic (temperature) within pre-defined margins; and (d) storage devices that can alternate between charging and generating. Our analysis of the devices seeks to find their optimal price-taking control strategy under a given stochastic model of the distribution market.

preprint2010arXiv

A Majorization-Minimization Approach to Design of Power Transmission Networks

We propose an optimization approach to design cost-effective electrical power transmission networks. That is, we aim to select both the network structure and the line conductances (line sizes) so as to optimize the trade-off between network efficiency (low power dissipation within the transmission network) and the cost to build the network. We begin with a convex optimization method based on the paper ``Minimizing Effective Resistance of a Graph'' [Ghosh, Boyd \& Saberi]. We show that this (DC) resistive network method can be adapted to the context of AC power flow. However, that does not address the combinatorial aspect of selecting network structure. We approach this problem as selecting a subgraph within an over-complete network, posed as minimizing the (convex) network power dissipation plus a non-convex cost on line conductances that encourages sparse networks where many line conductances are set to zero. We develop a heuristic approach to solve this non-convex optimization problem using: (1) a continuation method to interpolate from the smooth, convex problem to the (non-smooth, non-convex) combinatorial problem, (2) the majorization-minimization algorithm to perform the necessary intermediate smooth but non-convex optimization steps. Ultimately, this involves solving a sequence of convex optimization problems in which we iteratively reweight a linear cost on line conductances to fit the actual non-convex cost. Several examples are presented which suggest that the overall method is a good heuristic for network design. We also consider how to obtain sparse networks that are still robust against failures of lines and/or generators.

preprint2010arXiv

Belief Propagation and Loop Calculus for the Permanent of a Non-Negative Matrix

We consider computation of permanent of a positive $(N\times N)$ non-negative matrix, $P=(P_i^j|i,j=1,\cdots,N)$, or equivalently the problem of weighted counting of the perfect matchings over the complete bipartite graph $K_{N,N}$. The problem is known to be of likely exponential complexity. Stated as the partition function $Z$ of a graphical model, the problem allows exact Loop Calculus representation [Chertkov, Chernyak '06] in terms of an interior minimum of the Bethe Free Energy functional over non-integer doubly stochastic matrix of marginal beliefs, $β=(β_i^j|i,j=1,\cdots,N)$, also correspondent to a fixed point of the iterative message-passing algorithm of the Belief Propagation (BP) type. Our main result is an explicit expression of the exact partition function (permanent) in terms of the matrix of BP marginals, $β$, as $Z=\mbox{Perm}(P)=Z_{BP} \mbox{Perm}(β_i^j(1-β_i^j))/\prod_{i,j}(1-β_i^j)$, where $Z_{BP}$ is the BP expression for the permanent stated explicitly in terms if $β$. We give two derivations of the formula, a direct one based on the Bethe Free Energy and an alternative one combining the Ihara graph-$ζ$ function and the Loop Calculus approaches. Assuming that the matrix $β$ of the Belief Propagation marginals is calculated, we provide two lower bounds and one upper-bound to estimate the multiplicative term. Two complementary lower bounds are based on the Gurvits-van der Waerden theorem and on a relation between the modified permanent and determinant respectively.

preprint2010arXiv

Learning Planar Ising Models

Inference and learning of graphical models are both well-studied problems in statistics and machine learning that have found many applications in science and engineering. However, exact inference is intractable in general graphical models, which suggests the problem of seeking the best approximation to a collection of random variables within some tractable family of graphical models. In this paper, we focus our attention on the class of planar Ising models, for which inference is tractable using techniques of statistical physics [Kac and Ward; Kasteleyn]. Based on these techniques and recent methods for planarity testing and planar embedding [Chrobak and Payne], we propose a simple greedy algorithm for learning the best planar Ising model to approximate an arbitrary collection of binary random variables (possibly from sample data). Given the set of all pairwise correlations among variables, we select a planar graph and optimal planar Ising model defined on this graph to best approximate that set of correlations. We demonstrate our method in some simulations and for the application of modeling senate voting records.

preprint2010arXiv

Non-Equilibrium Statistical Physics of Currents in Queuing Networks

We consider a stable open queuing network as a steady non-equilibrium system of interacting particles. The network is completely specified by its underlying graphical structure, type of interaction at each node, and the Markovian transition rates between nodes. For such systems, we ask the question ``What is the most likely way for large currents to accumulate over time in a network ?'', where time is large compared to the system correlation time scale. We identify two interesting regimes. In the first regime, in which the accumulation of currents over time exceeds the expected value by a small to moderate amount (moderate large deviation), we find that the large-deviation distribution of currents is universal (independent of the interaction details), and there is no long-time and averaged over time accumulation of particles (condensation) at any nodes. In the second regime, in which the accumulation of currents over time exceeds the expected value by a large amount (severe large deviation), we find that the large-deviation current distribution is sensitive to interaction details, and there is a long-time accumulation of particles (condensation) at some nodes. The transition between the two regimes can be described as a dynamical second order phase transition. We illustrate these ideas using the simple, yet non-trivial, example of a single node with feedback.

preprint2010arXiv

Options for Control of Reactive Power by Distributed Photovoltaic Generators

High penetration levels of distributed photovoltaic(PV) generation on an electrical distribution circuit present several challenges and opportunities for distribution utilities. Rapidly varying irradiance conditions may cause voltage sags and swells that cannot be compensated by slowly responding utility equipment resulting in a degradation of power quality. Although not permitted under current standards for interconnection of distributed generation, fast-reacting, VAR-capable PV inverters may provide the necessary reactive power injection or consumption to maintain voltage regulation under difficult transient conditions. As side benefit, the control of reactive power injection at each PV inverter provides an opportunity and a new tool for distribution utilities to optimize the performance of distribution circuits, e.g. by minimizing thermal losses. We discuss and compare via simulation various design options for control systems to manage the reactive power generated by these inverters. An important design decision that weighs on the speed and quality of communication required is whether the control should be centralized or distributed (i.e. local). In general, we find that local control schemes are capable for maintaining voltage within acceptable bounds. We consider the benefits of choosing different local variables on which to control and how the control system can be continuously tuned between robust voltage control, suitable for daytime operation when circuit conditions can change rapidly, and loss minimization better suited for nighttime operation.

preprint2010arXiv

Planar Graphical Models which are Easy

We describe a rich family of binary variables statistical mechanics models on a given planar graph which are equivalent to Gaussian Grassmann Graphical models (free fermions) defined on the same graph. Calculation of the partition function (weighted counting) for such a model is easy (of polynomial complexity) as reducible to evaluation of a Pfaffian of a matrix of size equal to twice the number of edges in the graph. In particular, this approach touches upon Holographic Algorithms of Valiant and utilizes the Gauge Transformations discussed in our previous works.

preprint2010arXiv

Predicting Failures in Power Grids: The Case of Static Overloads

Here we develop an approach to predict power grid weak points, and specifically to efficiently identify the most probable failure modes in static load distribution for a given power network. This approach is applied to two examples: Guam's power system and also the IEEE RTS-96 system, both modeled within the static Direct Current power flow model. Our algorithm is a power network adaption of the worst configuration heuristics, originally developed to study low probability events in physics and failures in error-correction. One finding is that, if the normal operational mode of the grid is sufficiently healthy, the failure modes, also called instantons, are sufficiently sparse, i.e. the failures are caused by load fluctuations at only a few buses. The technique is useful for discovering weak links which are saturated at the instantons. It can also identify generators working at the capacity and generators under capacity, thus providing predictive capability for improving the reliability of any power network.

preprint2010arXiv

Statistical Classification of Cascading Failures in Power Grids

We introduce a new microscopic model of the outages in transmission power grids. This model accounts for the automatic response of the grid to load fluctuations that take place on the scale of minutes, when the optimum power flow adjustments and load shedding controls are unavailable. We describe extreme events, initiated by load fluctuations, which cause cascading failures of loads, generators and lines. Our model is quasi-static in the causal, discrete time and sequential resolution of individual failures. The model, in its simplest realization based on the Directed Current description of the power flow problem, is tested on three standard IEEE systems consisting of 30, 39 and 118 buses. Our statistical analysis suggests a straightforward classification of cascading and islanding phases in terms of the ratios between average number of removed loads, generators and links. The analysis also demonstrates sensitivity to variations in line capacities. Future research challenges in modeling and control of cascading outages over real-world power networks are discussed.

preprint2010arXiv

Worst Configurations (Instantons) for Compressed Sensing over Reals: a Channel Coding Approach

We consider the Linear Programming (LP) solution of the Compressed Sensing (CS) problem over reals, also known as the Basis Pursuit (BasP) algorithm. The BasP allows interpretation as a channel-coding problem, and it guarantees error-free reconstruction with a properly chosen measurement matrix and sufficiently sparse error vectors. In this manuscript, we examine how the BasP performs on a given measurement matrix and develop an algorithm to discover the sparsest vectors for which the BasP fails. The resulting algorithm is a generalization of our previous results on finding the most probable error-patterns degrading performance of a finite size Low-Density Parity-Check (LDPC) code in the error-floor regime. The BasP fails when its output is different from the actual error-pattern. We design a CS-Instanton Search Algorithm (ISA) generating a sparse vector, called a CS-instanton, such that the BasP fails on the CS-instanton, while the BasP recovery is successful for any modification of the CS-instanton replacing a nonzero element by zero. We also prove that, given a sufficiently dense random input for the error-vector, the CS-ISA converges to an instanton in a small finite number of steps. The performance of the CS-ISA is illustrated on a randomly generated $120\times 512$ matrix. For this example, the CS-ISA outputs the shortest instanton (error vector) pattern of length 11.

preprint2009arXiv

Distributed control of reactive power flow in a radial distribution circuit with high photovoltaic penetration

We show how distributed control of reactive power can serve to regulate voltage and minimize resistive losses in a distribution circuit that includes a significant level of photovoltaic (PV) generation. To demonstrate the technique, we consider a radial distribution circuit with a single branch consisting of sequentially-arranged residential-scale loads that consume both real and reactive power. In parallel, some loads also have PV generation capability. We postulate that the inverters associated with each PV system are also capable of limited reactive power generation or consumption, and we seek to find the optimal dispatch of each inverter's reactive power to both maintain the voltage within an acceptable range and minimize the resistive losses over the entire circuit. We assume the complex impedance of the distribution circuit links and the instantaneous load and PV generation at each load are known. We compare the results of the optimal dispatch with a suboptimal local scheme that does not require any communication. On our model distribution circuit, we illustrate the feasibility of high levels of PV penetration and a significant (20% or higher) reduction in losses.

preprint2009arXiv

Instanton-based Techniques for Analysis and Reduction of Error Floors of LDPC Codes

We describe a family of instanton-based optimization methods developed recently for the analysis of the error floors of low-density parity-check (LDPC) codes. Instantons are the most probable configurations of the channel noise which result in decoding failures. We show that the general idea and the respective optimization technique are applicable broadly to a variety of channels, discrete or continuous, and variety of sub-optimal decoders. Specifically, we consider: iterative belief propagation (BP) decoders, Gallager type decoders, and linear programming (LP) decoders performing over the additive white Gaussian noise channel (AWGNC) and the binary symmetric channel (BSC). The instanton analysis suggests that the underlying topological structures of the most probable instanton of the same code but different channels and decoders are related to each other. Armed with this understanding of the graphical structure of the instanton and its relation to the decoding failures, we suggest a method to construct codes whose Tanner graphs are free of these structures, and thus have less significant error floors.

preprint2009arXiv

Non-Equilibrium Thermodynamics and Topology of Currents

In many experimental situations, a physical system undergoes stochastic evolution which may be described via random maps between two compact spaces. In the current work, we study the applicability of large deviations theory to time-averaged quantities which describe such stochastic maps, in particular time-averaged currents and density functionals. We derive the large deviations principle for these quantities, as well as for global topological currents, and formulate variational, thermodynamic relations to establish large deviation properties of the topological currents. We illustrate the theory with a nontrivial example of a Heisenberg spin-chain with a topological driving of the Wess-Zumino type. The Cramér functional of the topological current is found explicitly in the instanton gas regime for the spin-chain model in the weak-noise limit. In the context of the Morse theory, we discuss a general reduction of continuous stochastic models with weak noise to effective Markov chains describing transitions between stable fixed points.

preprint2008arXiv

Fermions and Loops on Graphs. I. Loop Calculus for Determinant

This paper is the first in the series devoted to evaluation of the partition function in statistical models on graphs with loops in terms of the Berezin/fermion integrals. The paper focuses on a representation of the determinant of a square matrix in terms of a finite series, where each term corresponds to a loop on the graph. The representation is based on a fermion version of the Loop Calculus, previously introduced by the authors for graphical models with finite alphabets. Our construction contains two levels. First, we represent the determinant in terms of an integral over anti-commuting Grassman variables, with some reparametrization/gauge freedom hidden in the formulation. Second, we show that a special choice of the gauge, called BP (Bethe-Peierls or Belief Propagation) gauge, yields the desired loop representation. The set of gauge-fixing BP conditions is equivalent to the Gaussian BP equations, discussed in the past as efficient (linear scaling) heuristics for estimating the covariance of a sparse positive matrix.

preprint2008arXiv

Fermions and Loops on Graphs. II. Monomer-Dimer Model as Series of Determinants

We continue the discussion of the fermion models on graphs that started in the first paper of the series. Here we introduce a Graphical Gauge Model (GGM) and show that : (a) it can be stated as an average/sum of a determinant defined on the graph over $\mathbb{Z}_{2}$ (binary) gauge field; (b) it is equivalent to the Monomer-Dimer (MD) model on the graph; (c) the partition function of the model allows an explicit expression in terms of a series over disjoint directed cycles, where each term is a product of local contributions along the cycle and the determinant of a matrix defined on the remainder of the graph (excluding the cycle). We also establish a relation between the MD model on the graph and the determinant series, discussed in the first paper, however, considered using simple non-Belief-Propagation choice of the gauge. We conclude with a discussion of possible analytic and algorithmic consequences of these results, as well as related questions and challenges.

preprint2008arXiv

Irreversible Monte Carlo Algorithms for Efficient Sampling

Equilibrium systems evolve according to Detailed Balance (DB). This principe guided development of the Monte-Carlo sampling techniques, of which Metropolis-Hastings (MH) algorithm is the famous representative. It is also known that DB is sufficient but not necessary. We construct irreversible deformation of a given reversible algorithm capable of dramatic improvement of sampling from known distribution. Our transformation modifies transition rates keeping the structure of transitions intact. To illustrate the general scheme we design an Irreversible version of Metropolis-Hastings (IMH) and test it on example of a spin cluster. Standard MH for the model suffers from the critical slowdown, while IMH is free from critical slowdown.

preprint2003arXiv

Compensation for Extreme Outages caused by Polarization Mode Dispersion and Amplifier noise

Joint effect of weak birefringent disorder and amplifier noise on transmission in optical fiber communication systems appears to be strong. The probability of an extreme outage that corresponds to anomalously large values of Bit Error Rate (BER) is perceptible. We analyze the dependence of the Probability Distribution Function (PDF) of BER on the first-order and also higher-order PMD compensation schemes.

preprint2003arXiv

Probability of anomalously large Bit-Error-Rate in long haul optical transmission

We consider a linear model of optical pulse transmission through fiber with birefringent disorder in the presence of amplifier noise. Both disorder and noise are assumed to be weak, i.e. the average bit-error rate (BER) is small. The probability of rare violent events leading to the values of BER much larger than its typical value is estimated. We show that the probability distribution has a long algebraic tail.

preprint1998arXiv

On how a joint interaction of two innocent partners (smooth advection & linear damping) produces a strong intermittency

Forced advection of passive scalar by a smooth $d$-dimensional incompressible velocity in the presence of a linear damping is studied. Acting separately advection and dumping do not lead to an essential intermittency of the steady scalar statistics, while being mixed together produce a very strong non-Gaussianity in the convective range: $q$-th (positive) moment of the absolute value of scalar difference, $<|θ(t;{\bf r})-θ(t;0)|^{q}> $ is proportional to $r^{ξ_{q}}$, $ξ_{q}=\sqrt{d^{2}/4+αdq/[ (d-1)D]}-d/2$, where $α/D$ measures the rate of the damping in the units of the stretching rate. Probability density function (PDF) of the scalar difference is also found.