Komplementaritetsproblemet

Komplementaritetsproblemet refers to a class of problems in mathematical optimization. At its core, it involves finding a solution that satisfies a set of conditions, where some of these conditions are inequalities and others are equations. Specifically, a complementarity problem typically seeks a vector x such that:

1. Mx + q >= 0

2. x >= 0

3. x^T(Mx + q) = 0

Here, M is a matrix and q is a vector. The third condition, known as the complementarity condition, is the defining characteristic. It states that for each component i, either the i-th component of Mx + q is non-negative, or the i-th component of x is non-negative, but not both can be strictly positive. In other words, for each pair of corresponding components, at least one must be zero.

This problem formulation is very general and can encompass many other types of optimization problems. For instance, linear programming problems can be reformulated as linear complementarity problems (LCPs). Quadratic programming problems can also be transformed into LCPs. Furthermore, certain game theory problems and equilibrium models can be expressed in this framework.

Solving complementarity problems can be challenging. Various algorithms exist, including pivoting methods (like Lemke's algorithm), interior-point methods, and descent methods, each with its own strengths and weaknesses depending on the properties of the matrix M. The theoretical and algorithmic aspects of complementarity problems are an active area of research within operations research and applied mathematics.