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
where
Observe that the VI generalizes many problem classes:
- If
and , the VI is a system of nonlinear equations. - If
, the VI is a convex optimization problem. - If
and , the VI is an NLP. - If
and , the VI is an LP. If the feasible region is a box
, with , and , the VI is an MCP, where is a solution of the respective MCP if for each one of the following conditions holds:
Note that the set
Further, note that the
Variational Inequalities with EMP: A Simple Example
Consider the following simple three dimensional linear example (adapted from Yashtini & Malek (2007) [204]. Let
where
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 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
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
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 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
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].