Systems | Information | Learning | Optimization

Copositive Duality for Discrete Markets and Games

Models including binary decisions are often modelled as mixed-integer programs (MIPs). Such models are nonconvex and lack strong duality, which prevents the use of tools such as shadow prices and KKT conditions. For example, in convex markets, shadow (dual) prices are associated with market equilibrium, and for convex games the existence and uniqueness of Nash equilibrium can be proven via fixed-point theorem and KKT conditions. Those results are lacking in their nonconvex counterparts. We use copositive programming to formulate discrete problems in applications including nonconvex energy markets and nonconvex games, to leverage its convexity and strong duality features. We obtain several novel theoretical and numerical results for those applications, including a new revenue-adequate pricing scheme for energy markets, and existence, uniqueness, and KKT conditions for the pure-strategy Nash equilibrium in discrete games. We also propose a novel and purely MIP-based cutting-plane algorithm for mixed-integer copositive programs, and employ it in our applications. This is a joint work with Cheng Guo and Josh A. Taylor.
April 14 @ 12:30
12:30 pm (1h)


Merve Bodur