Addressing supply-side risk in uncertain power markets: Stochastic Nash models, scalable algorithms and error analysis

Aswin Kannan, Uday V. Shanbhag, Harrison M. Kim

Research output: Contribution to journalArticle

Abstract

Increasing penetration of volatile wind-based generation into the fuel mix is leading to growing supply-side volatility. As a consequence, the reliability of the power grid continues to be a source of much concern, particularly since the impact of supply-side risk exposure, arising from aggressive bidding,1 is not felt by risk-seeking generation firms; instead, the system operator is largely responsible for managing shortfalls in the real-time market. We propose an alternate design in which the cost of such risk is transferred to firms responsible for imposing such risk. The resulting strategic problem can be cast as a two-period generalized stochastic Nash game with shared strategy sets. A subset of equilibria is given by a solution to a related stochastic variational inequality, that is shown to be both monotone and solvable. Computing solutions of this variational problem is challenging since the size of the problem grows with the cardinality of the sample space, network size and the number of participating firms. Consequently, direct schemes are inadvisable for most practical problems. Instead, we present a distributed regularized primal-dual scheme and a dual projection scheme where both primal and dual iterates are computed separately. Rates of convergence estimates are provided and error bounds are developed for inexact extensions of the dual scheme. Unlike projection schemes for deterministic problems, here the projection step requires the solution of a possibly massive stochastic programme. By utilizing cutting plane methods, we ensure that the complexity of the projection scheme scales slowly with the size of the sample space. We conclude with a study of a 53-node electricity network that allows for deriving insights regarding market design and operation, particularly for accommodating firms with uncertain generation assets.

Original languageEnglish (US)
Pages (from-to)1095-1138
Number of pages44
JournalOptimization Methods and Software
Volume28
Issue number5
DOIs
StatePublished - Oct 1 2013

Fingerprint

Algorithm Analysis
Stochastic models
Error Analysis
Error analysis
Projection
Sample space
Model
Cutting Plane Method
Mathematical operators
Convergence Estimates
Bidding
Electricity
Primal-dual
Volatiles
Variational Problem
Iterate
Penetration
Volatility
Alternate
Variational Inequalities

Keywords

  • Nash games
  • cutting plane methods
  • projected gradient schemes
  • stochastic programming
  • variational inequalities

ASJC Scopus subject areas

  • Software
  • Control and Optimization
  • Applied Mathematics

Cite this

Addressing supply-side risk in uncertain power markets : Stochastic Nash models, scalable algorithms and error analysis. / Kannan, Aswin; Shanbhag, Uday V.; Kim, Harrison M.

In: Optimization Methods and Software, Vol. 28, No. 5, 01.10.2013, p. 1095-1138.

Research output: Contribution to journalArticle

@article{377bbe7f3788466d8ea147ce84b3fe96,
title = "Addressing supply-side risk in uncertain power markets: Stochastic Nash models, scalable algorithms and error analysis",
abstract = "Increasing penetration of volatile wind-based generation into the fuel mix is leading to growing supply-side volatility. As a consequence, the reliability of the power grid continues to be a source of much concern, particularly since the impact of supply-side risk exposure, arising from aggressive bidding,1 is not felt by risk-seeking generation firms; instead, the system operator is largely responsible for managing shortfalls in the real-time market. We propose an alternate design in which the cost of such risk is transferred to firms responsible for imposing such risk. The resulting strategic problem can be cast as a two-period generalized stochastic Nash game with shared strategy sets. A subset of equilibria is given by a solution to a related stochastic variational inequality, that is shown to be both monotone and solvable. Computing solutions of this variational problem is challenging since the size of the problem grows with the cardinality of the sample space, network size and the number of participating firms. Consequently, direct schemes are inadvisable for most practical problems. Instead, we present a distributed regularized primal-dual scheme and a dual projection scheme where both primal and dual iterates are computed separately. Rates of convergence estimates are provided and error bounds are developed for inexact extensions of the dual scheme. Unlike projection schemes for deterministic problems, here the projection step requires the solution of a possibly massive stochastic programme. By utilizing cutting plane methods, we ensure that the complexity of the projection scheme scales slowly with the size of the sample space. We conclude with a study of a 53-node electricity network that allows for deriving insights regarding market design and operation, particularly for accommodating firms with uncertain generation assets.",
keywords = "Nash games, cutting plane methods, projected gradient schemes, stochastic programming, variational inequalities",
author = "Aswin Kannan and Shanbhag, {Uday V.} and Kim, {Harrison M.}",
year = "2013",
month = "10",
day = "1",
doi = "10.1080/10556788.2012.676756",
language = "English (US)",
volume = "28",
pages = "1095--1138",
journal = "Optimization Methods and Software",
issn = "1055-6788",
publisher = "Taylor and Francis Ltd.",
number = "5",

}

TY - JOUR

T1 - Addressing supply-side risk in uncertain power markets

T2 - Stochastic Nash models, scalable algorithms and error analysis

AU - Kannan, Aswin

AU - Shanbhag, Uday V.

AU - Kim, Harrison M.

PY - 2013/10/1

Y1 - 2013/10/1

N2 - Increasing penetration of volatile wind-based generation into the fuel mix is leading to growing supply-side volatility. As a consequence, the reliability of the power grid continues to be a source of much concern, particularly since the impact of supply-side risk exposure, arising from aggressive bidding,1 is not felt by risk-seeking generation firms; instead, the system operator is largely responsible for managing shortfalls in the real-time market. We propose an alternate design in which the cost of such risk is transferred to firms responsible for imposing such risk. The resulting strategic problem can be cast as a two-period generalized stochastic Nash game with shared strategy sets. A subset of equilibria is given by a solution to a related stochastic variational inequality, that is shown to be both monotone and solvable. Computing solutions of this variational problem is challenging since the size of the problem grows with the cardinality of the sample space, network size and the number of participating firms. Consequently, direct schemes are inadvisable for most practical problems. Instead, we present a distributed regularized primal-dual scheme and a dual projection scheme where both primal and dual iterates are computed separately. Rates of convergence estimates are provided and error bounds are developed for inexact extensions of the dual scheme. Unlike projection schemes for deterministic problems, here the projection step requires the solution of a possibly massive stochastic programme. By utilizing cutting plane methods, we ensure that the complexity of the projection scheme scales slowly with the size of the sample space. We conclude with a study of a 53-node electricity network that allows for deriving insights regarding market design and operation, particularly for accommodating firms with uncertain generation assets.

AB - Increasing penetration of volatile wind-based generation into the fuel mix is leading to growing supply-side volatility. As a consequence, the reliability of the power grid continues to be a source of much concern, particularly since the impact of supply-side risk exposure, arising from aggressive bidding,1 is not felt by risk-seeking generation firms; instead, the system operator is largely responsible for managing shortfalls in the real-time market. We propose an alternate design in which the cost of such risk is transferred to firms responsible for imposing such risk. The resulting strategic problem can be cast as a two-period generalized stochastic Nash game with shared strategy sets. A subset of equilibria is given by a solution to a related stochastic variational inequality, that is shown to be both monotone and solvable. Computing solutions of this variational problem is challenging since the size of the problem grows with the cardinality of the sample space, network size and the number of participating firms. Consequently, direct schemes are inadvisable for most practical problems. Instead, we present a distributed regularized primal-dual scheme and a dual projection scheme where both primal and dual iterates are computed separately. Rates of convergence estimates are provided and error bounds are developed for inexact extensions of the dual scheme. Unlike projection schemes for deterministic problems, here the projection step requires the solution of a possibly massive stochastic programme. By utilizing cutting plane methods, we ensure that the complexity of the projection scheme scales slowly with the size of the sample space. We conclude with a study of a 53-node electricity network that allows for deriving insights regarding market design and operation, particularly for accommodating firms with uncertain generation assets.

KW - Nash games

KW - cutting plane methods

KW - projected gradient schemes

KW - stochastic programming

KW - variational inequalities

UR - http://www.scopus.com/inward/record.url?scp=84882402874&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84882402874&partnerID=8YFLogxK

U2 - 10.1080/10556788.2012.676756

DO - 10.1080/10556788.2012.676756

M3 - Article

AN - SCOPUS:84882402874

VL - 28

SP - 1095

EP - 1138

JO - Optimization Methods and Software

JF - Optimization Methods and Software

SN - 1055-6788

IS - 5

ER -