Copositive Duality for Discrete Markets and Games

Understand

Optimization problems with discrete decisions are nonconvex and thus lack strong duality, which limits the usefulness of tools such as shadow prices and the KKT conditions.

• 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 in two ways.