Convexification techniques for linear complementarity constraints

Trang T. Nguyen, Jean Philippe P. Richard, Mohit Tawarmalani

Research output: Contribution to journalArticlepeer-review


We develop convexification techniques for mathematical programs with complementarity constraints. Specifically, we adapt the reformulation-linearization technique of Sherali and Adams (SIAM J Discrete Math 3, 411–430, 1990) to problems with linear complementarity constraints and discuss how this procedure reduces to its standard specification for binary mixed-integer programs. Then, we consider specially structured complementarity sets that appear in KKT systems with linear constraints. For sets with a single complementarity constraint, we develop a convexification procedure that generates all nontrivial facet-defining inequalities and has an appealing “cancel-and-relax” interpretation. This procedure is used to describe the convex hull of problems with few side constraints in closed-form. As a consequence, we delineate cases when the factorable relaxation techniques yield the convex hull from those for which they do not. We then discuss how these results extend to sets with multiple complementarity constraints. In particular, we show that a suitable sequential application of the cancel-and-relax procedure produces all nontrivial inequalities of their convex hull. We conclude by illustrating, on a set of randomly generated problems, that the relaxations we propose can be significantly stronger than those available in the literature.

Original languageEnglish (US)
JournalJournal of Global Optimization
StateAccepted/In press - 2021

Bibliographical note

Funding Information:
This work was supported by NSF CMMI Grants 0856605, 0900065, 1234897, and 1235236.

Publisher Copyright:
© 2021, The Author(s), under exclusive licence to Springer Science+Business Media, LLC part of Springer Nature.

Copyright 2021 Elsevier B.V., All rights reserved.


  • Complementarity constraints
  • Convex hulls
  • Cutting planes
  • Fractional factors
  • Lift-and-project
  • Reformulation- linearization-technique

Fingerprint Dive into the research topics of 'Convexification techniques for linear complementarity constraints'. Together they form a unique fingerprint.

Cite this