An Extreme-Point Global Optimization Technique for Convex Hull Pricing

---

G. Wang, U. V. Shanbhag, T. Zheng, E. Litvinov, and S. P. Meyn

 

Abstract: Prices in electricity markets are given by the dual variables associated with the supply-demand constraint in the dispatch problem. However, in unit-commitment-based day-ahead markets, these variables are less easy to obtain. A common approach relies on resolving the dispatch problem with the commitment decisions fixed and utilizing the associated dual variables. Yet, this avenue leads to inadequate revenues to generators and necessitates an uplift payment to be made by the market operator. Recently, a convex hull pricing scheme has been proposed to reduce the impact of such payments and requires the global maximization of the associated Lagrangian dual problem, which is, in general, a piecewise-affine concave function. In this paper, we present an extreme-point-based finite-termination procedure for obtaining such a global maximizer. Unlike standard subgradient schemes where an arbitrary subgradient is used, we present a novel technique where the steepest ascent direction is constructed by solving a continuous quadratic program. The scheme initiates a move along this direction with an a priori constant steplength, with the intent of reaching the boundary of the face. A backtracking scheme allows for mitigating the impact of excessively large steps. Termination of the scheme occurs when the set of subgradients contains the zero vector. Preliminary numerical tests are seen to be promising and display the finite-termination property. Furthermore, the scheme is seen to significantly outperform standard subgradient methods.

Research supported in part by the Grainger Endowments to the University of Illinois. Gui Wang and Sean Meyn are with the Department of Electrical and Computer Engineering, University of Illinois at Urbana-Champaign, IL 61801 USA. Uday V. Shanbhag is with the Department of Industrial and Enterprise Systems Engineering at the same university. Tongxin Zheng and Eugene Litvinov are with Business Architecture and Technology, ISO New England, Holyoke, MA 01040 USA.

The views expressed in this paper are solely those of the authors and not necessarily those of ISO New England.

References

@unpublished{wanshazhelitmey10,
Author = {G. Wang and U. V. Shanbhag and T. Zheng and E. Litvinov and S. P. Meyn},
Keywords = {Convex hull price, electricity markets, uplift payments, nondifferentiable optimization, Lagrangian relaxation.},
Note = {Proceedings {PESGM} (submitted Nov., 2010)},
Title = {An Extreme-Point Global Optimization Technique for Convex Hull Pricing},
Year = {2011}}