An Introduction to Variational Inequalities

Part1: An Introduction to Variational Inequalities

This is the first part of a series of post on the optimization of GANs. In this first post I will present a framework from optimization called Variational Inequality (VI).

Motivation

Example 1: Finding the (local) minimums of a function

Let’s consider a smooth function $f: [a,b] \rightarrow \mathbb{R}$, we’re interested in finding the points $x^*$ s.t.:

$$x^* = \arg\min_{x \in [a,b]} f(x)$$

Three cases can occur:

• $a < x^* <b$, and $f’(x^*)=0$
• $x^*=a$, and $f’(x^*) \geq 0$
• $x^*=b$, and $f’(x^*) \leq 0$

These statements can be summarized by:

$$f'(x^*)(x-x^*) \geq 0 \forall x \in [a,b]$$

This inequality is called a Variational Inequality (VI).

Notes:

• A minimum necessarily satisfies the VI, but a point satisfying the VI is not necessarily a minimum.
• if $f$ is a convex function then x is a minimum of the function if and only if it satisfies the VI.

Example 2: Finding a (local) Nash equilibrium in a two-player games.

Let’s consider two smooth functions $f: \Theta \rightarrow \mathbb{R}$, $g: \Phi \rightarrow \mathbb{R}$ where $\Theta \in \mathbb{R}^{N_\theta}$ and $\Phi \in \mathbb{R}^{N_\phi}$, we’re interested in finding a point $x^*=(\theta^*,\phi^*)$ s.t.:

$$f(\theta^*) = \arg\min_{\theta \in \Theta} f(\theta)$$ $$g(\phi^*) = \arg\min_{\phi \in \Phi} f(\phi)$$

Such a point is called a Nash equilibrium, we can also generalize this notion to games with more players. (Write Def of Nash Equlibrium)

Notes:

• A minimum necessarily satisfies the VI, but a point satisfying the VI is not necessarily a minimum.
• if $\Theta$ and $\Phi$ are two convex sets and $f$ and $g$ are two convex functions, then x is a Nash equilibrium if and only if