Complementarity Problems

Back to Complementarity Problems and Variational Inequalities

Fundamental to all complementarity problems are the complementarity conditions, each of which requires the product of two (or more) non-negative quantities to be zero. Mathematically, \(x\) is complementary to \(y\) if
\[x \geq 0, y \geq 0, \mbox{and } x^T y = 0,\]
which is typically written as
\[0 \le x\perp y \ge 0.\]

Linear Complementarity Problems

Given a square matrix \(M \in \mathbb{R}^{n x n}\) and a column vector \(q \in \mathbb{R}^n\), the Linear Complementarity Problem (LCP) is to find \(w = (w_1, \cdots, w_n)^T\) and \(z = (z_1, \cdots, z_n)^T\) satisfying
\[\begin{array}{lll}
w - Mz & = & q \\
w & \geqq & 0 \\
z & \geqq & 0 \\
w_i z_i & = & 0 \quad \forall i = 1, \cdots, n
\end{array}\]

LCPs are important problems in the field of optimization in that the optimality criterion for linear programming and the necessary optimality conditions for quadratic programming can be expressed as LCPs. LCPs also arise naturally in applications in economics, engineering and science.

Nonlinear Complementarity Problem

The Nonlinear Complementarity Problem (NCP) is to find a vector \(x \in \mathbb{R}^n \) satisfying the system of equations and inequalities
\(x \ge 0, \quad\quad F(x) \ge 0, \quad\quad x^TF(x)=0 \quad\quad\)
or, equivalently,
\(x_i \ge 0, \quad\quad F_i(x) \ge 0, \quad\quad x_i{^T}F_i(x)=0 \quad\quad \) for \(\quad i=1,...,n \,.\)

\(F:X \rightarrow \mathbb{R}^n\) is a given function defined on a subset \(X \subseteq \mathbb{R}\) containing at least the nonnegative orthant.

Online and Software Resources

Applications

References

  • Cottle, R. W. 2004. Lecture notes for MS&E 316 Complementarity and Equilibrium Problems. Stanford University
  • Ferris, M. C. and Kanzow, C. 2002. ''Complementarity and Related Problems'', in Handbook of Applied Optimization, P.M. Paradalos and M.G.C. Resende eds., Oxford University Press, New York, pp. 514-530.
  • Murty, K. G. 1988. Linear Complementarity, Linear and Nonlinear Programming, Helderman-Verlag, Berlin. Internet Edition prepared by V.F. Yu, National Taiwan University of Science and Technology.