Variational Inequalities - What excatly does the definition say? Why are they useful?

Question

I am having issues understanding the definition of variational inequalities. We have the following definition:

Given a set $X \subset \mathcal{R}^n$ and a mapping $F: X \rightarrow \mathcal{R}^n$ a variational inequality problem consists of finding $x^*$ such that
$$ (x-x^* )^T F(x^*) \geq 0 \quad \quad \forall x \in X$$ If X is closed and F continous then the solution to VI(X,F) is a closed set.

What exactly does this mean? And what can it be used to?

I have a course in operations research and we just had about the KKT conditions and now we are learning about variational inequalities and complementarity problems.. however I cannot see the connection between these.

Hope someone can help

• Husky

Answer 1

My explanation below follows from varitional inequalities (VI) by Rockafeller.

The definition of VI says that $\langle F(x),x-x^*\rangle \geq 0$. Where F is some function from $C \rightarrow R^n$, C is a convex set; $x,x^* \in C$.The more general definition of VI is called varitional condition defined as: \begin{equation} 0 \in F(x) + N_C(x) \end{equation} where $N_C(x)$ is normal cone of the set C at $x$ shown below (set C replaced by A)

Mathematically, normal cone is defined as: \begin{equation} N_C(x) =\{d: \langle d,x-x^*\rangle\ \geq 0\quad \forall x^* \in C\} \end{equation}

When set $C= R^n_+$, then VI is called complementarity condition of the function $F$. To see this,let $F(x)=y=(y_1,y_2,...,y_n)$ and $x=(x_1,...,x_n)$. Now, generalized VI definition says that $0 \in y + N_{R^n_+}(x) \implies -y_i \in N_{R_+}(x_i) \forall i$. This means that $v_i =0$ when $x_i>0$ and $v_i \geq 0$ when $x_i =0$. Use the definition of normal cone above to have intuition why above is true.

Now, you have all the material of complementarity condition that says that the two vectors over which you are optimizing must be orthogonal. Here you have shown that $x$ and $y$ are orthogonal, i.e. $x^Ty = 0$.

Answer 2

Just for example, let $X\subset \mathbb{R}^2$ be a closed convex set and let $y$ be a point outside $X$. As you should know, there exists only one point $x^*\in X$ which has the least distance from $y$ (such a point is usually called orthogonal projection of $y$ onto $X$); more formally, $x^*$ satisfies the following inequality: $$\tag{1}|x-y|\geq |x^*-y|\qquad \forall x\in X\; .$$ Now you use convexity and (1) to get: $$0\leq |x^*-y|^2\leq \Big| tx +(1-t)x^* -y\Big| = |x-x^*|^2 t^2 +2 (x-x^*)^T\cdot (x^*-y) t + |x^*-y|^2$$ for every $t\in ]0,1]$; therefore you obtain: $$|x^*-x|^2 t - (x-x^*)^T\cdot (y-x^*)\geq 0\; .$$ Letting $t\to 0^+$ you have the variational inequality: $$\tag{2} (x-x^*)^T\cdot F(x^*)\geq 0\qquad \forall x \in X\; ,$$ where $F:\mathbb{R}^2\to \mathbb{R}^2$ with $F(x):= y-x$. On the other hand, you can prove that (2) implies (1) by evaluating the difference $|x^*-y|^2 - |x-y|^2$.

Therefore the variational inequality (2) is equivalent to the minimality condition which defines the orthogonal projection.

This is almost a quite general fact: many problems of applied mathematics (e.g., static and dynamic traffic equilibrium problems, Cournot-Nash equilibrium problems, etc...) involving minimality condition are equivalent to suitable variational inequalities. This makes variational inequalities worth studying.