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
- Complementarity Solvers on the NEOS Server
- Optimization Online Complementarity and Variational Inequalities area
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.