Doesn't mixed complementarity constraint require lower and upper bounds on the variable?

[hurak]

The package promises a support for the Mixed Complementarity Problem (MCP). From the short description in the QuickStart guard it appears that it is just the Linear Complementarity Problem (LCP), that is supported instead. Am I right?

[dfridovi]

Nope - this supports general MCPs, i.e. the functions G(.) and H(.) need not be linear in x and y. The example in the readme was just an LCP though as you’ve identified. Regarding lower and upper bounds, this package and the description in the readme follow the definition of MCPs provided in chapter 1 of the book by Facchinei and Pang; there are other equivalent formulations though and PrimalDualMCP structs can be constructed with lower and upper bounds (with some caveats per the docstrings of those functions). Does this help?

[hurak]

Thanks for the response.

I have checked the reference you give. Indeed, they define MCP (MiCP, as they call it) the way you describe. That is, besides the (nonlinear) complementarity constraint given by $0\leq v \bot H(u,v) \geq 0$ they also impose the additional constraint $G(u,v) = 0$.

I think I might need some time to see if it is consistent with the definitions used elsewhere, in particular the existence of lower and upper bounds (by quickly looking at your source code, I cannot find any discussion of these in the docstrings). Besides the Wikipedia pages I have already linked, this is how MCP is understood in JuMP: https://jump.dev/JuMP.jl/stable/tutorials/nonlinear/complementarity/. Similarly in PATH: as described in their paper.

I would not be surprised to learn that these two formulations are somehow equivalent. It is just that at this moment I cannot see it.

Perhaps it can be useful for the authors of the package to learn that there are potential users of their package who are coming with a different definition of MCP in mind.

[dfridovi]

Yep 100% agree. One day soon there should be a tutorial on this - whether it is here or in ParametricMCPs I am not yet sure. For the moment, you can see the connection by reading off the KKT conditions:

• the G(x, y) = 0 part corresponds to “gradient of Lagrangian wrt primal variables is zero, and equality constraints must be satisfied” parts of KKT
• the 0 \le H(x, y) \perp y \ge 0 similarly reconstructs the inequality constraints on the primal and appropriate dual variables, and complementarity

So, this establishes the correctness of the G-H formulation. To see the connection fully, we can reconstruct these conditions from the lower and upper bound formulation:

• define K(x, y) = [G; H]
• define z = [x; y]
• Write out the formulation for the MCP as K(z) \perp lb \le z \le ub, where lb = -\infty for entries corresponding to y and lb = 0 for entries corresponding to x; ub = \infty for all entries
  • for entries where z = lb = 0 we see that K \ge 0 recovers primal feasibility for inequality conditions, ie. H \ge 0, and part of complementarity
  • otherwise, z will never be equal to \pm \infty so we will force K = 0, which recovers the other part of complementarity and Lagrangian stationarity

[dfridovi]

Closing this issue for now. Please do reopen it (or a separate one) as appropriate!