Graduate Seminar: Convexification Techniques for Linear Complementarity Constraints

GAINESVILLE: J. P. Richard, Associate Professor of Industrial and Systems Engineering at the University of Florida, will deliver the graduate seminar “Convexification Techniques for Linear Complementarity Constraints,” at 4:05 p.m. on Thursday, October 6 in McCarty Hall Room 2186.

In this talk, convexification techniques for linear programs with linear complementarity constraints (LPCCs) are discussed. In particular, we generalize the reformulation-linearization technique of Sherali and Adams to problems with linear complementarity constraints and discuss how it reduces to the standard technique for binary mixed-integer programs (BMIPs). Then, we consider specially structured sets with complementarity constraints that appear in KKT systems and show that their convex hulls can be obtained using MIP convexification techniques. For these sets, we study further the case where a single complementarity constraint is imposed and show that all nontrivial facet-defining inequalities can be obtained through a simple “cancel-and-relax” procedure. We use this result to identify special cases where McCormick inequalities suffice to describe convex hulls and other cases where these inequalities are not sufficient. We then discuss various tools that can be used to extend these results to sets with multiple complementarity constraints. We conclude by illustrating on a small set of randomly generated problems, that the relaxations produced by the techniques we derived can be significantly stronger than those proposed in the literature.