The Complementarity Problem

Problems of the form

F(x) >=0
x >=0
F_i(x) x_i>=0, i=1,...,n .

If F depends linearly on x, then we have a linear, otherwise a nonlinear complementarity problem. Problems of this type occur often e.g. in mechanics, finance and games. Linear complementarity problems typically are solved by so called principal pivoting algorithms and nonlinear ones by a nonsmooth nonlinear equations approach using appropriate variants of the damped Newton's method e.g.

with Hi(x)=SQRT( Fi2 (x)+xi2)-Fi (x)-xi

Systems of equations, various pieces of software, mostly in Matlab, documentation, testproblems, net-submission and other info see:

Michael Ferris' webpage
AMPL interface to PATH
List of complementarity problems and software