Copositive Duality for Discrete Energy Markets

Optimization problems with discrete decisions are nonconvex and thus lack strong duality, which limits the usefulness of tools such as shadow prices. It was shown in Burer (2009) that mixed-binary quadratic programs can be written as completely positive programs, which are convex. Completely positive reformulations of discrete optimization problems therefore have strong duality if a constraint qualification is satisfied. We apply this perspective by writing unit commitment in power systems as a completely positive program, and then using the dual copositive program to design new pricing mechanisms. We show that the mechanisms are revenue-adequate, and, under certain conditions, supports a market equilibrium. To the best of our knowledge, one of our mechanisms is the first equilibrium-supporting scheme that uses only uniform prices. To facilitate implementation, we also design a cutting plane algorithm for solving copositive programs exactly, which we further speed up via a second-order cone programming approximation. We provide numerical examples to illustrate the potential benefits of the new mechanisms and algorithms.



View Copositive Duality for Discrete Energy Markets