ISyE Seminar Series: Merve Bodur
"Copositive Duality for Discrete Markets and Games"
Presentation by Professor Merve Bodur
Wednesday, January 27
About the seminar:
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.)
Copositive Duality for Discrete Markets and Games (pdf)
Merve Bodur is an Assistant Professor in the Department of Mechanical and Industrial Engineering at the University of Toronto. She also holds a Dean’s Spark Professorship in the Faculty of Applied Science and Engineering. Currently, she is the INFORMS Optimization Society Vice Chair of Integer and Discrete Optimization. She obtained her Ph.D. from University of Wisconsin-Madison and did a postdoc at Georgia Institute of Technology. She received her B.S. in Industrial Engineering and B.A. in Mathematics from Bogazici University, Turkey. Her research interests include stochastic programming, integer programming, multiobjective optimization and combinatorial optimization, with applications in a variety of areas such as scheduling, transportation, power systems, healthcare and telecommunications.