An Extreme-Point Subdifferential Method for Convex Hull Pricing in Energy and Reserve Markets—Part I: Algorithm Structure

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 not easy to obtain. A common approach relies on re-solving the dispatch problem with the commitment decisions fixed, and utilizing the associated dual variables. This avenue may lead to inadequate revenues to generators, which has led to the introduction of uplift payments made by the market operator for further compensating the generators. An alternative pricing mechanism known as convex hull pricing has been proposed to reduce or eliminate uplift payments. Computation of these prices requires the global maximization of an associated Lagrangian dual problem. In this paper, we present an extreme-point-based procedure for obtaining a global maximizer. Unlike standard subgradient schemes where an arbitrary subgradient is used, we present an extreme-point subdifferential (EPSD) algorithm; this is a novel technique in which the steepest ascent direction is constructed by solving a continuous quadratic program. The EPSD algorithm initiates a move along this direction, employing an a priori constant steplength, with the intent of reaching the boundary of the face. A backtracking scheme selects a steplength that ensures descent with respect to a suitably defined merit function. As most electricity markets today co-optimize energy and reserves, an extension of the proposed convex hull pricing algorithm is provided for such integrated markets. Under suitable assumptions, we compare outcomes of energy-only and energy-reserve co-optimized markets under different pricing and uplift rules. In these examples, pricing rules have a major impact on the total payment while the uplift payment only accounts for a small portion of it. We also observe that it remains unclear whether marginal-cost pricing or convex-hull pricing leads to higher total payment.