• Decentralized Frank-Wolfe Algorithm for Convex and Non-convex Problems(1612.01216)

Aug. 28, 2018 math.OC, stat.ML, cs.SY
Decentralized optimization algorithms have received much attention due to the recent advances in network information processing. However, conventional decentralized algorithms based on projected gradient descent are incapable of handling high dimensional constrained problems, as the projection step becomes computationally prohibitive to compute. To address this problem, this paper adopts a projection-free optimization approach, a.k.a.~the Frank-Wolfe (FW) or conditional gradient algorithm. We first develop a decentralized FW (DeFW) algorithm from the classical FW algorithm. The convergence of the proposed algorithm is studied by viewing the decentralized algorithm as an inexact FW algorithm. Using a diminishing step size rule and letting $t$ be the iteration number, we show that the DeFW algorithm's convergence rate is ${\cal O}(1/t)$ for convex objectives; is ${\cal O}(1/t^2)$ for strongly convex objectives with the optimal solution in the interior of the constraint set; and is ${\cal O}(1/\sqrt{t})$ towards a stationary point for smooth but non-convex objectives. We then show that a consensus-based DeFW algorithm meets the above guarantees with two communication rounds per iteration. Furthermore, we demonstrate the advantages of the proposed DeFW algorithm on low-complexity robust matrix completion and communication efficient sparse learning. Numerical results on synthetic and real data are presented to support our findings.
• Decentralized DC MicroGrid Monitoring and Optimization via Primary Control Perturbations(1703.10467)

March 26, 2018 cs.SY
We treat the emerging power systems with direct current (DC) MicroGrids, characterized with high penetration of power electronic converters. We rely on the power electronics to propose a decentralized solution for autonomous learning of and adaptation to the operating conditions of the DC Mirogrids; the goal is to eliminate the need to rely on an external communication system for such purpose. The solution works within the primary droop control loops and uses only local bus voltage measurements. Each controller is able to estimate (i) the generation capacities of power sources, (ii) the load demands, and (iii) the conductances of the distribution lines. To define a well-conditioned estimation problem, we employ decentralized strategy where the primary droop controllers temporarily switch between operating points in a coordinated manner, following amplitude-modulated training sequences. We study the use of the estimator in a decentralized solution of the Optimal Economic Dispatch problem. The evaluations confirm the usefulness of the proposed solution for autonomous MicroGrid operation.
• SUCAG: Stochastic Unbiased Curvature-aided Gradient Method for Distributed Optimization(1803.08198)

March 22, 2018 math.OC, stat.ML
We propose and analyze a new stochastic gradient method, which we call Stochastic Unbiased Curvature-aided Gra- dient (SUCAG), for finite sum optimization problems. SUCAG constitutes an unbiased total gradient tracking technique that uses Hessian information to accelerate convergence. We an- alyze our method under the general asynchronous model of computation, in which functions are selected infinitely often, but with delays that can grow sublinearly. For strongly convex problems, we establish linear convergence for the SUCAG method. When the initialization point is sufficiently close to the optimal solution, the established convergence rate is only dependent on the condition number of the problem, making it strictly faster than the known rate for the SAGA method. Furthermore, we describe a Markov-driven approach of implementing the SUCAG method in a distributed asynchronous multi-agent setting, via gossiping along a random walk on the communication graph. We show that our analysis applies as long as the undirected graph is connected and, notably, establishes an asymptotic linear convergence rate that is robust to the graph topology. Numerical results demonstrate the merit of our algorithm over existing methods.
• Continuous Time Multi-stage Stochastic Reserve and Unit Commitment(1803.07115)

March 19, 2018 math.OC
In this paper we introduce a continuous time multi stage stochastic optimization for scheduling generating units, their commitment, reserve capacities and their continuous time generation profiles in the day-ahead wholesale electricity market. Our formulation approximates the solution of a variational problem, in which the balance, generation capacity and ramping constraints are in continuous time. Due to the greater accuracy of our representation of ramping events this approach improves the system reliability and lowers the real-time cost.
• A Stochastic Model for Short-Term Probabilistic Forecast of Solar Photo-Voltaic Power(1706.05445)

Sept. 16, 2017 stat.AP
In this paper, a stochastic model with regime switching is developed for solar photo-voltaic (PV) power in order to provide short-term probabilistic forecasts. The proposed model for solar PV power is physics inspired and explicitly incorporates the stochasticity due to clouds using different parameters addressing the attenuation in power.Based on the statistical behavior of parameters, a simple regime-switching process between the three classes of sunny, overcast and partly cloudy is proposed. Then, probabilistic forecasts of solar PV power are obtained by identifying the present regime using PV power measurements and assuming persistence in this regime. To illustrate the technique developed, a set of solar PV power data from a single rooftop installation in California is analyzed and the effectiveness of the model in fitting the data and in providing short-term point and probabilistic forecasts is verified. The proposed forecast method outperforms a variety of reference models that produce point and probabilistic forecasts and therefore portrays the merits of employing the proposed approach.
• Anomaly Detection Using Optimally-Placed Micro-PMU Sensors in Distribution Grids(1708.00118)

Aug. 1, 2017 physics.data-an, cs.SY
As the distribution grid moves toward a tightly-monitored network, it is important to automate the analysis of the enormous amount of data produced by the sensors to increase the operators situational awareness about the system. In this paper, focusing on Micro-Phasor Measurement Unit ($\mu$PMU) data, we propose a hierarchical architecture for monitoring the grid and establish a set of analytics and sensor fusion primitives for the detection of abnormal behavior in the control perimeter. Due to the key role of the $\mu$PMU devices in our architecture, a source-constrained optimal $\mu$PMU placement is also described that finds the best location of the devices with respect to our rules. The effectiveness of the proposed methods are tested through the synthetic and real $\mu$PMU data.
• Utility Maximizing Sequential Sensing Over a Finite Horizon(1705.05960)

May 17, 2017 cs.SY
We consider the problem of optimally utilizing $N$ resources, each in an unknown binary state. The state of each resource can be inferred from state-dependent noisy measurements. Depending on its state, utilizing a resource results in either a reward or a penalty per unit time. The objective is a sequential strategy governing the decision of sensing and exploitation at each time to maximize the expected utility (i.e., total reward minus total penalty and sensing cost) over a finite horizon $L$. We formulate the problem as a Partially Observable Markov Decision Process (POMDP) and show that the optimal strategy is based on two time-varying thresholds for each resource and an optimal selection rule for which resource to sense. Since a full characterization of the optimal strategy is generally intractable, we develop a low-complexity policy that is shown by simulations to offer near optimal performance. This problem finds applications in opportunistic spectrum access, marketing strategies and other sequential resource allocation problems.
• Active Spectrum Sensing with Sub-Nyquist sampling(1707.00566)

May 16, 2017 cs.IT, math.IT
At high carriers, enabling low power wireless devices to use opportunistically the available spectrum requires an analog front-end that can sweep different bands quickly, since Nyquist sampling is prohibitively expensive. In this paper we propose a new framework that allows to optimize a sub-Nyquist sampling front-end to combine the benefits of optimum sequential sensing with those of compressive spectrum sensing. The sensing strategy we propose is formulated as an optimization problem whose objective of maximizing a utility decreasing linearly with the number of measurement and increasing monotonically with the components found empty. The optimization designs the optimum measurement selecting the best linear combinations of sub-bands to mix to accrue the maximum utility. The structure of the utility represents the trade-off between exploration, exploitation and risk of making an error that is characteristic of the spectrum sensing problem. We characterize the optimal policy under constraints on the sensing matrix and derive the approximation factor of the greedy approach. Second, we present the analog front-end architecture and map the measurement model into the abstract optimization problem proposed and analyzed in the first part of the paper. Numerical simulations corroborate our claims and show the benefits of combining opportunistic spectrum sensing with sub-Nyquist sampling.
• Convergence Results on Pulse Coupled Oscillator Protocols in Locally Connected Networks(1705.05954)

May 16, 2017 cs.NI
This work provides new insights on the convergence of a locally connected network of pulse coupled oscillator (PCOs) (i.e., a bio-inspired model for communication networks) to synchronous and desynchronous states, and their implication in terms of the decentralized synchronization and scheduling in communication networks. Bio-inspired techniques have been advocated by many as fault-tolerant and scalable alternatives to produce self-organization in communication networks. The PCO dynamics in particular have been the source of inspiration for many network synchronization and scheduling protocols. However, their convergence properties, especially in locally connected networks, have not been fully understood, prohibiting the migration into mainstream standards. This work provides further results on the convergence of PCOs in locally connected networks and the achievable convergence accuracy under propagation delays. For synchronization, almost sure convergence is proved for $3$ nodes and accuracy results are obtained for general locally connected networks whereas, for scheduling (or desynchronization), results are derived for locally connected networks with mild conditions on the overlapping set of maximal cliques. These issues have not been fully addressed before in the literature.
• The impact of random actions on opinion dynamics(1704.01660)

April 5, 2017 math.PR, cs.SI
Opinion dynamics have fascinated researchers for centuries. The ability of societies to learn as well as the emergence of irrational {\it herding} are equally evident. The simplest example is that of agents that have to determine a binary action, under peer pressure coming from the decisions observed. By modifying several popular models for opinion dynamics so that agents internalize actions rather than smooth estimates of what other people think, we are able to prove that almost surely the actions final outcome remains random, even though actions can be consensual or polarized depending on the model. This is a theoretical confirmation that the mechanism that leads to the emergence of irrational herding behavior lies in the loss of nuanced information regarding the privately held beliefs behind the individuals decisions.
• Dynamic Formulation for Multistage Stochastic Unit Commitment Problem(1612.06484)

Dec. 20, 2016 math.OC
As net-load becomes less predictable there is a lot of pressure in changing decision models for power markets such that they account explicitly for future scenarios in making commitment decisions. This paper proposes to make commitment decisions using a dynamic multistage stochastic unit commitment formulation over a cohesive horizon that leverages a state-space model for the commitment variables. We study the problem of constructing scenario tree approximations for both original and residual stochastic process and evaluate our algorithms on scenario tree libraries derived from real net-load data.
• RIDS: Robust Identification of Sparse Gene Regulatory Networks from Perturbation Experiments(1612.06565)

Dec. 20, 2016 cs.IT, math.IT, q-bio.QM, q-bio.MN, stat.ML
Reconstructing the causal network in a complex dynamical system plays a crucial role in many applications, from sub-cellular biology to economic systems. Here we focus on inferring gene regulation networks (GRNs) from perturbation or gene deletion experiments. Despite their scientific merit, such perturbation experiments are not often used for such inference due to their costly experimental procedure, requiring significant resources to complete the measurement of every single experiment. To overcome this challenge, we develop the Robust IDentification of Sparse networks (RIDS) method that reconstructs the GRN from a small number of perturbation experiments. Our method uses the gene expression data observed in each experiment and translates that into a steady state condition of the system's nonlinear interaction dynamics. Applying a sparse optimization criterion, we are able to extract the parameters of the underlying weighted network, even from very few experiments. In fact, we demonstrate analytically that, under certain conditions, the GRN can be perfectly reconstructed using $K = \Omega (d_{max})$ perturbation experiments, where $d_{max}$ is the maximum in-degree of the GRN, a small value for realistic sparse networks, indicating that RIDS can achieve high performance with a scalable number of experiments. We test our method on both synthetic and experimental data extracted from the DREAM5 network inference challenge. We show that the RIDS achieves superior performance compared to the state-of-the-art methods, while requiring as few as ~60% less experimental data. Moreover, as opposed to almost all competing methods, RIDS allows us to infer the directionality of the GRN links, allowing us to infer empirical GRNs, without relying on the commonly provided list of transcription factors.
• Active Sensing of Social Networks(1601.05834)

Oct. 5, 2016 cs.SI, stat.ML
This paper develops an active sensing method to estimate the relative weight (or trust) agents place on their neighbors' information in a social network. The model used for the regression is based on the steady state equation in the linear DeGroot model under the influence of stubborn agents, i.e., agents whose opinions are not influenced by their neighbors. This method can be viewed as a \emph{social RADAR}, where the stubborn agents excite the system and the latter can be estimated through the reverberation observed from the analysis of the agents' opinions. The social network sensing problem can be interpreted as a blind compressed sensing problem with a sparse measurement matrix. We prove that the network structure will be revealed when a sufficient number of stubborn agents independently influence a number of ordinary (non-stubborn) agents. We investigate the scenario with a deterministic or randomized DeGroot model and propose a consistent estimator of the steady states for the latter scenario. Simulation results on synthetic and real world networks support our findings.
• Automated Anomaly Detection in Distribution Grids Using $\mu$PMU Measurements(1610.01107)

Sept. 30, 2016 physics.data-an, cs.SY
The impact of Phasor Measurement Units (PMUs) for providing situational awareness to transmission system operators has been widely documented. Micro-PMUs ($\mu$PMUs) are an emerging sensing technology that can provide similar benefits to Distribution System Operators (DSOs), enabling a level of visibility into the distribution grid that was previously unattainable. In order to support the deployment of these high resolution sensors, the automation of data analysis and prioritizing communication to the DSO becomes crucial. In this paper, we explore the use of $\mu$PMUs to detect anomalies on the distribution grid. Our methodology is motivated by growing concern about failures and attacks to distribution automation equipment. The effectiveness of our approach is demonstrated through both real and simulated data.
• Distributed Estimation of the Operating State of a Single-Bus DC MicroGrid without an External Communication Interface(1609.04623)

Sept. 14, 2016 stat.ML, cs.SY
We propose a decentralized Maximum Likelihood solution for estimating the stochastic renewable power generation and demand in single bus Direct Current (DC) MicroGrids (MGs), with high penetration of droop controlled power electronic converters. The solution relies on the fact that the primary control parameters are set in accordance with the local power generation status of the generators. Therefore, the steady state voltage is inherently dependent on the generation capacities and the load, through a non-linear parametric model, which can be estimated. To have a well conditioned estimation problem, our solution avoids the use of an external communication interface and utilizes controlled voltage disturbances to perform distributed training. Using this tool, we develop an efficient, decentralized Maximum Likelihood Estimator (MLE) and formulate the sufficient condition for the existence of the globally optimal solution. The numerical results illustrate the promising performance of our MLE algorithm.
• Optimal Pricing to Manage Electric Vehicles in Coupled Power and Transportation Networks(1511.03611)

Sept. 14, 2016 cs.MA, cs.SY
We study the system-level effects of the introduction of large populations of Electric Vehicles on the power and transportation networks. We assume that each EV owner solves a decision problem to pick a cost-minimizing charge and travel plan. This individual decision takes into account traffic congestion in the transportation network, affecting travel times, as well as as congestion in the power grid, resulting in spatial variations in electricity prices for battery charging. We show that this decision problem is equivalent to finding the shortest path on an "extended" transportation graph, with virtual arcs that represent charging options. Using this extended graph, we study the collective effects of a large number of EV owners individually solving this path planning problem. We propose a scheme in which independent power and transportation system operators can collaborate to manage each network towards a socially optimum operating point while keeping the operational data of each system private. We further study the optimal reserve capacity requirements for pricing in the absence of such collaboration. We showcase numerically that a lack of attention to interdependencies between the two infrastructures can have adverse operational effects.
• Continuous-time Marginal Pricing of Power Trajectories in Power Systems(1607.03802)

July 11, 2016 math.OC
In this paper we formulate of the Economic Dispatch (ED) problem in Power Systems in continuous time and include in it ramping constraints to derive an expression of the price that reflects some important inter-temporal constraints of the power units. The motivation for looking at this problem is the scarcity of ramping resources and their increasing importance motivated by the variability of power resources, particularly due to the addition of solar power, which exacerbates the need of fast ramping units in the early morning and early evening hours. We show that the solution for the marginal price can be found through Euler-Lagrange equations and we argue that this price signal better reflects the market value of power in the presence of significant ramps in net-load.
• Modeling Group Dynamics Using Probabilistic Tensor Decompositions(1606.07840)

June 24, 2016 stat.ML
We propose a probabilistic modeling framework for learning the dynamic patterns in the collective behaviors of social agents and developing profiles for different behavioral groups, using data collected from multiple information sources. The proposed model is based on a hierarchical Bayesian process, in which each observation is a finite mixture of an set of latent groups and the mixture proportions (i.e., group probabilities) are drawn randomly. Each group is associated with some distributions over a finite set of outcomes. Moreover, as time evolves, the structure of these groups also changes; we model the change in the group structure by a hidden Markov model (HMM) with a fixed transition probability. We present an efficient inference method based on tensor decompositions and the expectation-maximization (EM) algorithm for parameter estimation.
• The Social System Identification Problem(1503.07288)

Aug. 21, 2015 cs.SI
The focus of this paper is modeling what we call a Social Radar, i.e. a method to estimate the relative influence between social agents, by sampling their opinions and as they evolve, after injecting in the network stubborn agents. The stubborn agents opinion is not influenced by the peers they seek to sway, and their opinion bias is the known input to the social network system. The novelty is in the model presented to probe a social network and the solution of the associated regression problem. The model allows to map the observed opinion onto system equations that can be used to infer the social graph and the amount of trust that characterizes the links.
• Generation bidding game with flexible demand(1408.6689)

Aug. 28, 2014 cs.GT
For a simple model of price-responsive demand, we consider a deregulated electricity marketplace wherein the grid (ISO, retailer-distributor) accepts bids per-unit supply from generators (simplified herein neither to consider start-up/ramp-up expenses nor day-ahead or shorter-term load following) which are then averaged (by supply allocations via an economic dispatch) to a common "clearing" price borne by customers (irrespective of variations in transmission/distribution or generation prices), i.e., the ISO does not compensate generators based on their marginal costs. Rather, the ISO provides sufficient information for generators to sensibly adjust their bids. Notwithstanding our idealizations, the dispatch dynamics are complex. For a simple benchmark power system, we find a price-symmetric Nash equilibrium through numerical experiments.
• Capturing Aggregate Flexibility in Demand Response(1404.1955)

April 7, 2014 cs.SY
Flexibility in electric power consumption can be leveraged by Demand Response (DR) programs. The goal of this paper is to systematically capture the inherent aggregate flexibility of a population of appliances. We do so by clustering individual loads based on their characteristics and service constraints. We highlight the challenges associated with learning the customer response to economic incentives while applying demand side management to heterogeneous appliances. We also develop a framework to quantify customer privacy in direct load scheduling programs.
• Scalable and Anonymous Modeling of Large Populations of Flexible Appliances(1404.1958)

April 7, 2014 cs.SY
To respond to volatility and congestion in the power grid, demand response (DR) mechanisms allow for shaping the load compared to a base load profile. When tapping on a large population of heterogeneous appliances as a DR resource, the challenge is in modeling the dimensions available for control. Such models need to strike the right balance between accuracy of the model and tractability. The goal of this paper is to provide a medium-grained stochastic hybrid model to represent a population of appliances that belong to two classes: deferrable or thermostatically controlled loads. We preserve quantized information regarding individual load constraints, while discarding information about the identity of appliance owners. The advantages of our proposed population model are 1) it allows us to model and control load in a scalable fashion, useful for ex-ante planning by an aggregator or for real-time load control; 2) it allows for the preservation of the privacy of end-use customers that own submetered or directly controlled appliances.
• The Cognitive Compressive Sensing Problem(1401.4237)

Jan. 23, 2014 cs.IT, math.IT, math.OC
In the Cognitive Compressive Sensing (CCS) problem, a Cognitive Receiver (CR) seeks to optimize the reward obtained by sensing an underlying $N$ dimensional random vector, by collecting at most $K$ arbitrary projections of it. The $N$ components of the latent vector represent sub-channels states, that change dynamically from "busy" to "idle" and vice versa, as a Markov chain that is biased towards producing sparse vectors. To identify the optimal strategy we formulate the Multi-Armed Bandit Compressive Sensing (MAB-CS) problem, generalizing the popular Cognitive Spectrum Sensing model, in which the CR can sense $K$ out of the $N$ sub-channels, as well as the typical static setting of Compressive Sensing, in which the CR observes $K$ linear combinations of the $N$ dimensional sparse vector. The CR opportunistic choice of the sensing matrix should balance the desire of revealing the state of as many dimensions of the latent vector as possible, while not exceeding the limits beyond which the vector support is no longer uniquely identifiable.
• Distributed Constrained Optimization by Consensus-Based Primal-Dual Perturbation Method(1304.5590)

Nov. 6, 2013 math.OC, cs.SY
Various distributed optimization methods have been developed for solving problems which have simple local constraint sets and whose objective function is the sum of local cost functions of distributed agents in a network. Motivated by emerging applications in smart grid and distributed sparse regression, this paper studies distributed optimization methods for solving general problems which have a coupled global cost function and have inequality constraints. We consider a network scenario where each agent has no global knowledge and can access only its local mapping and constraint functions. To solve this problem in a distributed manner, we propose a consensus-based distributed primal-dual perturbation (PDP) algorithm. In the algorithm, agents employ the average consensus technique to estimate the global cost and constraint functions via exchanging messages with neighbors, and meanwhile use a local primal-dual perturbed subgradient method to approach a global optimum. The proposed PDP method not only can handle smooth inequality constraints but also non-smooth constraints such as some sparsity promoting constraints arising in sparse optimization. We prove that the proposed PDP algorithm converges to an optimal primal-dual solution of the original problem, under standard problem and network assumptions. Numerical results illustrating the performance of the proposed algorithm for a distributed demand response control problem in smart grid are also presented.
• Incentive Design for Direct Load Control Programs(1310.0402)

Oct. 1, 2013 cs.SY
We study the problem of optimal incentive design for voluntary participation of electricity customers in a Direct Load Scheduling (DLS) program, a new form of Direct Load Control (DLC) based on a three way communication protocol between customers, embedded controls in flexible appliances, and the central entity in charge of the program. Participation decisions are made in real-time on an event-based basis, with every customer that needs to use a flexible appliance considering whether to join the program given current incentives. Customers have different interpretations of the level of risk associated with committing to pass over the control over the consumption schedule of their devices to an operator, and these risk levels are only privately known. The operator maximizes his expected profit of operating the DLS program by posting the right participation incentives for different appliance types, in a publicly available and dynamically updated table. Customers are then faced with the dynamic decision making problem of whether to take the incentives and participate or not. We define an optimization framework to determine the profit-maximizing incentives for the operator. In doing so, we also investigate the utility that the operator expects to gain from recruiting different types of devices. These utilities also provide an upper-bound on the benefits that can be attained from any type of demand response program.