×

zbMATH — the first resource for mathematics

An approximation scheme for a class of risk-averse stochastic equilibrium problems. (English) Zbl 1414.91293
Summary: We consider two models for stochastic equilibrium: one based on the variational equilibrium of a generalized Nash game, and the other on the mixed complementarity formulation. Each agent in the market solves a single-stage risk-averse optimization problem with both here-and-now (investment) variables and (production) wait-and-see variables. A shared constraint couples almost surely the wait-and-see decisions of all the agents. An important characteristic of our approach is that the agents hedge risk in the objective functions (on costs or profits) of their optimization problems, which has a clear economic interpretation. This feature is obviously desirable, but in the risk-averse case it leads to variational inequalities with set-valued operators – a class of problems for which no established software is currently available. To overcome this difficulty, we define a sequence of approximating differentiable variational inequalities based on smoothing the nonsmooth risk measure in the agents’ problems, such as average or conditional value-at-risk. The smoothed variational inequalities can be tackled by the PATH solver, for example. The approximation scheme is shown to converge, including the case when smoothed problems are solved approximately. An interesting by-product of our proposal is that the smoothing approach allows us to show existence of an equilibrium for the original problem. To assess the proposed technique, numerical results are presented. The first set of experiments is on randomly generated equilibrium problems, for which we compare the proposed methodology with the standard smooth reformulation of average value-at-risk minimization (using additional variables to rewrite the associated max-function). The second set of experiments deals with a part of the real-life European gas network, for which Dantzig-Wolfe decomposition can be combined with the smoothing approach.

MSC:
91B74 Economic models of real-world systems (e.g., electricity markets, etc.)
65K10 Numerical optimization and variational techniques
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
91A10 Noncooperative games
Software:
PATH Solver
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Baldick, R; Helman, U; Hobbs, B; O’Neill, R, Design of efficient generation markets, Proc. IEEE, 93, 1998-2012, (2005)
[2] Burke, J; Hoheisel, T, Epi-convergent smoothing with applications to convex composite functions, SIAM J. Optim., 23, 1457-1479, (2013) · Zbl 1278.49018
[3] Chen, C; Mangasarian, O, A class of smoothing functions for nonlinear and mixed complementarity problems, Comput. Optim. Appl., 5, 97-138, (1996) · Zbl 0859.90112
[4] Chen, X, Smoothing methods for nonsmooth, novonvex minimization, Math. Program., 134, 71-99, (2012) · Zbl 1266.90145
[5] Chen, X; Fukushima, M, Expected residual minimization method for stochastic linear complementarity problems, Math. Oper. Res., 30, 1022-1038, (2005) · Zbl 1162.90527
[6] Chen, X; Wets, RJB; Zhang, Y, Stochastic variational inequalities: residual minimization smoothing sample average approximations, SIAM J. Optim., 22, 649-673, (2012) · Zbl 1263.90098
[7] Chen, X; Zhang, C; Fukushima, M, Robust solution of monotone stochastic linear complementarity problems, Math. Program., 117, 51-80, (2009) · Zbl 1165.90012
[8] Collado, R.A., Powell, W.B.: Threshold risk measures part 1: finite horizon http://castlelab.princeton.edu/Papers/Collado-Threshold-Measures-FINITE_ONLY-April-22-2013.pdf (2013) · Zbl 1261.90033
[9] Conejo, A; Nogales, F; Arroyo, J; Garcia-Bertrand, R, Risk-constrained self-scheduling of a thermal power producer, IEEE Trans. Power Syst., 19, 1569-1574, (2004) · Zbl 1055.93005
[10] Conejo, A.J., Carrión, M., Morales, J.M.: Decision Making Under Uncertainty in Electricity Markets. International Series in Operations Research & Management Science. Springer, New York (2010) · Zbl 1209.91007
[11] David, A., Wen, F.: Strategic bidding in competitive electricity markets: a literature survey. In: Power Engineering Society Summer Meeting, 2000. IEEE, vol. 4, pp. 2168-2173 (2000). doi:10.1109/PESS.2000.866982 · Zbl 1235.90109
[12] Dentcheva, D., Ruszczyński, A., Shapiro, A.: Lectures on Stochastic Programming. SIAM, Philadelphia (2009) · Zbl 1183.90005
[13] Dirkse, S; Ferris, M, The PATH solver : a nonmonotone stabilization scheme for mixed complementarity problems, Optim. Methods Softw., 5, 123-156, (1995)
[14] Egging, R, Benders decomposition for multi-stage stochastic mixed complementarity problems applied to a global natural gas market model, Eur. J. Oper. Res., 226, 341-353, (2013) · Zbl 1292.90186
[15] Egging, RG; Gabriel, SA, Examining market power in the European natural gas market, Energy Policy, 34, 2762-2778, (2006)
[16] Ehrenmann, A; Neuhoff, K, A comparison of electricity market designs in networks, Oper. Res., 57, 274-286, (2009) · Zbl 1181.90177
[17] Ehrenmann, A; Smeers, Y, Generation capacity expansion in risky environment: a stochastic equilibrium analysis, Oper. Res., 59, 1332-1346, (2011) · Zbl 1241.91062
[18] Facchinei, F; Fischer, A; Piccialli, V, On generalized Nash games and variational inequalities, Oper. Res. Lett., 35, 159-164, (2007) · Zbl 1303.91020
[19] Facchinei, F; Kanzow, C, Generalized Nash equilibrium problems, Ann. OR, 175, 177-211, (2010) · Zbl 1185.91016
[20] Facchinei, F., Pang, J.S.: Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer Series in Operations Research, vol. II. Springer, New York (2003) · Zbl 1062.90002
[21] Ferris, MC; Munson, TS, Interfaces to PATH 3.0: design, implementation and usage, Comput. Optim. Appl., 12, 207-227, (1999) · Zbl 1040.90549
[22] Fuller, JD; Chung, W, Dantzig-Wolfe decomposition of variational inequalities, Comput. Econ., 25, 303-326, (2005) · Zbl 1161.91436
[23] Gabriel, SA; Zhuang, J; Egging, R, Solving stochastic complementarity problems in energy market modeling using scenario reduction, Eur. J. Oper. Res., 197, 1028-1040, (2009) · Zbl 1176.90438
[24] Hiriart-Urruty, J.B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms. No. 305-306 in Grund. der math. Wiss. Springer, Berlin (1993). (two volumes) · Zbl 1168.90009
[25] Hobbs, B; Metzler, C; Pang, JS, Strategic gaming analysis for electric power systems: an MPEC approach, IEEE Trans. Power Syst., 15, 638-645, (2000)
[26] Hu, X; Ralph, D, Using EPECs to model bilevel games in restructured electricity markets with locational prices, Oper. Res., 55, 809-827, (2007) · Zbl 1167.91357
[27] Kannan, A; Shanbhag, UV; Kim, HM, Addressing supply-side risk in uncertain power markets: stochastic Nash models, scalable algorithms and error analysis, Optim. Methods Softw., 28, 1095-1138, (2013) · Zbl 1278.91077
[28] Kulkarni, A; Shanbhag, U, On the variational equilibrium as a refinement of the generalized Nash equilibrium, Automatica, 48, 45-55, (2012) · Zbl 1245.91006
[29] Kulkarni, AA; Shanbhag, UV, Revisiting generalized Nash games and variational inequalities, J. Optim. Theory Appl., 154, 175-186, (2012) · Zbl 1261.90065
[30] Lin, GH; Chen, X; Fukushima, M, Solving stochastic mathematical programs with equilibrium constraints via approximation and smoothing implicit programming with penalization, Math. Program., 116, 343-368, (2009) · Zbl 1168.90008
[31] Luna, JP; Sagastizábal, C; Solodov, M, A class of Dantzig-Wolfe type decomposition methods for variational inequality problems, Math. Program., 143, 177-209, (2014) · Zbl 1286.90112
[32] Luna, JP; Sagastizábal, C; Solodov, M; Kovacevic, R (ed.); Pflug, G (ed.); Vespucci, M (ed.), Complementarity and game-theoretical models for equilibria in energy markets: deterministic and risk-averse formulations, 237-264, (2014), Berlin
[33] Meng, F; Sun, J; Goh, M, A smoothing sample average approximation method for stochastic optimization problems with CVaR risk measure, Comput. Optim. Appl., 50, 379-401, (2011) · Zbl 1261.90033
[34] Pang, JS, Three modeling paradigms in mathematical programming, Math. Program., 125, 297-323, (2010) · Zbl 1202.90254
[35] Pang, JS; Fukushima, M, Quasi-variational inequalities, generalized Nash equilibria, and multi-leader-follower games, Comput. Manag. Sci., 2, 21-56, (2005) · Zbl 1115.90059
[36] Pang, JS; Fukushima, M, Quasi-variational inequalities, generalized Nash equilibria, and multi-leader-follower games, Comput. Manag. Sci., 6, 373-375, (2009) · Zbl 1168.90618
[37] Patriksson, M; Wynter, L, Stochastic mathematical programs with equilibrium constraints, Oper. Res. Lett., 25, 159-167, (1999) · Zbl 0937.90076
[38] Ralph, D., Smeers, Y.: EPECs as models for electricity markets. In: Power Systems Conference and Exposition, 2006. PSCE ’06. 2006 IEEE PES, pp. 74-80 (2006). doi:10.1109/PSCE.2006.296252 · Zbl 1165.90012
[39] Ralph, D., Smeers, Y.: Pricing risk under risk measures: an introduction to stochastic-endogenous equilibria. Social Sci. Res. Netw. http://ssrn.com/abstract=1903897 (2011) · Zbl 1263.90098
[40] Ralph, D; Xu, H, Implicit smoothing and its application to optimization with piecewise smooth equality constraints1, J. Optim. Theory Appl., 124, 673-699, (2005) · Zbl 1211.90278
[41] Ravat, U; Shanbhag, UV, On the characterization of solution sets of smooth and nonsmooth convex stochastic Nash games, SIAM J. Optim., 21, 1168-1199, (2011) · Zbl 1235.90109
[42] Rockafellar, R; Uryasev, S, Conditional value-at-risk for general loss distributions, J. Bank. Finance, 26, 1443-1471, (2002)
[43] Rockafellar, R., Wets, J.B.: Variational Analysis. Springer, New York (1997) · Zbl 0888.49001
[44] Shapiro, A; Xu, H, Stochastic mathematical programs with equilibrium constraints, J. Optim. Theory Appl., 128, 223243, (2006) · Zbl 1130.90032
[45] Wets, RJB; Greengard, C (ed.); Ruszczynski, A (ed.), Stochastic programming models: wait-and-see versus here-and-now, No. 128, 1-15, (2002), New York · Zbl 1029.90049
[46] Xu, H; Zhang, D, Smooth sample average approximation of stationary points in nonsmooth stochastic optimization and applications, Math. Program., 119, 371-401, (2009) · Zbl 1168.90009
[47] Xu, H; Zhang, D, Stochastic Nash equilibrium problems: sample average approximation and applications, Comput. Optim. Appl., 55, 597-645, (2013) · Zbl 1281.91046
[48] Yin, H; Shanbhag, U; Mehta, P, Nash equilibrium problems with scaled congestion costs and shared constraints, IEEE Trans. Autom. Control, 56, 1702-1708, (2011) · Zbl 1368.91011
[49] Zhao, J; Hobbs, BF; Pang, JS, Long-run equilibrium modeling of emissions allowance allocation systems in electric power markets, Oper. Res., 58, 529-548, (2010) · Zbl 1228.90172
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.