4.3 Complementarity problems and their relation to variational inequalities

Complementarity problems are a crucial concept in variational analysis. They involve finding vectors that satisfy specific inequalities and complementarity conditions, with applications in economics, engineering, and optimization. These problems are closely related to variational inequalities.

The connection between complementarity problems and variational inequalities is significant. Under certain conditions, complementarity problems can be reformulated as equivalent variational inequalities, allowing for the application of powerful variational inequality techniques to solve them.

Complementarity Problems: Definition and Formulation

Definition and Mathematical Formulation

Top images from around the web for Definition and Mathematical Formulation

• 

  Frontiers | Boundary Integral Formulation of Frictionless Contact Problems Based on an Energetic ... View original

  Is this image relevant?

• 

  Modulus-Based Matrix Splitting Iteration Methods for a Class of Stochastic Linear ... View original

  Is this image relevant?

• 

  Robotics and Automation Engineering Journal | Juniper Publishers View original

  Is this image relevant?

• 

  Frontiers | Boundary Integral Formulation of Frictionless Contact Problems Based on an Energetic ... View original

  Is this image relevant?

• 

  Modulus-Based Matrix Splitting Iteration Methods for a Class of Stochastic Linear ... View original

  Is this image relevant?

1 of 3

Top images from around the web for Definition and Mathematical Formulation

• 

  Frontiers | Boundary Integral Formulation of Frictionless Contact Problems Based on an Energetic ... View original

  Is this image relevant?

• 

  Modulus-Based Matrix Splitting Iteration Methods for a Class of Stochastic Linear ... View original

  Is this image relevant?

• 

  Robotics and Automation Engineering Journal | Juniper Publishers View original

  Is this image relevant?

• 

  Frontiers | Boundary Integral Formulation of Frictionless Contact Problems Based on an Energetic ... View original

  Is this image relevant?

• 

  Modulus-Based Matrix Splitting Iteration Methods for a Class of Stochastic Linear ... View original

  Is this image relevant?

1 of 3

• Complementarity problems find a vector x satisfying a system of inequalities and complementarity conditions
• The standard mathematical formulation is: Find x such that $F(x) \geq 0$, $x \geq 0$, and $x^T F(x) = 0$, where F maps from $R^n$ to $R^n$
• The complementarity condition $x^T F(x) = 0$ means for each component i, either $x_i = 0$ or $F_i(x) = 0$, or both ($x_i$ and $F_i(x)$ cannot both be positive)
• Common types include the linear complementarity problem (LCP) and the nonlinear complementarity problem (NCP)

Applications and Importance

• Complementarity problems arise in various fields, such as economics (market equilibrium), engineering (contact mechanics), and optimization (KKT conditions)
• They often appear in the context of equilibrium or optimality conditions
• Solving complementarity problems is crucial for understanding and analyzing systems in these domains
• Examples:
  • In economics, complementarity problems can model supply and demand equilibria in markets
  • In contact mechanics, they can describe the contact forces between objects

Complementarity Problems vs Variational Inequalities

Relationship between Complementarity Problems and Variational Inequalities

• Complementarity problems can be reformulated as equivalent variational inequalities under certain conditions
• For a complementarity problem: Find x such that $F(x) \geq 0$, $x \geq 0$, and $x^T F(x) = 0$, the corresponding variational inequality is: Find $x \geq 0$ such that $(y - x)^T F(x) \geq 0$ for all $y \geq 0$
• The equivalence holds when the feasible set of the variational inequality is a cone (a set closed under nonnegative scalar multiplication)

Advantages of the Variational Inequality Formulation

• The reformulation allows the application of variational inequality theory and solution methods to solve complementarity problems
• Variational inequalities provide a more general framework that encompasses complementarity problems
• Many results and techniques from variational inequality theory can be directly applied to complementarity problems
• The variational inequality formulation can offer insights into the structure and properties of complementarity problems

Converting Complementarity Problems to Variational Inequalities

Conversion Process

• To convert a complementarity problem into a variational inequality, define the feasible set K as the nonnegative orthant: $K = \{x \in R^n : x \geq 0\}$
• The complementarity problem: Find x such that $F(x) \geq 0$, $x \geq 0$, and $x^T F(x) = 0$, is equivalent to the variational inequality: Find $x \in K$ such that $(y - x)^T F(x) \geq 0$ for all $y \in K$
• The variational inequality formulation captures the complementarity conditions through the choice of the feasible set K and the inequality constraint

Applicability and Examples

• The conversion process is straightforward and can be applied to both linear and nonlinear complementarity problems
• Examples:
  • A linear complementarity problem (LCP) with matrix M and vector q can be converted to a variational inequality with $F(x) = Mx + q$ and $K = \{x \in R^n : x \geq 0\}$
  • A nonlinear complementarity problem (NCP) with function F can be converted to a variational inequality with the same F and $K = \{x \in R^n : x \geq 0\}$

Solving Complementarity Problems with Variational Inequality Techniques

Solution Methods from Variational Inequality Theory

• Variational inequality theory provides a rich set of tools and algorithms for solving complementarity problems reformulated as variational inequalities
• The projection method is a fundamental iterative algorithm for solving variational inequalities, which can be applied to solve complementarity problems
• The basic projection method involves iteratively updating the solution by projecting onto the feasible set K and taking a step in the direction of the function F
• Other solution techniques for variational inequalities, such as extragradient methods, proximal point algorithms, and splitting methods, can also be employed to solve complementarity problems

Convergence Analysis and Considerations

• Convergence results and error bounds for the projection method can be derived using the properties of the function F, such as monotonicity ($(F(x) - F(y))^T(x - y) \geq 0$ for all $x, y$) and Lipschitz continuity ($\|F(x) - F(y)\| \leq L\|x - y\|$ for some $L > 0$)
• The choice of the solution method depends on the specific structure of the complementarity problem, such as linearity, convexity, and smoothness of the function F
• Examples:
  • For a linear complementarity problem (LCP), the projection method can be simplified to a quadratic programming subproblem at each iteration
  • For a nonlinear complementarity problem (NCP) with a smooth function F, the semismooth Newton method can be applied, which exploits the complementarity structure