Search

The conditional mean embedding (CME) encodes Markovian stochastic kernels through their actions on probability distributions embedded within the reproducing kernel Hilbert spaces (RKHS). The CME plays a key role in several well-known machine learning tasks such as reinforcement learning, analysis of dynamical systems, etc. We present an algorithm to learn the CME incrementally from data via an operator-valued stochastic gradient descent. As is well-known, function learning in RKHS suffers from scalability challenges from large data. We utilize a compression mechanism to counter the scalability challenge. The core contribution of this paper is a finite-sample performance guarantee on the last iterate of the online compressed operator learning algorithm with fast-mixing Markovian samples, when the target CME may not be contained in the hypothesis space. We illustrate the efficacy of our algorithm by applying it to the analysis of an example dynamical system., Comment: 39 pages

Distributed energy resource aggregators (DERAs) must share the distribution network together with the distribution utility in order to participate in the wholesale electricity markets that are operated by independent system operators (ISOs). We propose a forward auction that a distribution system operator (DSO) can utilize to allocate distribution network access limits to DERAs. As long as the DERAs operate within their acquired limits, these limits define operating envelopes that guarantee distribution network security, thus defining a mechanism that requires no real-time intervention from the DSOs for DERAs to participate in the wholesale markets. Our auctions take the form of robust and risk-sensitive markets with bids/offers from DERAs and utility's operational costs. Properties of the proposed auction, e.g., resulting surpluses of DSO and the DERAs, and the auction prices, along with empirical performance studies, are presented., Comment: 12 page, 8 figure

We design a coordination mechanism between a distribution system operator (DSO) and distributed energy resource aggregators (DERAs) participating directly in the wholesale electricity market. Aimed at ensuring system reliability while providing open access to DERAs, the coordination mechanism includes a forward auction that allocates access limits to aggregators based on aggregators' bids that represent their benefits of aggregation. The proposed coordination mechanism results in decoupled DSO and DERAs operations that satisfy the network constraints, independent of the stochasticity of the renewables, wholesale real-time locational marginal prices, and individual DERA's aggregation policy. Optimal bidding strategies by competitive aggregators are also derived. The efficiency of the coordination mechanism and the locational price distribution at buses of a radial distribution grid are demonstrated for a 141-bus radial network., Comment: 7 pages, 5 figures

We consider the control of a Markov decision process (MDP) that undergoes an abrupt change in its transition kernel (mode). We formulate the problem of minimizing regret under control-switching based on mode change detection, compared to a mode-observing controller, as an optimal stopping problem. Using a sequence of approximations, we reduce it to a quickest change detection (QCD) problem with Markovian data, for which we characterize a state-dependent threshold-type optimal change detection policy. Numerical experiments illustrate various properties of our control-switching policy.

We study incentive designs for a class of stochastic Stackelberg games with one leader and a large number of (finite as well as infinite population of) followers. We investigate whether the leader can craft a strategy under a dynamic information structure that induces a desired behavior among the followers. For the finite population setting, under convexity of the leader's cost and other sufficient conditions, we show that there exist symmetric \emph{incentive} strategies for the leader that attain approximately optimal performance from the leader's viewpoint and lead to an approximate symmetric (pure) Nash best response among the followers. Leveraging functional analytic tools, we further show that there exists a symmetric incentive strategy, which is affine in the dynamic part of the leader's information, comprising partial information on the actions taken by the followers. Driving the follower population to infinity, we arrive at the interesting result that in this infinite-population regime the leader cannot design a smooth ``finite-energy'' incentive strategy, namely, a mean-field limit for such games is not well-defined. As a way around this, we introduce a class of stochastic Stackelberg games with a leader, a major follower, and a finite or infinite population of minor followers. For this class of problems, we establish the existence of an incentive strategy and the corresponding mean-field Stackelberg game. Examples of quadratic Gaussian games are provided to illustrate both positive and negative results. In addition, as a byproduct of our analysis, we establish the existence of a randomized incentive strategy for the class mean-field Stackelberg games, which in turn provides an approximation for an incentive strategy of the corresponding finite population Stackelberg game., Comment: 1 figure

Solar hosting capacity analysis (HCA) assesses the ability of a distribution network to host distributed solar generation without seriously violating distribution network constraints. In this paper, we consider risk-sensitive HCA that limits the risk of network constraint violations with a collection of scenarios of solar irradiance and nodal power demands, where risk is modeled via the conditional value at risk (CVaR) measure. First, we consider the question of maximizing aggregate installed solar capacities, subject to risk constraints and solve it as a second-order cone program (SOCP) with a standard conic relaxation of the feasible set with power flow equations. Second, we design an incremental algorithm to decide whether a configuration of solar installations has acceptable risk of constraint violations, modeled via CVaR. The algorithm circumvents explicit risk computation by incrementally constructing inner and outer polyhedral approximations of the set of acceptable solar installation configurations from prior such tests conducted. Our numerical examples study the impact of risk parameters, the number of scenarios and the scalability of our framework., Comment: 10 pages, 7 figures, 2 tables

Electrification can help to reduce the carbon footprint of aviation. The transition away from jet fuel-powered conventional airplane towards battery-powered electrified aircraft will impose extra charging requirements on airports. In this paper, we first quantify the increase in energy demands at several airports across the United States (US), when commercial airline carriers partially deploy hybrid electric aircraft (HEA). We then illustrate that smart charging and minor modifications to flight schedules can substantially reduce peak power demands, and in turn the needs for grid infrastructure upgrade. Motivated by our data analysis, we then formulate an optimization problem for slot allocation that incorporates HEA charging considerations. This problem jointly decides flight schedules and charging profiles to manage airport congestion and peak power demands. We illustrate the efficacy of our formulation through a case study on the John F. Kennedy International Airport., Comment: 19 pages, 8 figures

We study finite-time performance of a recently proposed distributed dual subgradient (DDSG) method for convex constrained multi-agent optimization problems. The algorithm enjoys performance guarantees on the last primal iterate, as opposed to those derived for ergodic means for vanilla DDSG algorithms. Our work improves the recently published convergence rate of $\Ocal(\log T/\sqrt{T})$ with decaying step-sizes to $\Ocal(1/\sqrt{T})$ with constant step-size on a metric that combines suboptimality and constraint violation. We then numerically evaluate the algorithm on three grid optimization problems. Namely, these are tie-line scheduling in multi-area power systems, coordination of distributed energy resources in radial distribution networks, and joint dispatch of transmission and distribution assets. The DDSG algorithm applies to each problem with various relaxations and linearizations of the power flow equations. The numerical experiments illustrate various properties of the DDSG algorithm--comparison with vanilla DDSG, impact of the number of agents, and why Nesterov-style acceleration fails in DDSG settings.

Tie-line scheduling in multi-area power systems in the US largely proceeds through a market-based mechanism called Coordinated Transaction Scheduling (CTS). We analyze this market mechanism through a game-theoretic lens. Our analysis characterizes the effect of market liquidity, market participants' forecasts about inter-area price spreads, transactions fees and coupling of CTS markets with up-to-congestion virtual transactions. Using real data, we empirically verify that CTS bidders can employ simple learning algorithms to discover Nash equilibria that support the conclusions drawn from equilibrium analysis.

We consider a market in which both suppliers and consumers compete for a product via scalar-parameterized supply offers and demand bids. Scalar-parameterized offers/bids are appealing due to their modeling simplicity and desirable mathematical properties with the most prominent being bounded efficiency loss and price markup under strategic interactions. Our model incorporates production capacity constraints and minimum inelastic demand requirements. Under perfect competition, the market mechanism yields allocations that maximize social welfare. When market participants are price-anticipating, we show that there exists a unique Nash equilibrium, and provide an efficient way to compute the resulting market allocation. Moreover, we explicitly characterize the bounds on the welfare loss and prices observed at the Nash equilibrium., Comment: 8 pages, 4 figures

We propose a distributed algorithm to compute an equilibrium in aggregate games where players communicate over a fixed undirected network. Our algorithm exploits correlated perturbation to obfuscate information shared over the network. We prove that our algorithm does not reveal private information of players to an honest-but-curious adversary who monitors several nodes in the network. In contrast with differential privacy based algorithms, our method does not sacrifice accuracy of equilibrium computation to provide privacy guarantees.

We focus on the aggregation of distributed energy resources (DERs) through a profit-maximizing intermediary that enables participation of DERs in wholesale electricity markets. Particularly, we study the market efficiency brought in by the large-scale deployment of DERs and explore to what extent such benefits are offset by the profit-maximizing nature of the aggregator. We deploy a game-theoretic framework to study the strategic interactions between an aggregator and DER owners. The proposed model takes into account the stochastic nature of the DER supply. We explicitly characterize the equilibrium of the game and provide illustrative examples to quantify the efficiency loss due to the strategic incentives of the aggregator. Our numerical experiments illustrate the impact of uncertainty and amount of DER integration on the overall market efficiency.

We analyze pricing mechanisms in electricity markets with AC power flow equations that define a nonconvex feasible set for the economic dispatch problem. Specifically, we consider two possible pricing schemes. The first among these prices are derived from Lagrange multipliers that satisfy Karush-Kuhn-Tucker conditions for local optimality of the nonconvex market clearing problem. The second is derived from optimal dual multipliers of the convex semidefinite programming (SDP) based relaxation of the market clearing problem. Relationships between these prices, their revenue adequacy and market equilibrium properties are derived and compared. The SDP prices are shown to equal distribution locational marginal prices derived with second-order conic relaxations of power flow equations over radial distribution networks. We illustrate our theoretical findings through numerical experiments., Comment: 18 pages, 3 figures and 1 table. Journal paper

We study a first-order primal-dual subgradient method to optimize risk-constrained risk-penalized optimization problems, where risk is modeled via the popular conditional value at risk (CVaR) measure. The algorithm processes independent and identically distributed samples from the underlying uncertainty in an online fashion, and produces an $\eta/\sqrt{K}$-approximately feasible and $\eta/\sqrt{K}$-approximately optimal point within $K$ iterations with constant step-size, where $\eta$ increases with tunable risk-parameters of CVaR. We find optimized step sizes using our bounds and precisely characterize the computational cost of risk aversion as revealed by the growth in $\eta$. Our proposed algorithm makes a simple modification to a typical primal-dual stochastic subgradient algorithm. With this mild change, our analysis surprisingly obviates the need for a priori bounds or complex adaptive bounding schemes for dual variables assumed in many prior works. We also draw interesting parallels in sample complexity with that for chance-constrained programs derived in the literature with a very different solution architecture., Comment: 30 pages, 2 figures; Revised in order to formalize relation to existing primal-dual algorithms, better emphasize the salient features of the algorithm, and update the example

We consider centralized and distributed mirror descent algorithms over a finite-dimensional Hilbert space, and prove that the problem variables converge to an optimizer of a possibly nonsmooth function when the step sizes are square summable but not summable. Prior literature has focused on the convergence of the function value to its optimum. However, applications from distributed optimization and learning in games require the convergence of the variables to an optimizer, which is generally not guaranteed without assuming strong convexity of the objective function. We provide numerical simulations comparing entropic mirror descent and standard subgradient methods for the robust regression problem.

Increased penetration of wind energy will make electricity market prices more volatile. As a result, market participants will bear increased financial risks, which impact investment decisions and in turn, makes it harder to achieve sustainable energy goals. As a remedy, in this paper, we propose an insurance market that complements any wholesale market design. Our mechanism can be run by any suitable financial entity such as an independent system operator, with the aim of reducing the financial impacts of volatile prices. We provide theoretical guarantees, analytically characterize the outcomes over a copperplate power system example, and numerically explore the same for a modified IEEE 14-bus test system., Comment: arXiv admin note: text overlap with arXiv:1704.00369

The tie-line scheduling problem in a multi-area power system seeks to optimize tie-line power flows across areas that are independently operated by different system operators (SOs). In this paper, we leverage the theory of multi-parametric linear programming to propose algorithms for optimal tie-line scheduling within a deterministic and a robust optimization framework. Through a coordinator, the proposed algorithms are proved to converge to the optimal schedule within a finite number of iterations. A key feature of the proposed algorithms, besides their finite step convergence, is the privacy of the information exchanges; the SO in an area does not need to reveal its dispatch cost structure, network constraints, or the nature of the uncertainty set to the coordinator. The performance of the algorithms is evaluated using several power system examples.

Wholesale electricity market designs in practice do not provide the market participants with adequate mechanisms to hedge their financial risks. Demanders and suppliers will likely face even greater risks with the deepening penetration of variable renewable resources like wind and solar. This paper explores the design of a centralized cash-settled call option market to mitigate such risks. A cash-settled call option is a financial instrument that allows its holder the right to claim a monetary reward equal to the positive difference between the real-time price of an underlying commodity and a pre-negotiated strike price for an upfront fee. Through an example, we illustrate that a bilateral call option can reduce the payment volatility of market participants. Then, we design a centralized clearing mechanism for call options that generalizes the bilateral trade. We illustrate through an example how the centralized clearing mechanism generalizes the bilateral trade. Finally, the effect of risk preference of the market participants, as well as some generalizations are discussed., Comment: Proc. 20th IFAC World Congress (IFAC WC 2017), Toulouse, France, July 9-14, 2017 (accepted)

We study Cournot competition among firms in a networked marketplace that is centrally managed by a market maker. In particular, we study a situation in which a market maker facilitates trade between geographically separate markets via a constrained transport network. Our focus is on understanding the consequences of the design of the market maker and on providing tools for optimal design. To that end we provide a characterization of the equilibrium outcomes of the game between the firms and the market maker. Our results highlight that the equilibrium structure is impacted dramatically by the market maker's objective - depending on the objective there may be a unique equilibrium, multiple equilibria, or no equilibria. Further, the game may be a potential game (as in the case of classical Cournot competition) or not. Beyond characterizing the equilibria of the game, we provide an approach for designing the market maker in order to optimize a design objective (e.g., social welfare) at the equilibrium of the game. Additionally, we use our results to explore the value of transport (trade) and the efficiency of the market maker (as compared to a single, aggregate market).

We consider the problem of characterizing the locational marginal value of energy storage capacity in electric power networks with stochastic renewable supply and demand. The perspective taken is that of a system operator, whose objective is to minimize the expected cost of firm supply required to balance a stochastic net demand process over a finite horizon, subject to transmission and energy storage constraints. The value of energy storage capacity is defined in terms of the optimal value of the corresponding constrained stochastic control problem. It is shown to be concave and non decreasing in the vector of location-dependent storage capacities -- implying that the greatest marginal value of storage is derived from initial investments in storage capacities. We also provide a characterization of said marginal value, which reveals its explicit dependency on a specific measure of nodal price variation. And, more generally, we derive an upper bound on the locational marginal value of energy storage capacity in terms of the total variation of the corresponding nodal price process, and provide conditions under which this bound is tight.

We study the role of a market maker (or market operator) in a transmission constrained electricity market. We model the market as a one-shot networked Cournot competition where generators supply quantity bids and load serving entities provide downward sloping inverse demand functions. This mimics the operation of a spot market in a deregulated market structure. In this paper, we focus on possible mechanisms employed by the market maker to balance demand and supply. In particular, we consider three candidate objective functions that the market maker optimizes - social welfare, residual social welfare, and consumer surplus. We characterize the existence of Generalized Nash Equilibrium (GNE) in this setting and demonstrate that market outcomes at equilibrium can be very different under the candidate objective functions.

Several convex relaxations of the optimal power flow (OPF) problem have recently been developed using both bus injection models and branch flow models. In this paper, we prove relations among three convex relaxations: a semidefinite relaxation that computes a full matrix, a chordal relaxation based on a chordal extension of the network graph, and a second-order cone relaxation that computes the smallest partial matrix. We prove a bijection between the feasible sets of the OPF in the bus injection model and the branch flow model, establishing the equivalence of these two models and their second-order cone relaxations. Our results imply that, for radial networks, all these relaxations are equivalent and one should always solve the second-order cone relaxation. For mesh networks, the semidefinite relaxation is tighter than the second-order cone relaxation but requires a heavier computational effort, and the chordal relaxation strikes a good balance. Simulations are used to illustrate these results., Comment: 12 pages, 7 figures

In this paper we quantify the total economic impact of an epidemic over a complex network using tools from random matrix theory. Incorporating the direct and indirect costs of infection, we calculate the disease cost in the large graph limit for an SIS (Susceptible - Infected - Susceptible) infection process. We also give an upper bound on this cost for arbitrary finite graphs and illustrate both calculated costs using extensive simulations on random and real-world networks. We extend these calculations by considering the total social cost of an epidemic, accounting for both the immunization and disease costs for various immunization strategies and determining the optimal immunization. Our work focuses on the transient behavior of the epidemic, in contrast to previous research, which typically focuses on determining the steady-state system equilibrium., Comment: 25 pages, 12 figures. Submitted to Informs Journal of Mathematics of Operations Research

We formulate the optimal placement, sizing and control of storage devices in a power network to minimize generation costs with the intent of load shifting. We assume deterministic demand, a linearized DC approximated power flow model and a fixed available storage budget. Our main result proves that when the generation costs are convex and nondecreasing, there always exists an optimal storage capacity allocation that places zero storage at generation-only buses that connect to the rest of the network via single links. This holds regardless of the demand profiles, generation capacities, line-flow limits and characteristics of the storage technologies. Through a counterexample, we illustrate that this result is not generally true for generation buses with multiple connections. For specific network topologies, we also characterize the dependence of the optimal generation cost on the available storage budget, generation capacities and flow constraints., Comment: 15 pages, 9 figures, generalized result to include line losses in Section 4B

This paper proves that non-convex quadratically constrained quadratic programs can be solved in polynomial time when their underlying graph is acyclic, provided the constraints satisfy a certain technical condition. When this condition is not satisfied, we propose a heuristic to obtain a feasible point. We demonstrate this approach on optimal power flow problems over radial networks., Comment: 29 pages, 2 figures. A special case for optimal power flow problem was published earlier in 49th Annual Allerton Conference on Communication, Control, and Computing 2011 as "Optimal Power Flow over Tree Networks"