Variational Inequalities (VI)

Table of Contents

Variational inequalities provide a general mathematical framework for many problems arising in optimization. For example, constrained optimization problems like LP and NLP are special cases of VI, and systems of equations and complementarity problems can be cast as VI. Thus VI problems have many applications, including those in transportation networks, signal processing, regression analysis, and game theory.

In this section we present a mathematical formulation of VI, give an example of how VI can be modeled with GAMS EMP, and introduce the EMP annotations specific to VI. Note that to fully and properly understand some of this section, the introduction to MCP provides a useful background.

Variational Inequalities: Mathematical Formulation

For a given continuous function \(F: \mathbb{R}^n \rightarrow \mathbb{R}^n\) and a fixed closed convex set \(K \subset \mathbb{R}^n\) the variational inequality problem \(VI(F,K)\) is to find a point \(x^* \in K\) such that:

\begin{equation} \langle F(x^*), (x-x^*) \rangle \geq 0, \quad \forall x \in K, \tag {7} \end{equation}

where \(\langle \cdot, \cdot \rangle \) denotes the usual inner product.

Observe that the VI generalizes many problem classes:

  • If \(F(x)=0\) and \(K \equiv \mathbb{R}^n\), the VI is a system of nonlinear equations.
  • If \(F(x) = \bigtriangledown f(x)\), the VI is a convex optimization problem.
  • If \(F(x) = \bigtriangledown f(x)\) and \(K = \{x \, | \, Ax = b, Hx \leq h \}\), the VI is an NLP.
  • If \(F(x) = \bigtriangledown f(x) = p \) and \(K = \{x \, | \, Ax = b, Hx \leq h \}\), the VI is an LP.
  • If the feasible region is a box \(B = \{x \in \mathbb{R}^n | \, l_i \leq x_i \leq u_i, \, \textrm{for} \, i = 1, \dots , n \}\), with \( l_i \leq u_i\), \(\ l_i \in \mathbb{R} \cup \{- \infty \} \) and \(u_i \in \mathbb{R} \cup \{\infty\} \), the VI is an MCP, where \( x^* \in B\) is a solution of the respective MCP if for each \(i = 1, \dots , n\) one of the following conditions holds:

\begin{equation} \begin{array}{lll} F_i(x^*) = 0 & \textrm{and} & l_i \leq x^{*}_i \leq u_i, \\ F_i(x^*) > 0 & \textrm{and} & x^{*}_i = l_i, \\ F_i(x^*) < 0 & \textrm{and} & x^{*}_i = u_i. \\ \end{array} \end{equation}

Note that the set \(K\) is frequently defined in the following way:

\begin{equation} K = \{x \, | \, x \geq 0, \, h(x) \geq 0\}. \tag {8} \end{equation}

Further, note that the \(VI(F,K)\) represents a wider range of problems than classical optimization whenever \(F(x) \neq \bigtriangledown f(x)\) for some objective function \(f\) (or equivalently, the Jacobian of \(F\) is not symmetric). For example, problems that can be cast as VI include (generalized) Nash games and Nash equilibrium problems, systems of equations, complementarity problems, and fixed-point problems.

Variational Inequalities with EMP: A Simple Example

Consider the following simple three dimensional linear example (adapted from Yashtini & Malek (2007) [204]. Let

\begin{equation} F(x) = \begin{bmatrix} 22x_1 - 2x_2 + 6x_3 - 4\\ 2x_1 + 2x_2 \\ 6x_1 + 2x_3 \end{bmatrix}, \, K=\{ x \in \mathbb{R^3} \, | \, x_1 - x_2 \geq 1,\, -3x_1 - x_3 \geq -4, \, 2x_1 + 2x_2 + x_3 = 0, \, l \leq x \leq u \}, \tag {9} \end{equation}

where \(l=(-6,-6,-6)^T\), \(u=(6,6,6)^T\). N.B.: \(F\) is not the gradient of any function \(\mathbb{R}^3 \rightarrow \mathbb{R}\). This \(VI(F,K)\) has a unique solution: \(x=(2/3, -1/3, -2/3)\). The problem can be implemented in GAMS with EMP as follows:

Set      i /1*3/;
Variable x(i);

x.lo(i) = -6;
x.up(i) =  6;

Equations F(i), h1, h2, h3;

F(i)..   (22*x('1') - 2*x('2') + 6*x('3') - 4)$sameas(i,'1')
         + (2*x('1') + 2*x('2'))$sameas(i,'2')
         + (6*x('1') + 3*x('3'))$sameas(i,'3')
         =n= 0;

h1..     x('1') -x('2') =g= 1;

h2..     -3*x('1') - x('3') =g= -4;

h3..     2*x('1') + 2*x('2') + x('3') =e= 0;

Model linVI / F, h1, h2, h3 /;

File annotations /'%emp.info%'/;
put annotations;
putclose 'vi F x h1 h2 h3';

solve linVI using EMP;

Observe that the function \(F\) and the constraints \(h\) are formulated using standard GAMS syntax. \(F\) is implemented as an equation of type =n=, which does not imply or enforce any relationship between the left-hand side and the right-hand side. Instead, this relationship is implied by the position of the matching variables (given in the EMP info file) relative to their bounds. The annotations in the EMP info file define the structure of the VI: what functions are matched to what variables, and what constraints serve to define the set \(K\). The EMP keyword vi indicates that the model is a VI, that the VI function F is matched to the variable x, and that the constraints h1 h2 h3 define the set \(K\).

Alternatively, the EMP annotations could be written as follows:

putclose 'vi F x';

Here the equations after the equation-variable pair are omitted. This is acceptable, since by default any equations that are part of the model but are not matched with a variable are automatically used to define the set \(K\).

Since VI problems have no objective, the short form of the solve statement is used.

The solver JAMS will reformulate the VI as an MCP and pass this on to an MCP subsolver. The EMP Summary produced by JAMS will contain the following line:

--- EMP Summary
    ...
    VI Functions        = 3
    ...

This output reflects the fact that there were three VI functions in the model above, one for each member of the set i.

Note that there are several VI models in the GAMS EMP Library. For example, the models [SIMPLEVI] and [VI_MCP] demonstrate how some models can be specified using either MCP or VI syntax. A simple nonlinear VI is given in model [SIMPLEVI2]. As the transportation model is so well known, model [TRANSVI] demonstrates how it can be cast as a VI.

EMP Syntax for Variational Inequalities

The general syntax of the EMP annotations used to specify variational inequalities is as follows:

VI [{var|*}] { [-] equ var} [{[-] equ}]

The EMP keyword VI indicates that this is a variational inequality specification. The core of the VI specification is the (list of) equation-variable pair(s): the other parts are optional. A pair matches the equation equ with the variable var. This indicates that equ defines part of the VI function \(F\), and that these rows of \(F\) are perpendicular to columns taken from var. Multiple equation-variable pairs are allowed. The optional variables before the pairs are called preceding variables. These are variables that appear (and are often defined by) the constraints of the model, but they are not matched explicitly via the VI function \(F\). Instead, they are automatically matched with the zero function. See model [ZEROFUNC] for an example and a more detailed discussion. The optional equations after the equation-variable pairs are called trailing equations. They define the set \(K\) and may be omitted from the VI specification. By default, any equations that are included in the model but are not matched with a variable are automatically used to define the set \(K\). Even though both preceding variables and trailing equations may be omitted from the VI specification, we recommend to explicitly list them, since this clarifies intentions and eliminates ambiguity.

The "-" sign in the syntax above is used to flip (i.e. to reorient or negate) the marked equation, e.g. so that x**1.5 =L= y becomes y =G= x**1.5. Flipped equations in EMP behave in the same way as flipped equations in MCP.

Note
More than one VI specification may appear in a model. Often, it makes no difference whether multiple equ-var pairs are part of the same or separate VI specifications, but this is not the case in general. For an example, see model [SIMPLEVI4].