26. Complementarity

Mixed complementarity problems, or box-constrained variational inequalities, are related to nonlinear systems of equations. They are defined by a continuously differentiable function, , and bounds, and , on the variables such that . Given this information, is a solution to MCP(F, , u) if for each we have at least one of the following:

Note that when and we have a nonlinear system of equations, and and corresponds to the nonlinear complementarity problem [(ref cottle:nonlinear)].

Simple complementarity conditions arise from the first-order optimality conditions from optimization [(ref karush:minima),(ref kuhn.tucker:nonlinear)]. In the simple bound constrained optimization case, these conditions correspond to MCP( , , u), where is the objective function. In a one-dimensional setting these conditions are intuitive. If the solution is at the lower bound, then the function must be increasing and . However, if the solution is at the upper bound, then the function must be decreasing and . Finally, if the solution is strictly between the bounds, we must be at a stationary point and . Other complementarity problems arise in economics and engineering [(ref ferris.pang:engineering)], game theory [(ref nash:equilibrium)], and finance [(ref huang.pang:option)].

Evaluation routines for F and its Jacobian must be supplied prior to solving the application. The bounds, , on the variables must also be provided. If no starting point is supplied, a default starting point of all zeros is used.