Seminar: Copositive Duality for Discrete Markets and Games by Merve Bodur
Seminar
Department of Industrial Engineering
Copositive Duality for Discrete Markets and Games
Merve Bodur
Department of Mechanical and Industrial Engineering
University of Toronto
Abstract: 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.) Short Bio: 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, multi-objective optimization and combinatorial optimization, with applications in a variety of areas such as scheduling, transportation, power systems, healthcare and telecommunications.
University of Toronto
Abstract: 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.) Short Bio: 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, multi-objective optimization and combinatorial optimization, with applications in a variety of areas such as scheduling, transportation, power systems, healthcare and telecommunications.
Date: Friday, February 26, 2021
Time: 15:00-16:00.
Online Seminar Link:
https://boun-edu-tr.zoom.us/j/96945572901?pwd=UWRMdXV2QmdsS3JrUFpocEtiZ3hVQT09
Meeting ID: 969 4557 2901
Passcode: 335897
