Variational Inequality
Given a subset $K$ of the Euclidean $n$-dimensional space $\mathbb{R}^{n}$ and a mapping $F: K \rightarrow \mathbb{R}^{n}$, the variational inequality, denoted $\text{VI}(K, F)$, is to find a vector $x \in K$ such that $$ (y-x)^{T} F(x) \geq 0, \quad \forall y \in K $$
The set of solutions to this problem is denoted $\text{SOL}(K, F)$ .
We always assume the set $K$ is closed and the function $F$ is continuous, and it follows that $\text{SOL}(K, F)$ is a closed set.
Equivalently, if $K$ is closed and convex, by using normal cone, we have a more succinct representation $$ \begin{gathered} 0 \in F(x) + \mathrm{N}_K(x) \\ \text{where} \quad \mathrm{N}_K(x) = \{d \mid \langle d, y - x \rangle \leq 0 \; \text{ for all } y \in K\} \end{gathered} $$
Shown by the picture below
When $K = \mathbb{R}^n$, it reduces to $F(x) = 0$ ; in other words, $\text{SOL}(\mathbb{R}^n, F) = F^{-1}(0)$
Existence of Solutions
If $K$ is compact and $F$ is continuous on $K$, then the $\text{VI}(K, F)$ admits at least one solution.
Monotonicity
The function $F$ is monotone on $K$ if $$ \langle F(x_1) - F(x_2), x_1 - x_2 \rangle \geq 0, \quad \forall x_1, x_2 \in K $$ The function $F$ is strictly monotone on $K$ if $$ \langle F(x_1) - F(x_2), x_1 - x_2 \rangle > 0, \quad \forall x_1, x_2 \in K, x_1 \neq x_2 $$
Complementarity Problem
When $K$ is a cone, the $\text{VI}$ admits an equivalent form known as a complimentarity problem .
Given a cone $K$ and a mapping $F: K \rightarrow \mathbb{R}^{n}$, the complementarity problem, denoted $\text{CP}(K, F)$, is to find a vector $x \in \mathbb{R}^{n}$ satisfying the following conditions:
$$ K \ni x \perp F(x) \in K^{\ast} $$
We obtain the $\text{CP}(K, F)$ in the following form
$$ x \in K, \quad F(x) \in K^{\ast}, \quad \langle x, F(x) \rangle=0 $$
Let $K$ be a cone in $\mathbb{R}^n$. A vector $x$ solves the $\text{VI}(K, F)$ if and only if $x$ solves the $\text{CP}(K, F)$ .
When $K$ is the nonnegative orthant of $\mathbb{R}^n_{+}$ , $K=K^\ast$, the $\text{CP}(K, F)$ is known as the nonlinear complementarity problem and denoted $\text{NCP}(F)$ . The formulation of $\text{NCP}(F)$ is $$ x \geq 0, \quad F(x) \geq 0, \quad x_iF_i(x) = 0, \;\;\forall i = 1, \dots, n $$
If $F$ is affine, it is called linear complimentarity problem ($\text{LCP}$).
Constrained Optimization Problems and VI
Consider the constrained optimization problem $$ \begin{aligned} \min \; & \theta (x) \\ \text{s.t. } & x \in K \end{aligned} $$ If the objective function $\theta$ is continuously differentiable and the set $K$ is convex, then any local minimizer $x$ must satisfy $$ (y - x)^T \nabla \theta(x) \geq 0, \quad \forall y \in K $$ The inequality above implies that any feasible direction at $x$ is not a decent direction.
$\text{VI}(K, \nabla \theta)$ is called the stationary point problem. A solution to $\text{VI}(K, \nabla \theta)$ is called a stationary point.
It is well-known that if $\theta$ is a convex function, then every stationary point is a global minimum of the optimization problem.
As for the nonconvex case ( $K$ is not convex), if $x$ is a local minimizer, then $$ (y-x)^T \nabla \theta(x) \geq 0, \quad \forall y \in x + T_K(x) $$ The above inequality is an instance of a quasi-variational inequality, abbreviated as $\text{QVI}$, in which the defining set of the problem varies with the variable, ie. $K(x)$.
Notice that if $F(x)$ is identically equal to zero, the $\text{QVI}$ reduces to the problem of finding a vector x satisfying $x \in K(x)$. Such a vector is called a fixed point of the point-to-set map $K$.
Equivalent Formulations
Equation reformulations
Let $K$ be a closed convex set. The defining inequality for $\text{VI}(K, F)$ is $$ \langle y-x, F(x) \rangle \geq 0, \quad \forall y \in K \;\; \Longleftrightarrow \;\; (y-x)^T (x-(x-F(x))) \geq 0, \quad \forall y \in K $$ Which is equivalent to $$ x = \mathrm{p}_K(x - F(x)) $$ Define $\mathbf{F}_{K}^{\mathrm{nat}}(x) \equiv x-\mathrm{p}_{K}(x-F(x))$, which yields a equivalent equation reformulation of $\text{VI}(K, F)$ $$ x \in \operatorname{SOL}(K, F) \;\;\Longleftrightarrow \;\; \mathbf{F}_{K}^{\mathrm{nat}}(x)=0f $$
Merit functions
A different approach is to cast the $\text{VI/CP}$ as a minimization problem.
A merit function for the $\text{VI}(K, F)$ on a (closed) set $X \supseteq K$ is a nonnegative function $\theta : X \to \mathbb{R}_+$ such that $x \in \text{SOL}(K, F)$ if and only if $x \in X$ and $\theta(x) = 0$ .
So the solutions to $\text{VI}(K, F)$ coincide with the global solutions of the optimization problem $$ \begin{aligned} \min \; & \theta(y) \\ \text{s.t. } & y \in X \end{aligned} $$
Specifically, the gap function for $\text{VI}(K, F)$ is defined as $$ \theta_{\text{gap}} (x) = \sup_{y \in K} \langle x- y, F(x) \rangle $$
Source Problems
Saddle problems
Let $L: \mathbb{R}^{n+m} \rightarrow \mathbb{R}$ denote an arbitrary saddle function; let $X \subseteq \mathbb{R}^{n}$ and $Y \subseteq \mathbb{R}^{m}$ be two given closed sets. The saddle problem associated with this triple $(L, X, Y)$ is to find a pair of vectors $(x, y) \in X \times Y$, called a saddle point, such that $$ L(x, v) \leq L(x, y) \leq L(u, y), \quad \forall(u, v) \in X \times Y $$ When $L$ is continuously differentiable and “convex-concave”, and $X$ and $Y$ are convex sets, the saddle problem can be formulated as a $\text{VI}$ . $(x, y)$ is a saddle point if and only if $(x, y)$ solves the $\text{VI}(X \times Y, F)$, where $$ F(x, y) \equiv \begin{pmatrix} \nabla_x L(x, y) \\ -\nabla_y L(x, y) \end{pmatrix} $$
Nash equilibrium problems
In a general noncooperative game, there are $N$ players each of whom has a certain cost function $\theta_i(\mathbf{{x}}) = \theta_i(x_i, \mathbf{x}_{-i})$ and strategy set $K_i$
By solving a $\text{VI}$, a Nash equilibrium can be obtained under some conditions.
If $K_i$ is closed and convex, each cost function is convex and continuously differentiable, then $\mathbf{{x}}$ is a NE if and only if for each $i=1, \dots, N$ $$ \left(y^{i}-x^{i}\right)^{T} \nabla_{x^{i}} \theta_{i}(\mathbf{x}) \geq 0, \quad \forall y^{i} \in K_{i} $$ by concatenating these individual $\text{VI}$s, it follows easily that $\mathbf{x}$ must solve $$ (\mathbf{y}-\mathbf{x})^{T} \mathbf{F}(\mathbf{x}) \geq 0, \quad \forall \mathbf{y} \in \mathbf{K} $$ Where $$ \mathbf{K} \equiv \prod_{i=1}^{N} K_{i} \quad \text { and } \quad \mathbf{F}(\mathbf{x}) \equiv\left(\nabla_{x^{i}} \theta_{i}(\mathbf{x})\right)_{i=1}^{N} $$ In an extension of the above Nash game, each player $i$’s strategy set can depend on other players’ strategies. In this generalized context, the resulting $\text{VI}$ is of the $\text{QVI}$ type.