Convexification techniques for linear complementarity constraints

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

Research output: Contribution to journalArticlepeer-review

Abstract

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)
Pages (from-to)249-286
Number of pages38
JournalJournal of Global Optimization
Volume80
Issue number2
DOIs
StatePublished - Jan 27 2021

Bibliographical note

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

Keywords

  • 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