Komplementaritetsproblemer

Komplementaritetsproblemer refers to a class of mathematical optimization problems where the goal is to find a solution that satisfies certain complementarity conditions. These conditions typically involve pairs of variables that must either be non-negative and their product zero, or one variable is zero and the other is non-negative, or both are zero. A common example is the Linear Complementarity Problem (LCP), which seeks a vector z such thatMz + q >= 0, z >= 0, and z^T(Mz + q) = 0, where M is a given matrix and q is a given vector.

The core idea behind complementarity problems is that for each pair of related variables, at least one must be zero. This constraint arises naturally in many fields. For instance, in economics, it can model market equilibrium where prices and quantities are non-negative, and if the price of a good is zero, its quantity demanded is zero (or vice versa). In engineering, complementarity problems are used in areas like structural mechanics for contact problems, where the force of contact and the penetration of surfaces must be complementary.

Solving complementarity problems can be challenging. Standard optimization techniques may not directly apply due to the non-smooth and non-convex nature of the complementarity conditions. Various algorithms have been developed, including pivoting methods like Lemke's algorithm for LCP, interior-point methods, and specialized algorithms for non-linear complementarity problems (NCPs). The existence and uniqueness of solutions are important theoretical considerations that depend heavily on the properties of the function or matrix involved in the problem formulation.