Quasi-variational inequalities are a generalization of the variational inequality model: in a VI, the feasible set is fixed, while the QVI allows the feasible set to vary with or be a function of the variables in the model. To avoid repetition, we assume you are already familiar with the theory and notation for VI models. In this section, we present a mathematical formulation of QVI, give an example of how QVI can be modeled with GAMS EMP, and introduce the EMP annotations specific to QVI.

Quasi-Variational Inequalities: Mathematical Formulation

For a given continuous function \(F: \mathbb{R}^n \rightarrow \mathbb{R}^n\) and a point-to-set mapping \(K(y): \mathbb{R}^n \rightarrow \mathbb{R}^n\), the quasi-variational inequality problem \(QVI(F,K)\) is to find a point \(y^* \in K\) such that:

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

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

If the point-to-set mapping \(K(y): \mathbb{R}^n \rightarrow \mathbb{R}^n\) is constant, then the QVI above reduces to a VI. In order to define \(K(x)\) as a function of \(x\) it is convenient to introduce a shadow copy \(x\) of the variable \(y\). It should be understood that we have only one variable that appears in two forms: the variable of interest \(y\) and the parameter variable \(x\). Where \(y\) appears, we have a variable in the usual sense, and we take derivatives wrt this variable when deriving optimality conditions. Where \(x\) appears, we have a constant variable, i.e. we assume it is fixed when deriving optimality conditions. We can now use a function \(g(y,x)\) to define \(K(\cdot)\) and express QVI as: find a point \(y^* \in K\) (with its associated parameter variable \(x^*\)) such that:

\begin{equation} \langle F(y^*), (y-y^*) \rangle \geq 0, \quad \forall y \textrm{ s.t. } g(y,x) <= 0. \end{equation}

Quasi-Variational Inequalities with EMP: A Simple Example

Consider the following simple two dimensional linear example. Let \(y\) be the variable of interest with its parameter variable \(x\) and let

\begin{equation} F(y) = \begin{bmatrix} 2y_1 + \frac{8}{3}y_2 - \frac{100}{3} \\ 1.25y_1 + 2y_2 - 22.5 \end{bmatrix}, \, K(x) =\{ y \in \mathbb{R^2} \, | \, y_1 + x_2 \leq 15,\, x_1 + y_2 \leq 20, \, 0 \leq y,x \leq 11 \}. \end{equation}

This \(QVI(F,K)\) has a solution \(y=(10, 5)\). The problem can be implemented in GAMS with EMP as follows:

set i / 1*2 /;
alias(i,j);

table A(i,j)
      1       2
1     2     [8/3]
2   [5/4]     2   ;

parameters
  b(i) / 1 [100/3],  2 22.5 /
  Cy(i,j) / 1.1 1,  2.2 1 /
  Cx(i,j) / 1.2 1,  2.1 1 /
  rhs(i) / 1 15, 2 20 /
  ;
positive variables
  y(j)  'variable of interest, aka decision variable'
  x(j)  'parameter variable shadowing y'
  ;
y.up(j) = 11;   x.up(j) = 11;
equations
  F(i)   'FOC for agent optimization models'
  g(i)   'define feasible set K(x) for QVI'
  ;
F(i)..  sum{j, A(i,j)*y(j)} - b(i) =N= 0;

g(i)..  sum{j, Cy(i,j)*y(j)} + sum{j, Cx(i,j)*x(j)} =L= rhs(i);

model m / F, g /;
file annotations / '%emp.info%' /;
putclose annotations  'qvi  F y x  g'  ;
solve m using emp;

Observe that the function \(F\) and the constraints \(g\) 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 QVI: what functions are matched to what variables, and what constraints serve to define the mapping \(K(x)\). The EMP keyword qvi indicates that the model is a QVI, that the QVI function F is matched to the variable-of-interest y with its parameter variable x, and that the constraints g define the mapping \(K(x)\).

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

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

--- EMP Summary
    ...
    VI Functions        = 2
    QVI Parameters      = 2
    ...

This output reflects the fact that there were two VI functions in the model above, one for each member of the set i, and that each of the variables matched to these functions was shadowed by a parameter variable.

Note that there are two QVI models in the GAMS EMP Library, the models [SIMPLEQVI1] and [SIMPLEQVI2] (an expanded version of the example shown above).

EMP Syntax for Quasi-Variational Inequalities

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

QVI {0 var [ parameterVar] | [-] equ var [ parameterVar] } { [-] equ}

The EMP keyword QVI indicates that this is a quasi-variational inequality specification. All variables and equations included in a QVI must be listed explicitly. First we have the VI functions, their matching variables, and (optionally) the parameter variables shadowing these variables. Note that in a QVI there are no preceding variables as we have in a VI spec:: instead, the implied match to the zero function is indicated by the digit 0 appearing where an equation symbol would otherwise appear. After the function/variable pairs have been listed, the trailing equations (i.e. the equations/constraints defining the mapping \(K(\cdot)\)) appear.