Groupe d’études et de recherche en analyse des décisions

Finding Global Optima of Convex Quadratic Programs with Complementarity Constraints

John E. Mitchell

Mathematical programs with complementarity constraints constitute a powerful modeling paradigm. Applications include inverse optimization problems, hierarchical optimization problems, and Stackelberg Games. In this talk, we present a logical Benders decomposition approach for finding global optima of convex quadratic programs with complementarity constraints. The approach is also capable of verifying infeasibility or unboundedness, as appropriate. We discuss several algorithmic refinements, including the use of semidefinite programming to construct modified instances that are easier to solve. Computational results are given.