Description

This example is a gentle introduction to QVI.  It assumes you are
familiar with EMP in general and VI in particular.

Recall that the VI is to find x in K such that:
  <F(x), (y - x)>   >= 0   for all y in K      where
  K is a closed convex set, e.g. K = { y | g(y) <= 0 }

In this intro, we consider the special case where the (Q)VI arises as
the optimality conditions for a multi-agent model.  Clearly VI is more
general than this (just as MCP is more general than the KKT for NLP)
but it's useful to narrow our focus here.  Assuming that the feasible
set for each agent is independent of what other agents do or decide,
the feasible set K above is the product of the feasible sets for each
agent, and this product set is also fixed.  The functions F_i are the
first-order optimality conditions for the agent objective functions
wrt x_i.  We expect agent i's FOC to be affected by agent j's
decisions, but agent i's feasible set is independent of agent j.

Small Model of Type : QVI

Category : GAMS EMP library

Main file : simpleqvi2.gms

$Title Simple Quasi-Variational Inequality (SIMPLEQVI2,SEQ=102)

$ontext
This example is a gentle introduction to QVI.  It assumes you are
familiar with EMP in general and VI in particular.

Recall that the VI is to find x in K such that:
  <F(x), (y - x)>   >= 0   for all y in K      where
  K is a closed convex set, e.g. K = { y | g(y) <= 0 }

In this intro, we consider the special case where the (Q)VI arises as
the optimality conditions for a multi-agent model.  Clearly VI is more
general than this (just as MCP is more general than the KKT for NLP)
but it's useful to narrow our focus here.  Assuming that the feasible
set for each agent is independent of what other agents do or decide,
the feasible set K above is the product of the feasible sets for each
agent, and this product set is also fixed.  The functions F_i are the
first-order optimality conditions for the agent objective functions
wrt x_i.  We expect agent i's FOC to be affected by agent j's
decisions, but agent i's feasible set is independent of agent j.


The QVI generalizes this so that the feasible set K (or more
specifically, the feasible set K_i in agent i's model) can depend on
the values of the variables owned by other agents, but in a way where
agent i views these values as fixed.  This is a common theme in
multi-agent modeling: from an agent perspective, variables we don't
control are not fixed, but we don't control them so we don't take
derivatives wrt these variables when writing down "our" optimality
conditions.  The feasible set becomes a product of the sets K_i, where
each K_i is defined by the values of the other agent's variables. 
The feasible set K in VI becomes the set K(x) in QVI:

  K(x) = { y | g(y,x) <= 0 }

The set-valued mapping K() makes use of the function g(y,x) that
essentially uses two copies of the same variable y == x, where y (aka
the variable of interest) behaves in the more usual sense of a
variable and x (aka the parameter variable) is treated as fixed where
it appears.  So we move to solving a QVI over y.x (i.e. y with its
shadow copy or parameter variable x) defined as:

  find y in K(x) such that:
    <F(y), (z - y)>   >= 0   for all z in K(x)      where
    K(x) = { y | g(y,x) <= 0 }

This QVI example is taken from the paper:

 Jiri V. Outrata and Jochem Zowe: A Newton method for a class of
 quasi-variational inequalities,
 Computational Optimization and Applications, 4, 5-21 (1995)

A generalized Nash equilibrium problem for which this QVI represents
the optimality conditions is in this library as SIMPEQUIL3.103.

Contributor: Youngdae Kim & Steve Dirkse, Apr 2018
$offtext

$if not set CLEANUP $set CLEANUP YES
$if not set TESTTOL $set TESTTOL 1e-6
scalars tol / %TESTTOL% /;

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'
  ;
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 opt  / 'jams.opt' /;
file info / '%emp.info%' /;


* ------------------------ test QVI ------------------------

putclose info
  '* to define complementary pairs F.y and a feasible set K defined by x' /
  '* the syntax for QVI is: QVI  { F y x-the-shadow-of-y }  {F2 y2} { g }' /
  'qvi  F y x  g'
  ;
putclose opt
  'Dict        qviDict.txt' /
  'FileName    qviScalar.gms' /
  ;
y.up(j) = 11;
x.up(j) = 11;

m.optfile = 1;
solve m using emp;

abort$[m.solvestat <> %solvestat.NormalCompletion%]
     'wrong m.solvestat', m.solvestat;
abort$[m.modelstat <> %modelstat.Optimal%]
     'wrong m.modelstat', m.modelstat;
abort$[abs(y.l('1') - 10) > tol] 'at solution, expected y(1)==10', y.l;
abort$[abs(y.l('2') -  5) > tol] 'at solution, expected y(2)==5', y.l;

$set KILL_LIST "jams.opt qviDict.txt qviScalar.gms qviScalar.lst qviScalarpf.pf"

$ifthen %CLEANUP% == YES
execute 'rm -f %KILL_LIST%';

$else
file log /''/;
putclose log
  ' ' /
  'Several intermediate files created by this run remain for you to browse:' /
  '   %KILL_LIST%' /
  'If you want them deleted, do not run model with --CLEANUP=NO' /
  ' ' /
  ;
$endif