Embedded complementarity systems of the following form arise frequently in applications:

\begin{equation} \tag {12} \begin{array}{ll} \textrm{Min}_{x} & f(x,y) \\ \textrm{s.t.} & g(x,y) \leq 0 \quad (\perp \, \lambda \geq 0) \\ \end{array} \end{equation}

\begin{equation} \! \! H(x,y, \lambda) = 0 \quad \qquad (\perp \, y \; \textrm{free})\\ \end{equation}

Note that the optimization problem is over the variable \(x\) and it is parametrized by the variable \(y\). The choice of \(y\) is determined by the complementarity relationships represented here by \(H\).

From an EMP perspective, there are two ways to annotate a GAMS model to specify the model above: we will describe both below. These approaches provide equivalent additional information that prompts the EMP tool to automatically create the following MCP:

\begin{equation} \tag {13} \begin{array}{lll} 0 = \bigtriangledown_{x} L(x,y,\lambda) & \perp & x \, \textrm{free}\\ 0 \leq -\bigtriangledown_{\lambda} L(x,y,\lambda) & \perp & \lambda \geq 0 \\ 0 = H(x,y,\lambda) & \perp & y \, \textrm{free},\\ \end{array} \end{equation}

where the Lagrangian is defined as

\begin{equation} L(x,y,\lambda) = f(x,y) + \lambda^T \, g(x,y). \end{equation}

The first approach uses the EMP keywords dualequ and dualvar, as contained in the model [FERRIS43].

variables         obj, x, y;
positive variable lambda;

equations defobj, g, H;

* We omit the equation definitions here.

model ecs /defobj, g, H/;

file empinfo / '%emp.info%' /; putclose empinfo
'dualequ H y' /
'dualvar lambda g' / ;

solve ecs using EMP minimizing obj;

The external constraint \(H\) is expressed as a standard GAMS equation. The long form of the solve statement is used here, which implies the existence of a single optimizing agent that by default owns all equations and variables. The first EMP keyword dualequ indicates that the equation H and the variable y do not belong to the optimizing agent: instead, y is treated as an exogenous variable by this agent, and this agent is assumed to know nothing about the functional form of H, so that H will not appear in any first-order conditions. Instead, a complementarity relationship between the function defined by H and the variable y is required to exist at optimality. The EMP keyword dualvar indicates that the variable lambda is the dual of the equation g. As a result lambda will be treated exogenously wherever it appears. Given the EMP annotations for this model, JAMS will automatically reformulate the problem as the MCP in (12) and pass this model to an MCP subsolver.

The EMP Summary produced by JAMS contains the following lines:

--- EMP Summary
    Dual Variable Maps  = 1
    Dual Equation Maps  = 1

The second modeling approach recasts the problem above as an equilibrium problem with two agents: the first agent solves a minimization problem and the second agent solves a VI. The algebra in the model remains the same: only the EMP annotations and the solve statement change.

putclose empinfo
'equilibrium' /
' min obj x g defobj' /
' vi H y' /
' dualvar lambda g' /

solve ecs using EMP;

The EMP keyword equilibrium indicates we have an equilibrium problem. The EMP keyword min indicates that the first agent solves a minimization problem with the objective variable obj, the decison variable x and the equations g and defobj. In contrast to the first approach, where the default (because of the long-form solve statement) is one optimizing agent owning all equations, here we specify the first agent's minimization model explicitly and from the ground up. As a result it doesn't contain the equation H and we do not use the dualequ keyword to take H out. Instead, the EMP keyword vi specifies that the second agent solves a VI defined by H matched with the variable y. The dualvar keyword functions here as it did in the previous example.

The EMP Summary produced by JAMS contains the following lines:

--- EMP Summary
    ...
    Dual Variable Maps  = 1
    Dual Equation Maps  = 0
    VI Functions        = 1
    Equilibrium Agent   = 2
    ...

Other examples of embedded complementarity systems in the GAMS EMP Library include the simple equilibrium problem [SIMPEQUIL2], the equilibrium problem formulation of the well-known transportation model [TRANSECS], the PIES energy equilibrium problem [PIES], the pure exchange model [NEGISHI] and the spatial price equilibrium model [HARK-MONOP].

It's worthwhile highlighting the differences between the dualvar and dualequ keywords, as the two are easily and frequently confused. The dualvar keyword makes reference to a constraint owned by an optimizing agent. Derivatives of this constraint, multiplied by the variable referenced, appear in the first-order optimality conditions for this agent. The dualvar keyword allows us to use this variable or multiplier explicitly (and in a sense exogenously) in the model algebra. In constrast, the dualequ keyword indicates that, contrary to what the default is, an equation is not owned by any optimizing agent, so no derivatives of this equation will appear in any FOC or in the reformulated model. The two are similar in that if a variable x appears with either dualvar or dualequ, no derivatives w.r.t. x will appear in the model reformulation.

Table 1: Differences between dualvar and dualequ