1 Introduction and Motivation ................................ 1
1.1 Introduction ............................................... 1
1.2 Complementarity Models: Motivation and Description ......... 1
1.2.1 Illustrative Example. Three-Variable MCP ............ 4
1.2.2 Illustrative Example. Nonlinear Program Expressed
as an MCP ........................................... 5
1.2.3 Illustrative Example. PIES Model .................... 7
1.2.4 Illustrative Example. Nash-Cournot Duopoly in
Energy Production, Two Simultaneous Optimization
Problems ............................................ 8
1.2.5 Illustrative Example. Generalized Nash Equilibria,
Energy Production Duopoly .......................... 10
1.2.6 Illustrative Example. Nash-Cournot Duopoly
Expressed as a Variational Inequality .............. 11
1.2.7 Illustrative Example. Energy Network with
Multiple Players ................................... 12
1.2.8 Illustrative Example. MPEC ......................... 16
1.3 Summary ................................................... 18
1.4 Appendix: Computational Issues for Selected Problems ...... 19
1.4.1 Illustrative Example 1.2.1 ......................... 19
1.4.2 Illustrative Example 1.2.4 ......................... 20
1.4.3 Illustrative Example 1.2.5 ......................... 21
1.4.4 Illustrative Example 1.2.7 ......................... 23
References ................................................ 27
2 Optimality and Complementarity ............................ 31
2.1 Introduction .............................................. 31
2.2 Optimization Problems ..................................... 32
2.2.1 Illustrative Example. Optimization Problem: Only
Equality Constraints ............................... 33
2.2.2 Illustrative Example. Optimization Problem:
Unconstrained ...................................... 35
2.2.3 Illustrative Example. Optimization Problem:
Equality and Inequality Constraints ................ 35
2.2.4 Linear Optimization Problems ....................... 37
2.2.5 Illustrative Example. LP Problem: Primal-Dual
Formulation ........................................ 38
2.3 Karush-Kuhn-Tucker Conditions ............................. 39
2.3.1 Illustrative Example. KKT Conditions: Equality
Constraints ........................................ 40
2.3.2 Illustrative Example. KKT Conditions: Equality
and Inequality Constraints ......................... 41
2.4 Constraint Qualifications ................................. 42
2.4.1 Illustrative Example. Constraint Qualification:
Regular Solution ................................... 43
2.4.2 Illustrative Example. Constraint Qualification:
Non-Regular Solution ............................... 43
2.5 Sufficiency Conditions .................................... 44
2.5.1 Illustrative Example. Sufficiency Conditions ....... 45
2.6 Mixed Linear Complementarity Problem, MLCP ................ 46
2.6.1 Illustrative Example. MLCP ......................... 46
2.7 Equilibrium Problems, EP .................................. 47
2.7.1 Illustrative Example. Equilibrium Conditions: No
Constraints ........................................ 49
2.7.2 Illustrative Example. Equilibrium Conditions:
Only Equality Constraints ......................... 50
2.7.3 Illustrative Example. Equilibrium Conditions:
Equality and Inequality Constraints ................ 50
2.7.4 Illustrative Example. Linear Equilibrium Problem ... 52
2.8 Mathematical Programs with Equilibrium Constraints, MPEC .. 53
2.8.1 Illustrative Example. MPEC: Only Equality
Constraints ........................................ 56
2.8.2 Illustrative Example. MPEC: Both Equality and
Inequality Constraints ............................. 58
2.9 Equilibrium Problems with Equilibrium Constraints, EPEC ... 60
2.9.1 Illustrative Example. EPEC: Only Equality
Constraints ........................................ 62
2.9.2 Illustrative Example. EPEC: Both Equality and
Inequality Constraints ............................. 64
2.10 Non-Convexity and Non-Regularity Issues ................... 66
2.11 Summary ................................................... 67
2.12 Exercises ................................................. 68
References ................................................ 69
3 Some Microeconomic Principles ............................. 71
3.1 Introduction .............................................. 71
3.2 Basics of Supply and Demand ............................... 72
3.2.1 Supply Curves ...................................... 72
3.2.2 Demand Curves ...................................... 75
3.2.3 Notion of Equilibrium as Intersection of Supply
and Demand Curves .................................. 78
3.2.3.1 Illustrative Example. Equilibrium in the
Coal Market .................................... 79
3.2.3.2 Illustrative Example. Changes in Consumers'
and Producers' Surpluses Due to a Cartel ....... 80
3.2.4 Non-Price Influences: Shifting Supply and Demand
Curves ............................................. 81
3.2.5 Multicommodity Equilibrium ......................... 83
3.2.5.1 Illustrative Example. Simultaneous Equilibrium
of Coal and Wood Markets ....................... 84
3.2.6 Estimation of Parameters of Demand and Supply
Functions .......................................... 84
3.2.6.1 Тор-Down or Statistical Estimation on
Observations ................................... 84
3.2.6.2 Bottom-Up or Process-Based Estimation .......... 86
3.2.6.3 Auctions ....................................... 87
3.3 Social Welfare Maximization ............................... 88
3.3.1 Definition of Social Welfare in Single Commodity
Models: Consumers' Plus Producers' Surpluses ....... 88
3.3.2 Equilibrium as Maximization of Social Welfare in
Single Commodity Models ............................ 89
3.3.2.1 Illustrative Example. Equilibrium in Coal
Market as Social Welfare Maximization .......... 90
3.3.3 Pareto Efficiency Versus Social Welfare
Optimization ....................................... 90
3.3.4 Social Welfare in Multicommodity Models ............ 91
3.3.4.1 Possible Difficulty to Integrate Inverse
Demand Functions in Multicommodity Models ...... 91
3.3.4.2 Illustrative Example. Impossibility of
Integrating Inverse Demand Functions for
Coal and Wood .................................. 92
3.3.4.3 Measuring Changes in Social Welfare in
Multicommodity Models .......................... 93
3.3.4.4 Illustrative Example. Changes in Consumers'
Surplus, for Wood and Coal, Due to a Tax on
Coal ........................................... 93
3.4 Modeling Individual Players in Single Commodity Markets ... 94
3.4.1 Profit-Maximization Problem for Price-Taking
Firms, and Form of Equilibrium Problem ............. 94
3.4.2 Perfect Versus Imperfect Competition ............... 97
3.4.2.1 Illustrative Example. Three Price-Taking
Firms: Social Welfare Maximization Model ....... 98
3.4.2.2 Illustrative Example. Three Price-Taking
Firms: Complementarity Model .................. 100
3.4.2.3 Monopoly Model ................................ 101
3.4.2.4 Illustrative Example. Three Firms Merged
as One Firm: Monopoly Model ................... 102
3.4.2.5 Nash-Cournot Model ............................ 103
3.4.2.6 Illustrative Example. Nash-Cournot Model
of Three Firms: Complementarity Model ......... 104
3.4.2.7 Illustrative Example. Nash-Cournot Model
of Three Firms: Optimization Model if
Demand is Linear .............................. 107
3.4.2.8 Illustrative Example. Mixed Behaviors:
Firm 1 as Cournot, Firms 2 and 3 as Price-
Takers ........................................ 108
3.4.2.9 Illustrative Example. Mixed Behaviors:
Firms 1 and 2 as Cournot, Firm 3 as Price-
Taker ......................................... 108
3.4.2.10 Bertrand Game ................................. 109
3.4.2.11 Illustrative Example. Bertrand Model of
Coal Market ................................... 109
3.4.2.12 Cartels ....................................... 110
3.4.3 Nash Versus Generalized Nash Equilibria ........... 111
3.4.3.1 Illustrative Example. Generalized Nash
Model for Coal Market: Limit on Coal Yard,
with Government Allocation of Coal Yard
Shares ........................................ 114
3.4.3.2 Illustrative Example. Generalized Nash
Model for Coal Market: Limit on Coal
Yard, with Trading of Shares and Equal
Marginal Utilities of Yard Shares ............. 115
3.4.3.3 Illustrative Example. Generalized Nash
Model for Coal Market: Limit on Coal
Yard, with Auctioning of Shares and
Unequal Marginal Utilities .................... 117
3.5 Multi-Level Games ........................................ 118
3.5.1 Stackelberg Leader-Follower Games (MPECs) ......... 118
3.5.1.1 Illustrative Example. Stackelberg MPEC
with Firm 2 as Leader ......................... 119
3.5.1.2 Illustrative Example. Stackelberg MPEC
with Firms 1 and 2 Merged as One Leader ....... 119
3.5.2 Multi-Leader Games (EPECs) ........................ 120
Summary .................................................. 121
Exercises ................................................ 122
References ............................................... 125
4 Equilibria and Complementarity Problems .................. 127
4.1 Introduction ............................................. 127
4.2 Economics and Engineering Equilibria ..................... 129
4.2.1 Equilibria in Dominant Actions .................... 129
4.2.1.1 Illustrative Example. Energy Production
Duopoly ....................................... 129
4.2.1.2 Illustrative Example. Energy Production
Duopoly, Я Changed from 1.5 to 2) ............. 130
4.2.2 Nash Equilibria ................................... 131
4.2.2.1 Illustrative Example. Energy Production
Duopoly, Nash Equilibrium ..................... 131
4.2.2.2 Illustrative Example. Energy Production
Duopoly, /3 = 1, Additional Costs ............. 132
4.2.3 Types of Game Theory Problems Considered .......... 132
4.2.4 Mixed Versus Pure Equilibria ...................... 133
4.2.4.1 Illustrative Example. Energy Production
Bimatrix Game, Version 1 ...................... 135
4.2.4.2 Illustrative Example. Energy Production
Bimatrix Game, Version 2 ...................... 136
4.3 Duality in Optimization Versus Equilibria ................ 137
4.3.1 Linear Programs as Equilibrium Problems ........... 137
4.3.1.1 Illustrative Example. Energy Production
Optimization Problem, One Player .............. 138
4.3.2 Nonlinear Programs as Equilibrium Problems ........ 140
4.4 More About the Connection Between Optimization and
Equilibrium Problems ..................................... 141
4.4.1 Spatial Price Equilibrium Problem ................. 142
4.4.1.1 Illustrative Example. Spatial Price
Equilibrium for Energy Products ............... 143
4.4.2 Optimization Problems from Equilibrium
Conditions? ....................................... 146
4.4.2.1 Illustrative Example. Extended Energy
Production Optimization Problem ............... 148
4.4.2.2 Illustrative Example. Extended Energy
Production Optimization Derived from MCP ...... 150
4.4.3 Equilibria with No Corresponding KKT-Based
Optimization Problem .............................. 151
4.4.3.1 Illustrative Example. Spatial Price
Equilibrium, Version 2 ........................ 153
4.5 Selected Existence/Uniqueness Results for Equilibrium
Problems ................................................. 155
4.6 Extensions to Equilibrium Problems ....................... 161
4.6.1 Overview .......................................... 161
4.6.1.1 Illustrative Example. Integer-Constrained
Spatial Price Equilibrium ..................... 162
4.6.2 Discretely-Constrained Mixed Linear
Complementarity Problem ........................... 162
4.6.2.1 Illustrative Example. Integer-Constrained
Network Equilibrium ........................... 164
4.6.3 Stochastic Equilibria ............................ 166
4.6.3.1 Generator/'s Problem .......................... 167
4.6.3.2 Grid Owner's Problem .......................... 169
4.6.3.3 Market Clearing ............................... 169
4.7 Summary .................................................. 170
4.8 Appendix: Computational Issues for Selected Problems ..... 170
4.8.1 Computation of Nash Equilibrium Based on the
Range for the Parameters .......................... 170
4.8.2 Computations for Price Functions in Spatial
Price Equilibrium-Version 2 ....................... 172
4.8.3 Uniqueness of Spatial Price Equilibrium Version 2
Solution .......................................... 173
4.9 Exercises ................................................ 174
References ............................................... 177
5 Variational Inequality Problems .......................... 181
5.1 Introduction ............................................. 181
5.2 Formulation of Variational Inequality Problems ........... 182
5.2.1 Optimization Problem as a VI Problem .............. 182
5.2.2 VI Formulation of Nash Equilibrium: No Linking
Constraints ....................................... 183
5.2.2.1 Illustrative Example. Nash-Cournot Model
of Coal Market from Chapter 3 ................. 185
5.2.3 VI Formulation of Generalized Nash Equilibrium
With Linking Constraints: A Special Case .......... 186
5.2.3.1 Illustrative Example. Nash-Cournot Model
of Coal Market with Coal Yard Limit from
Chapter 3 ..................................... 189
5.2.3.2 Illustrative Example. Competitive
Equilibrium of Two Related Markets: Coal
and Wood from Chapter 3 ....................... 190
5.2.3.3 Illustrative Example. PIES Multicommodity
Competitive Equilibrium Model from Chapter 1 .. 193
5.2.3.4 Illustrative Example. Stochastic Equilibrium
Model from Chapter 4 .......................... 194
5.3 Relations between Variational Inequality and
Complementarity Problems ................................. 197
5.3.1 Any Complementarity Problem Has an Equivalent
Variational Inequality Problem .................... 198
5.3.1.1 Illustrative Example. NCP and Two VI
Forms for Coal Yard Model ..................... 198
5.3.2 Any Variational Inequality Problem Has an
Equivalent Complementarity Problem ................ 200
5.3.2.1 Illustrative Example. Comparison of MCP
and VI Forms of Coal Market Model with
Coal Yard Limits .............................. 201
5.3.3 Alternative Equivalent Forms of Variational
Inequality Problems ............................... 202
5.3.3.1 Alternative Form of VI for Nash Equilibrium
with Linking Constraints ...................... 204
5.3.3.2 Illustrative Example. Alternative VI for
Nash-Cournot Model of Coal Market with
Yard Limit .................................... 205
5.4 Generalized Nash Equilibrium as Quasi-variational
Inequality Problem ....................................... 206
5.4.1 Some Important Properties of Quasi-variational
Inequality Problems ............................... 209
5.4.1.1 The VI Solution is a QVI Solution: Linking
Duals are Equal ............................... 209
5.4.1.2 Illustrative Example. Simple Electric
Capacity Market Model with High Cost
Green Energy and Equal Prices for All ......... 210
5.4.1.3 Modified VI: First Price-Directed Search
for QVI Solutions ............................. 211
5.4.1.4 Illustrative Example. Electric Capacity
Market Model with Subsidized Green Energy ..... 212
5.4.1.5 Modified VI: Second Price-Directed Search
for QVI Solutions ............................. 212
5.4.1.6 Illustrative Example. Electric Capacity
Market Model with Green Price a Multiple
of Conventional Price ......................... 213
5.4.1.7 Modified VI: Resource-Directed Search for
QVI Solutions ................................. 214
5.4.1.8 Illustrative Example. Electric Capacity
Market Model with Quotas for Green and
Conventional .................................. 214
5.5 Summary .................................................. 215
5.6 Exercises ................................................ 216
References ............................................... 219
6 Optimization Problems Constrained by Complementarity
and Other Optimization Problems .......................... 221
6.1 Introduction ............................................. 221
6.1.1 Practical Interest ................................ 221
6.1.2 Structure and Basic Classification ................ 222
6.2 Optimization Problems Constrained by Other Optimization
Problems, OPcOP .......................................... 223
6.2.1 General Formulation ............................... 223
6.2.2 Illustrative Example. Strategic Offering, OPcOP ... 226
6.2.3 Illustrative Example. Vulnerability Assessment,
OPcOP ............................................. 229
6.2.4 Illustrative Example. Transmission Investment,
OPcOP ............................................. 231
6.2.5 Basic Assumption: Constraining Problems are
Convex ............................................ 235
6.2.6 Mathematical Program with Complementarity
Constraints, MPCC ................................. 235
6.2.7 Illustrative Example. Vulnerability Assessment,
MPCC .............................................. 236
6.2.8 Mathematical Program with Equilibrium
Constraints, MPEC ................................. 237
6.2.9 Illustrative Example. Strategic Offering, MPEC .... 237
6.2.10 Illustrative Example. Transmission Investment,
MPEC .............................................. 238
6.2.11 Stochastic OPcOPs ................................. 239
6.2.12 Illustrative Example. Strategic Offering, sOPcOP .. 240
6.3 Optimization Problems Constrained by Linear Problems,
OPcLP .................................................... 241
6.3.1 Mathematical Program with Primal and Dual
Constraints, MPPDC ................................ 242
6.3.2 Illustrative Example. Strategic Offering, MPPDC ... 243
6.3.3 Illustrative Example. Vulnerability Assessment,
MPPDC ............................................. 244
6.3.4 Illustrative Example. Transmission Investment,
MPPDC ............................................. 246
6.3.5 Mathematical Program with Complementarity
Constraints, MPCC ................................. 247
6.3.6 Stochastic OPcLPs ................................. 248
6.3.7 Illustrative Example. Transmission Investment,
sOPcLP ............................................ 249
6.4 Transforming an MPCC/MPEC/MPPDC into a MILP .............. 250
6.4.1 Fortuny-Amat McCarl Linearization ................. 250
6.4.2 SOS1 and Penalty Function Linearization ........... 251
6.4.3 Other Linearizations .............................. 251
6.4.3.1 Illustrative Example. Strategic Offering:
Exact Linear Transformation ................... 252
6.5 Writing and Solving the KKTs of an MPPDC ................. 253
6.5.1 KKTs of an MPPDC .................................. 253
6.5.2 Illustrative Example. Strategic Offering, KKTs .... 254
6.5.3 Reformulating an MCP as an Optimization Problem ... 256
6.5.4 Illustrative Example. Strategic Offering: MCP
Optimization Problem .............................. 257
6.6 Summary .................................................. 258
6.7 Exercises ................................................ 258
References ............................................... 261
7 Equilibrium Problems with Equilibrium Constraints ........ 263
7.1 Introduction ............................................. 263
7.2 The EPEC Problem ......................................... 264
7.2.1 Problem Statement and Diagonalization Algorithm ... 264
7.2.2 Diagonalization Applied to EPEC ................... 267
7.3 Energy Applications of EPECs ............................. 271
7.4 EPEC Power Market Model 1: Strategic Quantity Decisions
by Generators ............................................ 274
7.4.1 Model Formulation ................................. 274
7.4.1.1 Model Structural Assumptions .................. 274
7.4.1.2 Consumer ...................................... 276
7.4.1.3 Transmission Provider ......................... 277
7.4.1.4 Follower Equilibrium .......................... 277
7.4.1.5 Generator (Leader) MPEC ....................... 278
7.4.1.6 EPEC .......................................... 279
7.4.2 Illustrative Example .............................. 279
7.4.2.1 Assumptions ................................... 279
7.4.2.2 Follower Problem .............................. 280
7.4.2.3 Leader Problems ............................... 281
7.4.2.4 EPEC Statement and Analysis ................... 282
7.4.2.5 Attempted Solution by Diagonalization ......... 285
7.4.2.6 Mixed Strategy Solution ....................... 286
7.4.2.7 Comparison of Outcomes of Alternative
Game Formulations ............................. 287
7.4.2.8 Sensitivity Case: Single Oligopolist .......... 288
7.4.2.9 Sensitivity Case: Transmission Expansion ...... 289
7.4.2.10 Summary of Cournot EPEC Example ............... 290
7.5 EPEC Power Market Model 2: Strategic Offering by
Generators ............................................... 291
7.5.1 Model Formulation ................................. 291
7.5.1.1 Structural Assumptions ........................ 291
7.5.1.2 Auctioneer (Transmission Provider) ............ 292
7.5.1.3 Producer MPEC ................................. 293
7.5.1.4 EPEC .......................................... 294
7.5.2 Illustrative Example .............................. 295
7.5.2.1 Assumptions ................................... 295
7.5.2.2 EPEC Formulation .............................. 295
7.5.2.3 Application of Diagonalization ................ 296
7.5.2.4 Mixed Strategy Equilibrium Computation ........ 299
7.5.2.5 Comparison of Average MPEC Results,
EPEC Mixed Equilibrium, and Competitive
Equilibrium ................................... 301
7.5.2.6 Pure Strategy Equilibrium ..................... 301
7.6 Closed Loop Multistage Nash Equilibrium: Capacity
Expansion ................................................ 302
7.6.1 Introduction ...................................... 302
7.6.2 Stage 2 Equilibrium: The Commodity Market ......... 303
7.6.2.1 Perfect Competition ........................... 303
7.6.2.2 Cournot Competition ........................... 305
7.6.3 Stage 1 EPEC Problem .............................. 306
7.6.4 Illustrative Example: Consumers prefer Cournot
to Bertrand Competition ........................... 308
7.7 Summary .................................................. 315
7.8 Exercises ................................................ 315
References ............................................... 319
8 Algorithms for LCPs, NCPs and Vis ........................ 323
8.1 Introduction ............................................. 323
8.2 Algorithms for LCP Models ................................ 324
8.2.1 Lemke's Pivoting Method for LCPs .................. 325
8.2.1.1 General Background on Pivoting ................ 325
8.2.1.2 Illustrative Example. Pivoting in Simplex
Method for a Linear Program ................... 326
8.2.1.3 Lemke's Method ................................ 328
8.2.1.3.1 Illustrative Example. Simple
LCP from Chapter 1 ........................ 328
8.2.1.3.2 General Statement of Lemke's Method ....... 329
8.2.1.3.3 Illustrative Example. Equilibrium
of two commodities ........................ 331
8.2.1.3.4 Convergence of Lemke's Method ............. 333
8.2.2 Iterative Methods for LCPs ........................ 333
8.2.2.1 General Background on Matrix Splitting ........ 334
8.2.2.2 Matrix Splitting for the LCP .................. 335
8.2.2.2.1 Illustrative Example. Matrix splitting
for two-commodity model: В = diagonal
part of M ................................. 336
8.2.2.2.2 Illustrative Example. Matrix splitting
for two-commodity model: symmetric В ...... 337
8.2.2.2.3 Convergence of Matrix Splitting
Algorithms for the LCP .................... 338
8.2.2.3 Other Iterative Methods for LCPs .............. 340
8.3 Algorithms for NCP Models ................................ 340
8.3.1 Newton's Method for Systems of Smooth Equations ... 342
8.3.1.1 Undamped Newton Method for Smooth Equations ... 343
8.3.1.1.1 Illustrative Example. Solving two
equations in two unknowns by Newton's
method .................................... 343
8.3.1.1.2 Convergence of the Undamped Newton
Method for Smooth Equations ............... 344
8.3.1.2 Damped Newton Methods for Smooth Equations .... 345
8.3.1.2.1 Illustrative Example. Damping Procedures
to Accelerate Convergence ................. 345
8.3.1.2.2 Convergence of the Damped Newton Method
for Smooth Equations ...................... 347
8.3.2 Newton's Method for the NCP ....................... 349
8.3.2.1 Constructing an Approximate LCP ............... 349
8.3.2.2 Solving the Approximate LCP ................... 350
8.3.2.3 Getting Started: Solving the First
Approximate LCP ............................... 351
8.3.2.4 Two Examples Without Damping .................. 352
8.3.2.4.1 Illustrative Example. PATH method for
two-commodity LCP ......................... 352
8.3.2.4.2 Illustrative Example. PATH method for
two-commodity NCP ......................... 353
8.3.2.5 Damping in the Newton Method for NCPs ......... 355
8.3.2.5.1 Illustrative Example. Min-based merit
function for two-commodity NCP .............. 356
8.3.2.5.2 Path Search between Previous Iterate and
Newton Point .............................. 356
8.3.2.6 Summary and Overview of Other Features
of the PATH Algorithm ......................... 358
8.4 Algorithms for VI Models ................................. 359
8.4.1 Solve Equivalent KKT System as MCP ................ 359
8.4.2 Iterative Methods: Sequential Optimization ........ 360
8.4.2.1 Project Independence Evaluation System
(PIES) ........................................ 360
8.4.2.1.1 Illustrative Example. Simple PIES model
and algorithm ............................. 362
8.4.2.1.2 PIES-g Algorithm .......................... 364
8.4.2.1.3 Convergence of PIES and PIES-g
Algorithms ................................ 364
8.4.2.2 A Nonlinear Approximation of G -
Diagonalization Method ........................ 365
8.4.2.2.1 Illustrative Example. The PIES-g
algorithm as diagonalization method on
a VI ...................................... 366
8.4.2.3 Symmetric Linear Approximations of G .......... 367
8.4.2.4 Convergence of Diagonalization and Symmetric
Linear Approximation .......................... 367
8.5 Summary .................................................. 368
8.6 Appendix: Introduction to Theory for PATH and Other
NCP Algorithms ........................................... 369
8.6.1 Projection Mappings ............................... 370
8.6.1.1 Illustrative Example. Projection Mapping
for В = Ж1 .................................... 370
8.6.1.2 Illustrative Example. Projection Mapping
for В as a Rectangular Box .................... 371
8.6.2 NCP Reformulated as Nonsmooth Equation Using
Projection Mapping ................................ 371
8.6.2.1 Illustrative Example. Illustration of
Theorem 8.3 with хф z ......................... 372
8.6.2.2 Illustrative Example. Illustration of
Theorem 8.3 with x = z ........................ 372
8.6.3 Some Useful Merit Functions and Corresponding
Nonsmooth Equations ............................... 373
8.6.3.1 Merit Function Based on Min Function .......... 373
8.6.3.2 Merit Function Based on Norm of the
Normal Map .................................... 374
8.6.3.3 Merit Function Based on Fischer-Burmeister
Function ...................................... 374
8.6.3.3.1 Illustrative Example. Fischer-
Burmeister-based merit function for two-
commodity NCP ............................. 375
8.6.3.4 Merit Function Based on Plus Function ......... 375
8.6.4 Damped Newton Method for NCP as Nonsmooth
Equation .......................................... 376
8.6.5 Convergence of the PATH Algorithm ................. 377
8.6.6 Other Methods to Solve NCPs ....................... 377
8.7 Exercises ................................................ 378
References ............................................... 383
9 Some Advanced Algorithms for VI Decomposition,
MPCCs and EPECs .......................................... 385
9.1 Introduction ............................................. 385
9.2 Decomposition Algorithms for Vis ......................... 386
9.2.1 Illustrative Example. Dantzig-Wolfe
Decomposition of a Simple LP ...................... 386
9.2.2 Illustrative Example. Simplified Stochastic
Power Model from Chapters 4 and 5 ................. 392
9.2.3 Dantzig-Wolfe Decomposition of Vis ................ 394
9.2.3.1 Some Computational Enhancements to
Dantzig-Wolfe Decomposition of Vis ............ 397
9.2.4 Illustrative Example. Dantzig-Wolfe
Decomposition of Simplified Stochastic Power
Model ............................................. 398
9.2.5 Simplicial Decomposition of Vis ................... 400
9.2.6 Illustrative Example. Simplicial Decomposition
of Simplified Stochastic Power Model .............. 402
9.2.7 Benders Decomposition of Vis ...................... 403
9.2.7.1 Illustrative Example. Benders Decomposition
of a Simple LP ................................ 403
9.2.7.2 General Development of Benders Decomposition
for Vis ....................................... 404
9.2.7.3 Illustrative Example. Benders Decomposition
of Simplified Stochastic Power Model .......... 406
9.2.8 Cobweb Decomposition Method - No Master Problem ... 411
9.3 Algorithms for Mathematical Programs with
Complementarity Constraints .............................. 412
9.3.1 Why Are MPCCs Difficult to Solve? ................. 414
9.3.2 Applying Standard NLP Algorithms to MPCCs ......... 415
9.3.2.1 Regularization of Complementarity
Constraints ................................... 415
9.3.2.2 Illustrative Example. Regularization
Applied to the Strategic Offer MPCC ........... 416
9.3.2.3 Penalization of Complementarity Constraints ... 417
9.3.2.4 Illustrative Example. Penalization Applied
to the Strategic Offer MPCC ................... 418
9.3.2.5 Sequential Quadratic Programming .............. 419
9.3.2.6 Illustrative Example. SQP Applied to the
Strategic Offer MPCC .......................... 419
9.3.2.7 Some Practical Advice ......................... 420
9.3.3 Some Other Methods for MPCCs ...................... 420
9.4 Algorithms for Equilibrium Programs with Equilibrium
Constraints (EPECs) ...................................... 422
9.4.1 Diagonalization Method for EPECs .................. 423
9.4.2 NLP Reformulation of EPECs ........................ 424
9.4.3 Illustrative Example. A simple 2-Leader,
1-Follower EPEC ................................... 424
9.5 Summary .................................................. 429
9.6 Exercises ................................................ 429
References ............................................... 431
10 Natural Gas Market Modeling .............................. 433
10.1 Introduction ............................................. 433
10.2 Natural Gas Market Models ................................ 435
10.3 Engineering Considerations ............................... 439
10.4 The Natural Gas Supply Chain and the Various Market
Agents ................................................... 440
10.4.1 Sectoral and Seasonal Aspects and Gas Storage
Operator .......................................... 441
10.4.2 Capacity Expansion and Multi-Year Perspective ..... 443
10.4.3 Representation of Consumers and Strategic Versus
Non-Strategic Players ............................. 443
10.4.4 Additional Players and Engineering Aspects ........ 445
10.4.5 Suppliers ......................................... 445
10.4.5.1 Production .................................... 445
10.4.5.2 Delivering Gas to the Market .................. 448
10.4.5.3 Supplier's Problem (Version 1: Production
and Export Functions) ......................... 450
10.4.5.4 Storage Operations .......................... 452
10.4.5.5 Supplier's Problem (Version 2: Production,
Export and Storage Functions) ............... 454
10.4.6 Transportation .................................... 456
10.4.7 A Model for the Whole Market ...................... 457
10.4.8 Illustrative Example. Small Natural Gas Network
Equilibrium ....................................... 459
10.4.8.1 Overview ..................................... 459
10.4.8.2 Base Case .................................... 461
10.4.8.3 Analysis of Storage .......................... 465
10.4.8.4 Analysis of Total Gas Reserves Constraint .... 466
10.4.8.5 Analysis of Contract Sales ................... 468
10.5 Summary .................................................. 469
10.6 Exercises ................................................ 470
References ............................................... 473
11 Electricity and Environmental Markets .................... 477
11.1 Introduction ............................................. 477
11.2 Transmission-Constrained Electricity Markets ............. 479
11.2.1 Sfiort-Run, Perfectly Competitive Market .......... 480
11.2.2 Illustrative Example. Transmission-Constrained
Perfect Competition Equilibrium ................... 485
11.2.3 Oligopolistic Market: A Cournot Model ............. 489
11.2.4 Illustrative Example. Transmission-Constrained
Cournot Equilibrium ............................... 495
11.3 Environmental Markets: Emissions Trading ................. 497
11.3.1 A Simple Model of Emissions Trading among
Producers ......................................... 499
11.3.2 Illustrative Example. Simple Source-Based
Emissions Trading Equilibrium ..................... 501
11.3.3 A Simple Model of Emissions Trading among
Load-Serving Entities ............................. 503
11.3.4 Illustrative Example. Simple Load-Based Market
Equilibrium ....................................... 504
11.3.5 Model Analysis: Equivalence of Source-Based and
Load Based Trading ................................ 506
11.4 Summary .................................................. 507
11.5 Exercises ................................................ 508
References ............................................... 511
12 Multicommodity Equilibrium Models: Accounting for
Demand-Side Linkages ..................................... 515
12.1 Introduction ............................................. 515
12.2 Linkages among Multiple Energy Markets ................... 516
12.3 Demand Relations over Time ............................... 520
12.3.1 Regulated Vertically Integrated Utility Model ..... 521
12.3.2 Unbundled Power Market with and without
Cross-Price Elasticities .......................... 525
12.4 Multi-Sector Models with Demand Linkages ................. 530
12.4.1 The Project Independence Evaluation System ........ 530
12.4.2 PIES Model Components ............................. 532
12.4.2.1 Consumers ..................................... 533
12.4.2.2 Fuel Producers ................................ 534
12.4.2.3 Oil Refiners .................................. 536
12.4.2.4 Shippers ...................................... 538
12.4.2.5 Market Clearing ............................... 539
12.4.3 Assembling and Solving the PIES Model ............. 540
12.4.3.1 Market Equilibrium LCP ........................ 540
12.4.3.2 Solution Approaches ........................... 542
12.4.4 PIES Equilibrium: Interpreting the Solutions of
a Multicommodity Model with Demand Linkages ...... 543
12.4.4.1 Interpreting Solutions: Where Do Prices
Come From? .................................... 544
12.4.4.2 Interpreting Solutions: Effects of Policy ..... 550
12.4.4.3 Comparison with Own-Elasticity Only Results ... 552
12.5 Summary .................................................. 556
12.6 Exercises ................................................ 557
References ............................................... 559
A Convex Sets and Functions ................................ 561
References ............................................... 569
В GAMS codes ............................................... 571
References ............................................... 605
С DC Power Flow ............................................ 607
References ............................................... 611
D Natural Gas Engineering Considerations ................... 613
References ............................................... 617
List of Tables ................................................ 619
List of Figures ............................................... 623
Index ......................................................... 625
|
