Mixed complementarity problem (MCP)

 Top  Previous  Next

Mathematically, the Mixed Complementarity Problem (MCP) looks like:

Solve for Z such that

 

Fi(Z) = 0 and Li < Zi < Ui

or

Fi(Z) > 0 and Zi = Li

or

Fi(Z) < 0 and Zi = Ui

where

Zi is a set of variables to be set

F(Z) is a (possibly nonlinear) function

Li and Ui are a set of upper and lower bounds on the variables, where Li may be –inf and Ui may be +inf

The number of Zi variables and the number of relations Fi(Z) is equal.

This problem can be written compactly as

F(Z)┴ L < Z < U

where the ┴ ("perp") symbol indicates pair-wise complementarity between the function F and the variable Z and its bounds.  This problem does not have an objective function.

A common special case of the MCP that illustrates the basic complementarity nature of the problem.

 F(Z) ┴ Z > 0

which is often written as F(Z) ≥ 0, Z ≥ 0,  F(Z) *Z = 0.  In this case, the lower bound on Z implies that F(Z) ≥ 0, with equality holding when Z is nonzero.  None of this rules out the degenerate case (i.e. where a binding F(Z) has a zero complementary variable Z) but  this can make for a difficult model to solve.

Another special case arises when the bounds L and U are infinite, since Z is always between its bounds.  In such a case, the function F(Z) will always equal zero and the MCP then reduces to a square but in general non linear system of equations.

The MCP problem structure imposes particular requirements on specification of the equations F(Z) in the problem.  This implies a couple of things.

•It is always acceptable to write the equations defining the problem with =N= relations.  In this case, the bounds on F(Z) are implied by the equation/variable matching and the variable bounds.
•If the variable Z matched to F(Z) has lower bounds only (e.g  if Z in GAMS terms is a positive variable) then it is acceptable to write the equation defining F with =G= relations, since this is consistent with the constraint implied by the lower bound on Z.
•A variable bounded only above can be matched with =L= equations.
•Free variables without bounds can be matched with =E= equations.
•If Z has both bounds then the inequality type of the F(Z) equation is indefinite and =N= must be used.
•You can write the constraints of an LP or NLP when writing down its KKT conditions as an MCP, as long as you declare the constraint inequalities and the sign restrictions on the dual multipliers correctly.  By convention, the matching between GAMS equations and their .m values is correct in the sense of MCP for minimization models, while maximization models need to have the sign of the multiplier reversed.

A familiar example of complementary relationship is found in the complementary relationship between the binding nature of the constraints in a problem and the associated dual multipliers: if a constraint is non-binding its dual multiplier must be zero (i.e. at bound) while if a dual multiplier is nonzero the associated constraint must be binding.  In fact, the Kuhn Karush Tucker conditions or theoretical conditions that characterize many model types in economics (especially in the general equilibrium class) and engineering can be expressed as an MCP.  See http://www.cs.wisc.edu/cpnet/ for more discussion of this class of problems.

Complementarity problems are easily specified in GAMS. The only additional requirement is the definition of complementarity pairs as discussed in the Variables, Equations, Models and Solves chapter or in the NLP and MCP Model Types chapter.

For information on the names of the solvers that can be used on the MCP problem class see the section on Solver Model type Capabilities.