A smoothing method for a class of generalized Nash equilibrium problems

Abstract

The generalized Nash equilibrium problem is an extension of the standard Nash equilibrium problem where both the utility function and the strategy space of each player depend on the strategies chosen by all other players. Recently, the generalized Nash equilibrium problem has emerged as an effective and powerful tool for modeling a wide class of problems arising in many fields and yet solution algorithms are extremely scarce. In this paper, using a regularized Nikaido-Isoda function, we reformulate the generalized Nash equilibrium problem as a mathematical program with complementarity constraints (MPCC). We then propose a suitable method for this MPCC and under some conditions, we establish the convergence of the proposed method by showing that any accumulation point of the generated sequence is a M-stationary point of the MPCC. Numerical results on some generalized Nash equilibrium problems are reported to illustrate the behavior of our approach.

1 Introduction

This paper considers the generalized Nash equilibrium problem with jointly convex constraints (GNEP). To be more specific, let us now give formal definitions of the standard Nash equilibrium problem (NEP) and the GNEP. We assume there are N players, each player $\nu\in\{1,\ldots,N\}$ controls the variables $x^{\nu}\in\Re^{n_{\nu}}$ and $x=(x^{1},\ldots,x^{N})^{T}\in \Re^{n}$ with $n=n_{1}+\cdots+n_{N}$ denotes the vector comprised of all these decision variables. To emphasize the νth player’s variables within the vector x, we sometimes write $x=(x^{\nu},x^{-\nu})^{T}$, where $x^{-\nu}$ subsumes all the other players’ variables. We will also write $n_{-\nu}=n-n_{\nu}$. Moreover, for both NEPs and GNEPs, let $\theta ^{\nu}:\Re^{n}\rightarrow\Re$ be the νth player’s payoff (or loss or utility) function.

For a NEP, there is a separate strategy set $X^{\nu}\subseteq\Re^{n_{\nu}}$ for each player ν. Let

$$ X:=\prod_{\nu=1}^{N}X^{\nu} $$

(1.1)

be the Cartesian product of the strategy sets of all players, then a vector $x^{*}\in X$ is called a Nash equilibrium, or a solution of the NEP, if each block component $x^{*,\nu}$ is a solution of the optimization problem

$$\begin{aligned}& \min_{x^{\nu}} \theta^{\nu}\bigl(x^{\nu},x^{*,-{\nu}} \bigr) \\& \quad \mbox{s.t. } x^{\nu} \in X^{\nu} , \end{aligned}$$

i.e., $x^{*}$ is a Nash equilibrium if no player can improve his situation by unilaterally changing his strategy.

On the other hand, in a GNEP, there is a common strategy set $X\subseteq\Re^{n}$ for all players, and a vector $x^{*}=(x^{*,1},\ldots,x^{*,N})^{T}\in\Re^{n}$ is called a generalized Nash equilibrium or a solution of the GNEP if each block component $x^{*,\nu}$ is a solution of the optimization problem

$$\begin{aligned}& \min_{x^{\nu}} \theta^{\nu}\bigl(x^{\nu},x^{*,-\nu} \bigr) \\& \quad \mbox{s.t. } \bigl(x^{\nu},x^{*,-\nu}\bigr)\in X. \end{aligned}$$

If X has the Cartesian product structure as (1.1), then a GNEP reduces to a NEP. Throughout this paper, we assume that X can be represented as

$$ X=\bigl\{ x \in{\Re}^{n} \mid g(x)\leq0 \bigr\} $$

(1.2)

for some functions $g:\Re^{n} \rightarrow\Re^{m}$. Note that usually, a player ν might have some additional constraints of the form $h^{\nu}(x^{\nu})\leq0$ depending on his decision variables only. However, these additional constraints can be viewed as part of the joint constraints $g(x)\leq0$, with some of the component functions $g_{i}$ of g depending on the block component $x^{\nu}$ of x only. So, we include these latter constraints in the former ones.

The GNEP was formally introduced by Debreu [1] as early as 1952, but it is only from the mid-1990s that the GNEP attracted much attention because of its capability of modeling a number of interesting problems in economy, computer science, telecommunications and deregulated markets (for example, see [2–4]). Motivated by the fact that a NEP can be reformulated as a variational inequality problem (VI); see, for example, [5, 6], Harker [7] characterized the GNEP as a quasi-variational inequality (QVI). But unlike VI, there are few efficient methods for solving QVI, and therefore such a reformulation is not used widely in designing implementable algorithms. The idea of using an exact penalty approach to the GNEP was proposed by Facchinei and Pang [8] and Facchinei and Kanzow [9], but the disadvantage of this method is that a nondifferentiable NEP has to be solved to obtain a generalized Nash equilibrium.

Another approach for solving the GNEP is based on the Nikaido-Isoda function. Relaxation methods and proximal-like methods using the Nikaido-Isoda function are investigated in [10–12]. A regularized version of the Nikaido-Isoda function was first introduced in [13] for NEPs then further investigated by Heusinger and Kanzow [14], they reformulated the GNEP as a constrained optimization problem with continuously differentiable objective function.

Motivated by [14], in this paper, we further reformulate the GNEP as a MPCC. Moreover, we propose a smoothing method to this problem and give some suitable conditions for the convergence of the proposed method. The organization of the paper is as follows. In the next section, we recall some preliminaries and basic facts and definitions. In Section 3, we give details of our optimization reformulation of the GNEP and discuss the convergence properties of our method. Finally, in Section 4, we present some numerical results.

We use the following notations throughout the paper. For a differentiable function $g:\Re^{n}\rightarrow\Re^{m}$, the Jacobian of g at $x\in\Re^{n}$ is denoted by $\mathcal{J}g(x)$, and it is transposed by $\nabla g(x)$. Given a differentiable function $\Psi:\Re^{n} \rightarrow\Re$, the symbol $\nabla_{x^{\nu}} \Psi (x)$ denotes the partial gradient with respect to $x^{\nu}$-part only. For a function $f:\Re^{n}\times\Re^{n}\rightarrow \Re$, $f(x,\cdot):\Re^{n}\rightarrow\Re$ denotes the function with x being fixed. For vectors $x,y\in\Re^{n}$, $\langle x,y \rangle$ denotes the inner product defined by $\langle x,y \rangle:=x^{T}y$ and $x\perp y$ means $\langle x,y \rangle=0$. Finally, throughout the paper, $\|\cdot\|$ denotes the Euclidean vector norm.

2 Preliminaries

Throughout this paper, we make the following blanket assumptions.

Assumption 2.1

• (i) The utility functions $\theta^{\nu}$ are twice continuously differentiable and as a function of $x^{\nu}$ along, $\theta^{\nu}$ are convex.

• (ii) The function g is twice continuously differentiable, its components $g_{i}$ are convex (in x), and the corresponding strategy space X defined by (1.2) is nonempty.

Note that the convexity assumptions are absolutely standard setting under which the GNEP is usually investigated in the literature, and Assumption 2.1(ii) implies that the strategy set $X\subseteq\Re^{n}$ is nonempty, closed, and convex. An important tool for both NEPs and GNEPs is the Nikaido-Isoda function (NI function for short) $\Psi:\Re^{n} \times\Re^{n} \rightarrow\Re$,

$$\Psi(x,y):=\sum_{\nu=1}^{N}\bigl[ \theta^{\nu}\bigl(x^{\nu},x^{-\nu }\bigr)- \theta^{\nu}\bigl(y^{\nu},x^{-\nu}\bigr)\bigr]. $$

In particular, the NI function provides an important subset of all the solutions of a GNEP.

Definition 2.1

A vector $x^{*}\in X$ is called a normalized Nash equilibrium of the GNEP if

$$ \sup_{y\in X}\Psi\bigl(x^{*},y\bigr)=0. $$

(2.1)

However, the supremum in (2.1) may not be attained, or it may be attained at more than one point. In order to overcome these disadvantages, in [14] authors provided a regularized version of the NI function. Let $\alpha>0$ be a given parameter that is assumed to be fixed throughout this paper. The regularized NI function is given by

$$\Psi_{\alpha}(x,y) := \Psi(x,y)-\frac{\alpha}{2}\|x-y\|^{2}. $$

We now define the corresponding value function by

$$V_{\alpha}(x):= \max_{y\in X} \Psi_{\alpha}(x,y) = \Psi_{\alpha }\bigl(x,y_{\alpha}(x)\bigr), $$

where $y_{\alpha}(x)$ denotes the unique solution of the uniformly concave maximization problem

$$ \begin{aligned} &\max \Psi_{\alpha}(x,y) \\ &\quad \mbox{s.t. } y\in X. \end{aligned} $$

(2.2)

As noted in [14], the function $V_{\alpha}$ is continuously differentiable with gradient given by

$$\nabla V_{\alpha}(x)= \nabla _{x} \Psi_{\alpha}(x,y)|_{y=y_{\alpha}(x)}, $$

and $x^{*}$ is a normalized Nash equilibrium of the GNEP if and only if it solves the constrained optimization problem

$$ \begin{aligned} &\min V_{\alpha}(x) \\ &\quad \mbox{s.t. } x\in X \end{aligned} $$

(2.3)

with optimal function value $V_{\alpha}(x^{*})= 0$.

3 Problem reformulation and a smoothing method

We now use the regularized NI function in order to obtain a MPCC reformulation of the GNEP.

Based on (2.3), $x^{*}$ is a normalized Nash equilibrium of the GNEP if and only if $x^{*}$ solves the following optimization problem:

$$\begin{aligned}& \min \Psi_{\alpha}\bigl(x,y_{\alpha}(x)\bigr) \\& \quad \mbox{s.t. } y_{\alpha}(x)= \arg\max_{y\in X} \Psi_{\alpha}(x,y), \\& \hphantom{\quad \mbox{s.t. }} x\in X. \end{aligned}$$

(3.1)

We consider Problem (2.2). For every $x\in X$, let the linear independence constraint qualification (LICQ) hold at $y_{\alpha}(x)$, then by Assumption 2.1, $y_{\alpha}(x)$ is a solution of (2.2) if and only if $y_{\alpha}(x)$ satisfies

$$\begin{aligned}& \nabla_{y} \Psi_{\alpha}\bigl(x,y_{\alpha}(x)\bigr)- \nabla g\bigl(y_{\alpha }(x)\bigr)\lambda_{\alpha}(x) =0, \\& 0\leq\lambda_{\alpha}(x) \perp-g\bigl(y_{\alpha}(x)\bigr)\geq0, \end{aligned}$$

where $\lambda_{\alpha}(x)$ is a Lagrangian multiplier. Thus, Problem (3.1) is equivalent to

$$ \begin{aligned} &\min \Psi_{\alpha}(x,y) \\ &\quad \mbox{s.t. } \nabla_{y} \Psi_{\alpha}(x,y)- \nabla g(y) \lambda=0, \\ &\hphantom{\quad \mbox{s.t. }} g(x)\leq0, \\ &\hphantom{\quad \mbox{s.t. }} 0\leq\lambda\perp-g(y)\geq0. \end{aligned} $$

(3.2)

This problem is a MPCC.

Now, we can easily get the following result as regards the normalized Nash equilibrium of the GNEP and the solution of the MPCC.

Proposition 3.1

For every $x\in X$, let the LICQ hold at $y_{\alpha}(x)$, then $x^{*}$ is a normalized Nash equilibrium if and only if there exists a vector $(y^{*},\lambda^{*})$ such that $(x^{*},y^{*},\lambda^{*})$ is a solution of Problem (3.2).

Let $z=(x,y,\lambda)$, $f(z)=\Psi_{\alpha}(x,y)$, $h(z)=\nabla_{y} \Psi_{\alpha}(x,y)- \nabla g(y)\lambda$, $\bar{g}(z)=g(x)$, $G(z)=\lambda$, and $H(z)=-g(y)$, we rewrite (3.2) more compactly as

$$ \begin{aligned} &\min f(z) \\ &\quad \mbox{s.t. } h(z) =0, \\ &\hphantom{\quad \mbox{s.t. }} \bar{g}(z)\leq0, \\ &\hphantom{\quad \mbox{s.t. }} 0\leq G(z)\perp H(z)\geq0. \end{aligned} $$

(3.3)

Define the Lagrangian of (3.3) as

$$L\bigl(z,\mu, \eta, \xi^{G},\xi^{H}\bigr)= f(z)+ h(z)^{T}\mu+ \bar {g}(z)^{T} \eta- G(z)^{T} \xi^{G}- H(z)^{T}\xi^{H} $$

and the index sets of active constraints as

$$I_{\bar{g}}(z)=\bigl\{ i\mid \bar{g}_{i}(z)=0\bigr\} ,\qquad I_{G}(z)=\bigl\{ i\mid G_{i}(z)=0\bigr\} ,\qquad I_{H}(z)=\bigl\{ i\mid H_{i}(z)=0\bigr\} , $$

the MPCC-LICQ for (3.3) at a feasible point $\bar{z}$ says that the following vectors:

$$\begin{aligned}& \nabla h_{i}(\bar{z}),\quad i=1,\ldots,n,\qquad \nabla \bar{g}_{i}(\bar{z}),\quad i\in I_{\bar{g}}(\bar{z}), \\& \nabla G_{i}(\bar{z}),\quad i\in I_{G}(\bar{z}),\qquad \nabla H_{i}(\bar{z}), \quad i\in I_{H}(\bar{z}) \end{aligned}$$

are linearly independent.

We next consider two simple GNEPs which show that the MPCC-LICQ for (3.3) holds at a solution $z^{*}$.

Example 3.1

Consider the GNEP with $N=2$, $X=\{x\in\Re^{2}\mid x^{1}\geq1, x^{2}\geq1\}$, and payoff functions $\theta^{1}(x)=x^{1}x^{2}$ and $\theta^{2}(x)=x^{2}$. Now let us consider $y_{\alpha}(x)$, the unique solution of

$$\begin{aligned}& \max \biggl(x^{1}x^{2}-y^{1}x^{2}+x^{2}-y^{2}- \frac{\alpha}{2}\bigl(y^{1}-x^{1}\bigr)^{2}- \frac {\alpha}{2}\bigl(y^{2}-x^{2}\bigr)^{2}\biggr) \\& \quad \mbox{s.t. } y\in X. \end{aligned}$$

An elementary calculation shows that

$$\begin{aligned}& y^{1}_{\alpha}(x)=\max\biggl\{ 1,\biggl(x^{1}- \frac{x^{2}}{\alpha}\biggr)\biggr\} , \\& y^{2}_{\alpha}(x)=\max\biggl\{ 1,\biggl(x^{2}-\frac{1}{\alpha}\biggr)\biggr\} . \end{aligned}$$

Furthermore, we get

$$\begin{aligned}& \lambda^{1}_{\alpha}(x)=\max\bigl\{ 0,\bigl(x^{2}+ \alpha-\alpha x^{1}\bigr)\bigr\} , \\& \lambda ^{2}_{\alpha}(x)= \max\bigl\{ 0,\bigl(\alpha+1-\alpha x^{2}\bigr)\bigr\} . \end{aligned}$$

We see that $x^{*}=(1,1)$ is the normalized Nash equilibrium and $z^{*}=(1,1,1,1,1,1)$ is a solution of (3.3). It is easy to compute that

$$\begin{aligned}& \nabla h_{1}\bigl(z^{*}\bigr)=(\alpha,-1,-\alpha,0,1,0)^{T}, \\& \nabla h_{2}\bigl(z^{*}\bigr)=(0,\alpha,0,-\alpha,0,1)^{T}, \\& \nabla\bar{g}_{1}\bigl(z^{*}\bigr)=(-1,0,0,0,0,0)^{T}, \\& \nabla\bar {g}_{2}\bigl(z^{*}\bigr)=(0,-1,0,0,0,0)^{T}, \\& \nabla H_{1}\bigl(z^{*}\bigr)=(0,0,1,0,0,0)^{T}, \\& \nabla H_{2}\bigl(z^{*}\bigr)=(0,0,0,1,0,0)^{T}. \end{aligned}$$

Moreover, we can see $\nabla h_{i}(z^{*})$, $i=1,2$, $\nabla \bar{g}_{i}(z^{*})$, $i=1,2$, $\nabla H_{i}(z^{*})$, $i=1,2$, are linearly independent, hence the MPCC-LICQ holds at $z^{*}$.

Example 3.2

Consider the GNEP with two players:

$$ \begin{array}{c@{\qquad}c} \begin{array}{l} \min x^{1}x^{2} \\ \quad \mbox{s.t. } x^{1}\geq1, \\ \hphantom{\quad \mbox{s.t. }}x^{2}\geq1, \\ \hphantom{\quad \mbox{s.t. }} x^{1}+x^{2}\leq10, \end{array} & \begin{array}{l} \min -x^{1}x^{2} \\ \quad \mbox{s.t. } x^{1}\geq1, \\ \hphantom{\quad \mbox{s.t. }} x^{2}\geq1, \\ \hphantom{\quad \mbox{s.t. }} x^{1}+x^{2}\leq10. \end{array} \end{array} $$

The regularized NI function is

$$\Psi_{\alpha}(x,y)=-y^{1}x^{2}+y^{2}x^{1}- \frac{\alpha}{2}\bigl(x^{1}-y^{1}\bigr)^{2}- \frac {\alpha}{2}\bigl(x^{2}-y^{2}\bigr)^{2}, $$

and $X=\{x\mid 1-x^{1}\leq0, 1-x^{2}\leq0, x^{1}+x^{2}-10\leq0\}$. It can be seen that $x^{*}=(1,9)$ is the unique normalized Nash equilibrium and

$$z^{*}=\bigl(x^{1,*},x^{2,*},y_{\alpha}^{1,*},y_{\alpha}^{2,*}, \lambda_{\alpha}^{1,*},\lambda_{\alpha}^{2,*}, \lambda_{\alpha}^{3,*}\bigr)= (1,9,1,9,10,0,1) $$

is the solution of (3.3). Moreover, we have

$$\begin{aligned}& \nabla h_{1}\bigl(z^{*}\bigr)=(\alpha,-1,-\alpha,0,1,0,-1)^{T}, \\& \nabla h_{2}\bigl(z^{*}\bigr)=(1,\alpha,0,-\alpha,0,1,-1)^{T}, \\& \nabla\bar{g}_{1}\bigl(z^{*}\bigr)=(-1,0,0,0,0,0,0)^{T}, \\& \nabla\bar {g}_{3}\bigl(z^{*}\bigr)=(1,1,0,0,0,0,0)^{T}, \\& \nabla H_{1}\bigl(z^{*}\bigr)=(0,0,1,0,0,0,0)^{T}, \\& \nabla H_{3}\bigl(z^{*}\bigr)=(0,0,-1,-1,0,0,0)^{T}, \\& \nabla G_{2}\bigl(z^{*}\bigr)=(0,0,0,0,0,1,0)^{T}. \end{aligned}$$

Obviously, $\nabla h_{i}(z^{*})$, $i=1,2$, $\nabla\bar{g}_{i}(z^{*})$, $i=1,3$, $\nabla H_{i}(z^{*})$, $i=1,3$, $\nabla G_{i}(z^{*})$, $i=2$, are linearly independent, hence the MPCC-LICQ for (3.3) holds at $z^{*}$.

In the study of MPCCs, there are several kinds of stationarity defined for Problem (3.3).

Definition 3.1

• (1) A feasible point $\bar{z}$ of (3.3) is called a critical point if there exist multipliers $\bar{\mu}$, $\bar{\eta}$, $\bar{\xi}^{G}$, and $\bar{\xi}^{H}$ such that

  $$ \begin{aligned} &\nabla_{z}L\bigl(\bar{z}, \bar{\mu},\bar{\eta},\bar {\xi}^{G},\bar{\xi}^{H}\bigr)=0, \\ &\bar{\eta}\geq0,\qquad \bar{\eta}^{T}\bar{g}({\bar {z}})=0, \\ &\bar{\xi}_{i}^{G}=0, \quad \mbox{if }i\notin I_{G}(\bar{z}), \\ &\bar{\xi}_{i}^{H}=0,\quad \mbox{if }i\notin I_{H}(\bar{z}). \end{aligned} $$

  (3.4)

• (2) Clarke (C)-stationarity: $\bar{\eta}_{i}\geq0$ and $\bar{\xi}_{k}^{G}\bar{\xi}_{k}^{H}\geq0$ for all $k\in I_{G}(\bar{z})\cap I_{H}(\bar{z})$.

• (3) Mordukhovich (M)-stationarity: $\bar{\eta}_{i}\geq0$ and either $\bar{\xi}_{k}^{G}, \bar{\xi}_{k}^{H}>0$ or $\bar{\xi}_{k}^{G}\bar{\xi}_{k}^{H}= 0$ for all $k\in I_{G}(\bar{z})\cap I_{H}(\bar{z})$.

We now propose our smoothing method for (3.3). This method is similar to one given in [15] which, however, uses a different reformulation of the complementarity constraints. Let

$$\phi(a,b,\epsilon)= a+b-\sqrt{(a-b)^{2}+ \epsilon}. $$

and $\epsilon>0$ is the smoothing parameter. We have

$$\phi(a,b,\epsilon)=0\quad \Leftrightarrow\quad a> 0, b> 0,ab=\frac{\epsilon }{4} $$

and

$$\begin{aligned}& \frac{ \partial}{ \partial a}\phi(a,b,\epsilon) = 1-\frac{ a-b}{ \sqrt{(a-b)^{2}+\epsilon}}, \\& \frac{ \partial}{ \partial b}\phi(a,b,\epsilon) = 1-\frac{ b-a}{ \sqrt{(a-b)^{2}+\epsilon}}, \\& \frac{ \partial^{2}}{ \partial a^{2}}\phi(a,b,\epsilon) = \frac { -\epsilon}{ [(a-b)^{2}+\epsilon]^{\frac{3}{2}}}, \\& \frac{ \partial^{2}}{ \partial b^{2}}\phi(a,b,\epsilon) = \frac { -\epsilon}{ [(a-b)^{2}+\epsilon]^{\frac{3}{2}}}, \\& \frac{ \partial^{2}}{ \partial a\, \partial b}\phi(a,b,\epsilon) = \frac{ \epsilon}{ [(a-b)^{2}+\epsilon ]^{\frac{3}{2}}}. \end{aligned}$$

By the definition of the function ϕ and the calculation formulas for its first- and second-order partial derivatives, we can easily obtain the following properties of ϕ.

Lemma 3.1

Let $(a,b,\epsilon)$ satisfy $\phi(a,b,\epsilon)=0$ and $\epsilon >0$.

• (i) We have

  $$\begin{aligned} \begin{aligned} &\frac{ \partial}{ \partial a}\phi(a,b,0)= 0, \quad \textit{if } a>0=b, \\ &\frac{ \partial}{ \partial b}\phi(a,b,0)= 0, \quad \textit{if } a=0< b. \end{aligned} \end{aligned}$$

• (ii) Let $(a^{k},b^{k})\rightarrow(0,0)$ as $\epsilon ^{k}\rightarrow 0^{+}$ with $\phi(a^{k},b^{k},\epsilon^{k})=0$. If

  $$\lim_{k\rightarrow\infty}\frac{\frac{ \partial}{ \partial a}\phi(a^{k},b^{k},\epsilon ^{k})}{\frac{ \partial}{ \partial b}\phi (a^{k},b^{k},\epsilon^{k})}\rightarrow r>0, $$

  we have

  $$\bigl(V^{k}\bigr)H^{k}\bigl(V^{k} \bigr)^{T}\rightarrow-\infty, \quad \textit{as }k\rightarrow \infty, $$

  where $V^{k}=(\frac{ \partial\phi}{ \partial b}, -\frac{ \partial\phi}{ \partial a})$ and $H^{k}$ is the Hessian of ϕ with respect to a and b evaluated at $(a^{k},b^{k}, \epsilon^{k})$.

Now, we consider the following problem with $\epsilon>0$:

$$ \begin{aligned} &\min f(z) \\ &\quad \mbox{s.t. } h(z) =0, \\ &\hphantom{\quad \mbox{s.t. }} \bar{g}(z)\leq0, \\ &\hphantom{\quad \mbox{s.t. }} \Phi^{\epsilon} (z)=0, \end{aligned} $$

(3.5)

where $\Phi^{\epsilon} (z)= (\phi(G_{1}(z),H_{1}(z),\epsilon),\ldots,\phi (G_{m}(z),H_{m}(z),\epsilon))^{T}$. We recall that $z^{\epsilon}$ is stationary for (3.5) if it is feasible and there exist Lagrangian multiplier vectors $\mu^{\epsilon}\in\Re^{n}$, $\eta^{\epsilon}\in\Re^{m}$, and $\xi^{\epsilon}\in\Re^{m}$ satisfying

$$\begin{aligned}& \nabla_{z}L\bigl(z^{\epsilon},\mu^{\epsilon}, \eta^{\epsilon},\xi^{\epsilon}\bigr)=0, \\& h\bigl(z^{\epsilon}\bigr)=0, \\& \bar{g}\bigl(z^{\epsilon}\bigr)\leq0,\qquad \eta^{\epsilon}\geq0,\qquad \bar {g}\bigl(z^{\epsilon}\bigr)^{T}\eta^{\epsilon}=0, \\& \Phi^{\epsilon} \bigl(z^{\epsilon}\bigr)=0, \end{aligned}$$

where the Lagrangian function is

$$L(z,\mu,\eta,\xi)= f(z)+ h(z)^{T} \mu+\bar{g}(z)^{T} \eta+ \Phi^{\epsilon}(z)^{T}\xi. $$

A stationary point $z^{\epsilon}$ with Lagrangian multipliers $\mu ^{\epsilon}$, $\eta^{\epsilon}$, $\xi^{\epsilon}$ of (3.5) is said to satisfy a second-order necessary condition (SONC) if

$$d^{T}\nabla^{2}_{zz} L\bigl(z^{\epsilon}, \mu^{\epsilon},\eta^{\epsilon},\xi^{\epsilon}\bigr)d \geq0 $$

for any d in the critical cone,

$$C\bigl(z^{\epsilon}\bigr)=\left \{d \left\vert \begin{array}{l} \nabla h_{i}(z^{\epsilon})^{T}d=0, i=1,\ldots,n \\ \nabla\Phi_{i}^{\epsilon}(z^{\epsilon})^{T}d=0, i=1,\ldots,m \\ \nabla\bar{g}_{i}(z^{\epsilon})^{T}d=0, i: \bar {g}_{i}(z^{\epsilon})=0, \eta_{i}^{\epsilon}>0 \\ \nabla\bar{g}_{i}(z^{\epsilon})^{T}d\leq0, i: \bar {g}_{i}(z^{\epsilon})=0, \eta_{i}^{\epsilon}=0 \end{array} \right . \right \}. $$

We need a slightly weaker condition that we call the weak second-order necessary condition (WSONC), which requires the positive semidefiniteness of $\nabla^{2}_{zz} L(z^{\epsilon},\mu^{\epsilon},\eta^{\epsilon},\xi^{\epsilon})$ on the critical subspace

$$\operatorname{lin} C\bigl(z^{\epsilon}\bigr)=\left \{d \left\vert \begin{array}{l} \nabla h_{i}(z^{\epsilon})^{T}d=0, i=1,\ldots,n \\ \nabla\Phi_{i}^{\epsilon}(z^{\epsilon})^{T}d=0, i=1,\ldots,m \\ \nabla\bar{g}_{i}(z^{\epsilon})^{T}d=0, i\in I_{\bar{g}}(z^{\epsilon}) \end{array} \right . \right \}. $$

Now, we state a convergence result for the smoothing method (3.5).

Theorem 3.1

Let $\{z^{k},\mu^{k},\eta^{k},\xi^{k}\}$ be a Karush-Kuhn-Tucher (KKT) point of (3.5) for each $\epsilon=\epsilon^{k}$, where $\epsilon^{k}\rightarrow0^{+}$. Suppose that $\bar{z}$ is a limit point of $\{z^{k}\}$ and the MPCC-LICQ holds at $\bar{z}$ for (3.3). Then

• (i) $\bar{z}$ is a C-stationary point of (3.3);

• (ii) if WSONC holds for (3.5) at each $z^{k}$, then $\bar{z}$ is a M-stationary point of (3.3).

Proof

By taking a subsequence if necessary, we assume that $z^{k}\rightarrow \bar{z}$, and it is easy to see that $\bar{z}$ is feasible for (3.3). To simplify notation, in the following, we denote

$$\begin{aligned}& \frac{\partial\phi_{i}}{\partial a}=\frac{\partial}{\partial a}\phi \bigl(G_{i} \bigl(z^{k}\bigr),H_{i}\bigl(z^{k}\bigr), \epsilon^{k}\bigr),\qquad \frac{\partial\phi_{i}}{\partial b}=\frac{\partial}{\partial b}\phi \bigl(G_{i}\bigl(z^{k}\bigr),H_{i} \bigl(z^{k}\bigr),\epsilon^{k}\bigr), \\& \frac{\partial^{2} \phi_{i}}{\partial a^{2}}=\frac{\partial^{2}}{\partial a^{2}}\phi\bigl(G_{i} \bigl(z^{k}\bigr),H_{i}\bigl(z^{k}\bigr), \epsilon^{k}\bigr), \qquad \frac{\partial^{2} \phi _{i}}{\partial b^{2}}=\frac{\partial^{2}}{\partial b^{2}}\phi \bigl(G_{i}\bigl(z^{k}\bigr),H_{i} \bigl(z^{k}\bigr),\epsilon^{k}\bigr), \\& \frac{\partial^{2} \phi_{i}}{\partial a\, \partial b}=\frac{\partial ^{2}}{\partial a\, \partial b}\phi\bigl(G_{i} \bigl(z^{k}\bigr),H_{i}\bigl(z^{k}\bigr), \epsilon^{k}\bigr). \end{aligned}$$

First, we show that $\bar{z}$ is a critical point of (3.3). The gradient equation of the KKT system for (3.5) at $z^{k}$ is

$$\begin{aligned}& \nabla f\bigl(z^{k}\bigr)+\nabla h\bigl(z^{k} \bigr)\mu^{k}+\nabla \bar{g}\bigl(z^{k}\bigr) \eta^{k}+\sum_{i=1}^{m} \xi_{i}^{k}\frac {\partial \phi_{i}}{\partial a}\nabla G_{i} \bigl(z^{k}\bigr)+\sum_{i=1}^{m} \xi_{i}^{k}\frac{\partial \phi_{i}}{\partial b}\nabla H_{i} \bigl(z^{k}\bigr)=0, \\& \quad h\bigl(z^{k}\bigr)=0, \\& \quad 0\leq\eta^{k} \perp-\bar{g}\bigl(z^{k}\bigr)\geq0, \\& \quad \Phi^{\epsilon}\bigl(z^{k}\bigr)=0. \end{aligned}$$

(3.6)

Equation (3.6) can be equivalently expressed as

$$\begin{aligned}& \nabla f\bigl(z^{k}\bigr)+ \sum _{i=1}^{n} \mu_{i}^{k} \nabla h_{i}\bigl(z^{k}\bigr)+\sum_{i\in I_{\bar{g}}(z^{k})} \eta^{k}_{i} \nabla\bar{g}_{i} \bigl(z^{k}\bigr) + \sum_{i\in I_{G}(\bar{z})} \xi_{i}^{k}\frac{ \partial\phi_{i}}{\partial a}\nabla G_{i} \bigl(z^{k}\bigr) \\& \quad {}+ \sum_{i\notin I_{G}(\bar{z})}\xi_{i}^{k} \frac{\partial\phi_{i}}{ \partial a}\nabla G_{i}\bigl(z^{k}\bigr)+\sum _{i\in I_{H}(\bar{z})}\xi_{i}^{k} \frac{ \partial\phi_{i}}{ \partial b}\nabla H_{i}\bigl(z^{k}\bigr)+\sum _{i\notin I_{H}(\bar{z})}\xi_{i}^{k} \frac{\partial\phi_{i}}{ \partial b}\nabla H_{i}\bigl(z^{k}\bigr)=0. \end{aligned}$$

(3.7)

Let $r_{i}^{k}=\xi_{i}^{k}\frac{ \partial \phi_{i}}{ \partial a}$ and $v_{i}^{k}=\xi_{i}^{k}\frac{ \partial \phi_{i}}{ \partial b}$, we show that $\lim_{k\rightarrow\infty}r_{i}^{k}$ exists and $r_{i}^{k}\rightarrow0$ if $i\notin I_{G}(\bar{z})$. Let $i\notin I_{G}(\bar{z})$, then $i\in I_{H}(\bar{z})$ by the feasibility of $\bar{z}$. We assume that there exist a positive number $\bar{\alpha} >0$ and a subsequence (we denote the subsequence by the sequence itself for the sake of notational simplicity) such that $| r_{i}^{k}| \geq\bar{\alpha}$ for sufficiently large k. Since

$$\lim_{k\rightarrow\infty}\frac{\partial\phi}{\partial a}\bigl(G_{i} \bigl(z^{k}\bigr),H_{i}\bigl(z^{k}\bigr), \epsilon^{k}\bigr)=\frac{\partial \phi}{\partial a}\bigl(G_{i}( \bar{z}),H_{i}(\bar{z}),0 \bigr)=0, $$

then $\lim_{k\rightarrow\infty} | \xi_{i}^{k}| =+\infty$. Let $\beta^{k}:=\|(\mu^{k},\eta^{k},\xi^{k})\|$, then $\beta^{k} \rightarrow+\infty$. It is not difficult to obtain for sufficiently large k, $I_{\bar{g}}(z^{k}) \subseteq I_{\bar {g}}(\bar{z})$. Dividing (3.7) by $\beta^{k}$, and taking any limit point $(\tilde{\mu},\tilde{\eta},\tilde{r},\tilde{v})$ of $(\mu^{k},\eta^{k},r^{k},v^{k})/\beta^{k}$ yields $(\tilde{\mu},\tilde{\eta},\tilde{r},\tilde {v})\neq 0$ and

$$ \sum_{i=1}^{n}\tilde{ \mu}_{i}\nabla h_{i}(\bar{z})+\sum _{i\in I_{\bar{g}}(\bar{z})}\tilde{\eta}_{i}\nabla \bar{g}_{i}( \bar{z}) + \sum_{i\in I_{G}(\bar{z})}\tilde{r}_{i}\nabla G_{i}(\bar{z})+ \sum_{i\in I_{H}(\bar{z})} \tilde{v}_{i}\nabla H_{i}(\bar{z})=0. $$

(3.8)

Equation (3.8) contradicts the MPCC-LICQ at $\bar{z}$. Therefore, $\lim_{k\rightarrow\infty}r_{i}^{k}=0$, for $i\notin I_{G}(\bar{z})$. In the same way, we can also prove that $\lim_{k\rightarrow\infty}v_{i}^{k}=0$, for $i\notin I_{H}(\bar{z})$. Furthermore, $\{\mu_{i}^{k}\}_{i=1}^{n}$, $\{\eta_{i}^{k}\}_{i\in I_{\bar{g}}(\bar{z})}$, $\{r_{i}^{k}\}_{i\in I_{G}(\bar{z})}$, and $\{v_{i}^{k}\}_{i\in I_{H}(\bar{z})}$ are bounded. Otherwise, dividing (3.7) by $\beta^{k}$ and taking the limit will lead to a contradiction to the MPCC-LICQ at $\bar{z}$ as done above. Due to the MPCC-LICQ at $\bar{z}$, Let $(\bar{\mu},\bar{\eta},\bar{r},\bar{v})$ denote the unique limit of $(\mu^{k},\eta^{k},r^{k},v^{k})$, with $r^{k}=(r_{1}^{k},\ldots,r_{m}^{k})^{T}$ and $v^{k}=(v_{1}^{k},\ldots,v_{m}^{k})^{T}$, we can see, $(\bar{z},\bar{\mu},\bar{\eta},\bar {r},\bar{v})$ satisfies (3.4), so, $\bar{z}$ is a critical point of (3.3).

Note that, for any $i\in I_{G}(\bar{z})\cap I_{H}(\bar{z})$,

$$\bar{r}_{i}\bar{v}_{i}=\lim_{k\rightarrow\infty } \bigl(r_{i}^{k}v_{i}^{k}\bigr)= \lim _{k\rightarrow\infty}\biggl(\xi_{i}^{k} \frac{\partial \phi_{i}}{\partial a}\biggr) \biggl(\xi_{i}^{k} \frac{\partial\phi_{i}}{\partial b}\biggr)=\lim_{k\rightarrow\infty}\bigl(\xi_{i}^{k} \bigr)^{2}\frac{\partial \phi_{i}}{\partial a}\frac{\partial\phi_{i}}{\partial b}\geq0, $$

the C-stationarity of $\bar{z}$ follows.

For the M-stationarity of $\bar{z}$. If $\bar{z}$ is not a M-stationary point of (3.3) which means that there exists at least one index, denoted by $l\in I_{G}(\bar{z})\cap I_{H}(\bar{z})$ such that $\bar{r}_{l}>0$ and $\bar{v}_{l}>0$, so we have $\xi_{l}^{k}>0$ and away from zero for sufficiently large k. First, it is easy to see that

$$\lim_{k\rightarrow\infty} \frac{ \xi_{l}^{k}\frac{ \partial\phi_{l}}{\partial a}}{\xi_{l}^{k}\frac{ \partial\phi_{l}}{ \partial b}}=\lim_{k\rightarrow\infty} \frac{\frac{ \partial \phi_{l}}{ \partial a}}{\frac{ \partial \phi_{l}}{ \partial b}}=\frac{\bar{r}_{l}}{\bar{v}_{l}}>0. $$

Second, by the MPCC-LICQ at $\bar{z}$, we have

$$\left ( \begin{array}{@{}c@{}} \nabla h_{i}(\bar{z})^{T}, i=1,\ldots,n \\ \nabla\bar{g}_{i}(\bar{z})^{T}, i\in I_{\bar {g}}(\bar{z}) \\ \nabla G_{i}(\bar{z})^{T} , i\in I_{G}(\bar{z}) \\ \nabla H_{i}(\bar{z})^{T} , i\in I_{H}(\bar{z}) \end{array} \right ) $$

has full row rank. Then for sufficiently large k,

$$\left ( \begin{array}{@{}c@{}} \nabla h_{i}(z^{k})^{T} , i=1,\ldots,n \\ \nabla\bar{g}_{i}(z^{k})^{T} , i\in I_{\bar{g}}(\bar {z}) \\ \nabla G_{i}(z^{k})^{T} , i\in I_{G}(\bar{z})\backslash\{l\} \\ \nabla H_{i}(z^{k})^{T} , i\in I_{H}(\bar{z})\backslash\{l\} \\ \nabla G_{l}(z^{k})^{T} \\ \nabla H_{l}(z^{k})^{T} \end{array} \right ) $$

is full row rank also. Therefore there exists $d^{k}$ which is bounded and satisfies

$$\begin{aligned}& \nabla h_{i}\bigl(z^{k}\bigr)^{T}d^{k}=0, \quad i=1,\ldots,n, \\& \nabla\bar{g}_{i}\bigl(z^{k}\bigr)^{T}d^{k}=0, \quad i\in I_{\bar {g}}(\bar{z}), \\& \nabla G_{i}\bigl(z^{k}\bigr)^{T}d^{k}=0, \quad i\in I_{G}(\bar{z})\backslash\{ l\}, \\& \nabla H_{i}\bigl(z^{k}\bigr)^{T}d^{k}=0, \quad i\in I_{H}(\bar{z})\backslash\{ l\}, \\& \nabla G_{l}\bigl(z^{k}\bigr)^{T}d^{k}= \frac{ \partial\phi_{l}}{ \partial b}, \\& \nabla H_{l}\bigl(z^{k}\bigr)^{T}d^{k}=- \frac{ \partial\phi_{l}}{ \partial a}. \end{aligned}$$

It is easy to see that $d^{k}$ is in the critical subspace $\operatorname{lin} C(z^{k})$ of Problem (3.5) at $z^{k}$, and

$$\begin{aligned}& \bigl(d^{k}\bigr)^{T}\nabla_{zz}^{2}L \bigl(z^{k},\mu^{k},\eta^{k},\xi^{k} \bigr) \bigl(d^{k}\bigr) \\& \quad = \bigl(d^{k} \bigr)^{T}\Biggl\{ \nabla^{2}f\bigl(z^{k}\bigr)+ \sum_{i=1}^{n}\mu_{i}^{k} \nabla ^{2}h_{i}\bigl(z^{k}\bigr) + \sum _{i=1}^{m}\eta_{i}^{k} \nabla^{2}\bar {g}_{i}\bigl(z^{k}\bigr) \Biggr\} d^{k} \\& \qquad {} +\bigl(d^{k}\bigr)^{T}\Biggl( \sum _{i=1}^{m}\xi_{i}^{k} \frac{ \partial\phi_{i}}{ \partial a} \nabla^{2}G_{i}\bigl(z^{k} \bigr)\Biggr)d^{k} +\bigl(d^{k}\bigr)^{T}\Biggl( \sum _{i=1}^{m}\xi_{i}^{k} \frac{ \partial\phi_{i}}{ \partial b} \nabla^{2}H_{i}\bigl(z^{k} \bigr)\Biggr)d^{k} \\& \qquad {} +\bigl(d^{k}\bigr)^{T}\Biggl( \sum _{i=1}^{m}\xi_{i}^{k}\nabla G_{i}\bigl(z^{k}\bigr)\frac{ \partial^{2} \phi_{i}}{ \partial a \, \partial a}\nabla G_{i}\bigl(z^{k}\bigr)^{T} \Biggr)d^{k} \\& \qquad {} +2\bigl(d^{k}\bigr)^{T}\Biggl( \sum _{i=1}^{m}\xi_{i}^{k}\nabla G_{i}\bigl(z^{k}\bigr)\frac{ \partial^{2} \phi_{i}}{ \partial a\, \partial b}\nabla H_{i}\bigl(z^{k}\bigr)^{T}\Biggr)d^{k} \\& \qquad {} +\bigl(d^{k}\bigr)^{T}\Biggl( \sum _{i=1}^{m}\xi_{i}^{k}\nabla H_{i}\bigl(z^{k}\bigr)\frac{ \partial^{2} \phi_{i}}{ \partial b\, \partial b}\nabla H_{i}\bigl(z^{k}\bigr)^{T} \Biggr)d^{k}. \end{aligned}$$

We know $(d^{k})^{T}\{\nabla^{2}f(z^{k})+ \sum_{i=1}^{n}\mu_{i}^{k}\nabla^{2}h_{i}(z^{k}) + \sum_{i=1}^{m}\eta_{i}^{k}\nabla^{2}\bar{g}_{i}(z^{k}) \}d^{k}$, $(d^{k})^{T}( \sum_{i=1}^{m}\xi_{i}^{k}\frac{ \partial\phi _{i}}{ \partial a}\times \nabla^{2}G_{i}(z^{k}))d^{k}$ and $(d^{k})^{T}( \sum_{i=1}^{m}\xi_{i}^{k}\frac{ \partial\phi_{i}}{ \partial b} \nabla^{2}H_{i}(z^{k}))d^{k}$ are bounded, and

$$\begin{aligned}& \bigl(d^{k}\bigr)^{T}\Biggl( \sum _{i=1}^{m}\xi_{i}^{k}\nabla G_{i}\bigl(z^{k}\bigr)\frac{ \partial^{2} \phi_{i}}{ \partial a \, \partial a}\nabla G_{i}\bigl(z^{k}\bigr)^{T} \Biggr)d^{k} \\& \qquad {}+2\bigl(d^{k}\bigr)^{T}\Biggl( \sum _{i=1}^{m}\xi_{i}^{k}\nabla G_{i}\bigl(z^{k}\bigr)\frac{ \partial^{2} \phi_{i}}{ \partial a\, \partial b}\nabla H_{i}\bigl(z^{k}\bigr)^{T}\Biggr)d^{k} \\& \qquad {}+\bigl(d^{k}\bigr)^{T}\Biggl( \sum _{i=1}^{m}\xi_{i}^{k}\nabla H_{i}\bigl(z^{k}\bigr)\frac{ \partial^{2} \phi_{i}}{ \partial b \, \partial b}\nabla H_{i}\bigl(z^{k}\bigr)^{T} \Biggr)d^{k} \\& \quad = \bigl(d^{k}\bigr)^{T}\biggl(\xi_{l}^{k} \nabla G_{l}\bigl(z^{k}\bigr)\frac{ \partial ^{2} \phi_{l}}{ \partial a\, \partial a}\nabla G_{l}\bigl(z^{k}\bigr)^{T} \biggr)d^{k} \\& \qquad {}+2\bigl(d^{k}\bigr)^{T}\biggl( \xi_{l}^{k}\nabla G_{l}\bigl(z^{k} \bigr)\frac{ \partial^{2} \phi _{l}}{ \partial a\, \partial b}\nabla H_{l}\bigl(z^{k} \bigr)^{T}\biggr)d^{k} \\& \qquad {}+\bigl(d^{k} \bigr)^{T}\biggl(\xi_{l}^{k}\nabla H_{l}\bigl(z^{k}\bigr)\frac{ \partial^{2} \phi _{l}}{ \partial b\, \partial b}\nabla H_{l}\bigl(z^{k}\bigr)^{T} \biggr)d^{k}. \end{aligned}$$

(3.9)

For sufficiently large k, we have $\xi_{l}^{k}>0$ and (3.9) is equal to

$$\xi_{l}^{k}\frac{\partial^{2}\phi_{l}}{\partial a\, \partial a}\biggl(\frac{\partial\phi_{l}}{\partial b} \biggr)^{2}-2\xi_{l}^{k}\frac{\partial^{2}\phi_{l}}{\partial a\, \partial b} \frac{\partial\phi_{l}}{\partial a} \frac{\partial\phi_{l}}{\partial b} +\xi_{l}^{k} \frac{\partial^{2}\phi_{l}}{\partial b \, \partial b}\biggl(\frac{\partial\phi_{l}}{\partial a}\biggr)^{2}= \xi_{l}^{k} \bigl(V^{k}\bigr)H^{k} \bigl(V^{k}\bigr)^{T}, $$

which tends to −∞ by Lemma 3.1. This contradicts that $z^{k}$ satisfies WSONC. The M-stationarity of $\bar{z}$ follows. □

4 Numerical experiments

We have tested the method on various examples of the GNEP. We applied MATLAB 7.0 built-in solver function fmincon to solve the nonlinear programs for positive ϵ-values. The computational results are summarized in Tables 1, 2, 4-6, 8, which indicate that the proposed method produces good approximate solutions.

Example 4.1

This problem is taken from [16]. There are two players, each player ν has a one-dimensional decision variable $x^{\nu} \in \Re$. The optimization problems of the two players are given by

$$\begin{aligned}& \min_{x^{1}}\bigl(x^{1}-1\bigr)^{2} \quad \mbox{s.t. } x^{1}+x^{2}\leq1, \\& \min_{x^{2}}\biggl(x^{2}-\frac{1}{2} \biggr)^{2} \quad \mbox{s.t. } x^{1}+x^{2}\leq 1. \end{aligned}$$

This problem has infinitely many solutions $\{(\alpha,1-\alpha)\mid \alpha\in[0.5,1]\}$, but has only one normalized Nash equilibrium at $\bar{x}=( \frac{3}{4}, \frac{1}{4})^{T}$. Table 1 is for the corresponding numerical results.

Table 1 Numerical results for Example 4.1

Example 4.2

This is a duopoly model with two players taken from [10]. Each player ν controls one variable $x^{\nu} \in\Re$. The payoff functions are given by

$$\theta^{\nu}(x)=x^{\nu}\bigl(\bar{\rho} \bigl(x^{1}+x^{2} \bigr)+\lambda-d\bigr)\quad \mbox{for }\nu=1,2, $$

and the constraints are given by

$$-10\leq x^{\nu} \leq10\quad \mbox{for }\nu=1,2, $$

where $d=20$, $\lambda=4$, $\bar{\rho} =1$.

Table 2 Numerical results for Example 4.2

Example 4.3

This example is a river basin pollution game also taken from [10]. There are three players, each player controls a single variable $x^{\nu}\in{\Re}$. The objective functions are given by

$$\theta^{\nu}(x)=x^{\nu}\bigl(c_{1\nu}+c_{2\nu}x^{\nu }-d_{1}+d_{2} \bigl(x^{1}+x^{2}+x^{3}\bigr)\bigr) $$

for $\nu=1,2,3$, and the constraints are

$$ \mu_{11}e_{1}x^{1}+\mu_{21}e_{2}x^{2}+ \mu_{31}e_{3}x^{3}\leq K1, \qquad \mu_{12}e_{1}x^{1}+\mu_{22}e_{2}x^{2}+ \mu_{32}e_{3}x^{3}\leq K2. $$

The economic constants $d_{1}$ and $d_{2}$ determine the inverse demand law and set to 3.0 and 0.01, respectively. Values for constants $c_{1,\nu}$, $c_{2,\nu}$, $e_{\nu}$, $\mu_{\nu,1}$, and $\mu_{\nu,2}$ are given in Table 3, and $K_{1}=K_{2}=100$.

Table 3 Values of constants for Example  4.3

Table 4 Numerical results for Example 4.3

Example 4.4

This test problem is an Internet switching model introduced by Kesselman et al. [17]. There are N players, the cost function of each player is given by

$$\theta^{\nu}(x)=\frac{x^{\nu}}{B}-\frac{x^{\nu}}{ \sum_{\nu =1}^{N}x^{\nu}}, $$

with constraints $x^{\nu}\geq0.01$, $\nu=1,\ldots,N$, and $\sum_{\nu=1}^{N}x^{\nu}\leq B$. We set $N=10$, $B=1$. The exact solution of this problem is $x^{*}=(0.09,0.09,\ldots,0.09)^{T}$. We only state the first three components of x in Table 5.

Table 5 Numerical results for Example 4.4

Example 4.5

Let us consider the following GNEP. There are two players in the game, where player 1 controls a two-dimensional variable $x^{1}=(x_{1},x_{2})^{T}\in\Re^{2}$ and player 2 controls a one-dimensional variable $x^{2}=x_{3}\in\Re$. The problem is

$$\begin{aligned}& \min_{x_{1},x_{2}} x_{1}^{2}+x_{1}x_{2}+ x_{2}^{2}+(x_{1}+x_{2})x_{3}-25x_{1}-38x_{2} \\& \quad \mbox{s.t. } x_{1},x_{2}\geq0, \\& \hphantom{\quad \mbox{s.t. }} x_{1}+2x_{2}-x_{3}\leq14, \\& \hphantom{\quad \mbox{s.t. }} 3x_{1}+2x_{2}+x_{3}\leq30, \\& \min_{x_{3}} x_{3}^{2}+(x_{1}+x_{2})x_{3}-25x_{3} \\& \quad \mbox{s.t. } x_{3}\geq0, \\& \hphantom{\quad \mbox{s.t. }} x_{1}+2x_{2}-x_{3}\leq14, \\& \hphantom{\quad \mbox{s.t. }} 3x_{1}+2x_{2}+x_{3}\leq30. \end{aligned}$$

The problem has infinitely many solutions given by

$$\bigl\{ (\alpha,11-\alpha,8-\alpha)\mid\alpha\in[0,2]\bigr\} , $$

but it has only one normalized Nash equilibrium at $\alpha=0$.

Table 6 Numerical results for Example 4.5

Example 4.6

This GNEP from [18] is the electricity market problem. This model has three players, player 1 controls a single variable $x^{1}\in\Re$, player 2 controls a two-dimensional vector $x^{2}=(x_{1}^{2},x_{2}^{2})$, and player 3 controls a three-dimensional decision variable $x^{3}=(x_{1}^{3},x_{2}^{3},x_{3}^{3})$. Let

$$x=\bigl(x_{1}^{1},x_{1}^{2},x_{2}^{2},x_{1}^{3},x_{2}^{3},x_{3}^{3} \bigr)^{T} =(x_{1},x_{2},x_{3},x_{4},x_{5},x_{6})^{T}. $$

The utility functions are given by

$$\begin{aligned}& \theta^{1}(x) = \psi(x)x_{1}+\biggl( \frac {1}{2}c_{1}x_{1}^{2}+d_{1}x_{1}+e_{1} \biggr), \\& \theta^{2}(x) = \psi(x) (x_{2}+x_{3})+ \sum _{i=2}^{3}\biggl(\frac {1}{2}c_{i}x_{i}^{2}+d_{i}x_{i}+e_{i} \biggr), \\& \theta^{3}(x) = \psi (x) (x_{4}+x_{5}+x_{6})+ \sum_{i=4}^{6}\biggl(\frac {1}{2}c_{i}x_{i}^{2}+d_{i}x_{i}+e_{i} \biggr), \end{aligned}$$

where $\psi(x)=2(x_{1}+\cdots+x_{6})-378.4$ and the constants $c_{i}$, $d_{i}$, $e_{i}$ are given in Table 7.

Table 7 Values of constants for Example  4.6

The constraints are

$$\begin{aligned}& 0\leq x_{1}\leq80,\qquad 0\leq x_{2}\leq80, \qquad 0\leq x_{3}\leq50, \\& 0\leq x_{4}\leq55, \qquad 0\leq x_{5}\leq30, \qquad 0\leq x_{6}\leq40. \end{aligned}$$

Table 8 is for the corresponding numerical results.

Table 8 Numerical results for Example 4.6

The numerical experiments show that the method proposed in this paper is implementable for solving GNEPs with jointly convex constraints.

5 Remarks

The main idea of this paper is to try use a smoothing method to solve the GNEP. Based on the regularized Nikaido-Isoda function, we reformulate the set of normalized Nash equilibria, which is a subset of the generalized Nash equilibria, as solutions of a MPCC and we solve the MPCC by a smoothing method. There are some problems as regards the smoothing method worth further investigating:

• (i) In this paper, some conditions are given to establish the convergence of the smoothing method by showing that any accumulation point of the generated sequence is a M-stationary point of the MPCC. For the next step, less strict assumptions than Theorem 3.1 to obtain the results of Theorem 3.1 are worth considering.

• (ii) Based on the special structure of the MPCC defined in (3.3), can we derive convergence results tailored to the GNEP, which may possibly be stronger than those known for the MPCC? This problem is worth studying.