Complementarity problems occur in many application areas. They can be used to model free boundary problems, disjunctive constraints (either-or constraints), the notion of switching between systems of equations and the optimality conditions of optimization problems. 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 \]
or, equivalently,
\[ x_i \ge 0, \quad\quad F_i(x) \ge 0, \quad\quad x_i{^T}F_i(x)=0 \] for \(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.
Applications
- A survey of applications is found at: Michael C. Ferris and Jong Shi Pang, Engineering and Economic Applications of Complementarity Problems, SIAM Review 39 (1997) pp. 669–713.
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.