从经济学到自然科学,双层规划模型在很多领域都得到广泛的研究^[4].顾名思义, 双层规划模型^[3]是一个层次嵌套的模型, 它分为上层和下层.本文主要讨论双层规划的乐观模型.在乐观模型中, 上层决策者受2个变量 $x$和 $y$的影响, 其中 $y$又来自于下层问题的解, 受变量 $x$的影响.因此, 该问题可以看成一个有两个参与者的优化问题.但是, 这两个参与者在这个优化问题中扮演的角色并不对称, 上层决策者控制了2个变量 $x$和 $y$, 而下层决策者只控制了一个变量 $y$.这种上下层之间关系的不对称使得双层规划问题是一个困难问题^[2].如果在这种优化问题中, 上层和下层之间的关系是对等的, 例如所有的变量既受上层决策者的控制又受下层决策者的控制, 就会得到一个单纯的层次问题; 又或者变量 $x$仅仅受到上层决策者的控制而变量 $y$仅仅受到下层决策者的控制, 就会得到一个含有两个参与者的博弈模型, 而在这个问题中, 两个决策者的地位平等.

有两种形式的双层规划乐观模型^[1]受到了广泛的学习, 其中一种是原始双层规划乐观模型(OBP)

$ \begin{array}{*{20}{l}} {\mathop {{\rm{minimize}}}\limits_x \;\;\;{{\min }_y}\left\{ {F\left( {x,y} \right):y \in S\left( x \right)} \right\},}\\ {\;\;\;\;\;{\rm{s}}.{\rm{t}}.\;\;\;\;\;\;x \in X;} \end{array} $

(1.1)

还有一种就是标准双层规划乐观模型(SBP)

$ \begin{array}{*{20}{l}} {\mathop {{\rm{minimize}}}\limits_{x,y} \;\;\;\;\;\;F\left( {x,y} \right),}\\ {\;\;\;\;\;{\rm{s}}.{\rm{t}}.\;\;\;\;\;\;\;\;\;x \in X,y \in S\left( x \right),} \end{array} $

(1.2)

其中 $F:R^{n_{0} }\times R^{n_{1} }\to R, X\subseteq R^{n_{0}}$, 且集值映射 $S:R^{n_{0} }\Rightarrow R^{n_{1} }$, 集值映射 $S\left(x \right)$表示下层问题的解集, 下层问题为

$ \begin{array}{*{20}{l}} {\mathop {{\rm{minimize}}}\limits_w \;\;\;\;\;f\left( {x,w} \right),}\\ {\;\;\;\;\;{\rm{s}}.{\rm{t}}.\;\;\;\;\;\;\;\;w \in U,g\left( {x,w} \right) \le 0,} \end{array} $

(1.3)

其中 $f:R^{n_{0} }\times R^{n_{1} }\to R, g:R^{n_{0} }\times R^{n_{1} }\to R^{m}, U\subseteq R^{n_{1} }$.

在本文中, 对于要求解的OBP和SBP需要满足以下条件: $F, f:R^{n_{0} }\times R^{n_{1} }\to R, g:R^{n_{0} }\times R^{n_{1}}\to R^{m}$是连续的, $X\subseteq R^{n_{0} }, U\subseteq R^{n_{1}}$是闭集.

令 $W=\left\{ {\left( {x, y} \right):x\in X, y\in S\left( x\right)} \right\}, K\left( x \right)=\left\{ {v\in R^{n_{1}}:g\left( {x, v} \right)\leq 0} \right\}$.若 $\left( {x^{\ast }, y^{\ast }} \right)\in W, $且 $\forall (x, y)\in W, F\left({x^{\ast }, y^{\ast }} \right)\leq F\left( {x, y} \right)$, 则 $\left( {x^{\ast }, y^{\ast }} \right)$为SBP (1.2) 的一个全局解.将其详细表示出来就是

$ \left( {{x}^{*}},{{y}^{*}} \right)\in X\times U,f\left( {{x}^{*}},{{y}^{*}} \right)\le f\left( {{x}^{*}},y \right),\forall y\in U\cap K\left( {{x}^{*}} \right),g\left( {{x}^{*}},{{y}^{*}} \right)\le 0, $

(1.4)

$ F\left( {{x}^{*}},{{y}^{*}} \right)\le F\left( x,y \right),\forall \left( x,y \right)\in W, $

(1.5)

其中 $W = \left\{ {(u,v) \in X \times U:f\left( {u,v} \right) \le \mathit{f}\left( {u,w} \right)\forall w \in U\mathop \cap \nolimits^ K\left( u \right),g\left( {u,v} \right) \le 0} \right\}$.

OBP和SBP问题在求解全局解的时候是等价的^{[5, 6]}, 但是在局部解方面, SBP的一个局部解不一定是OBP的一个局部解.需要提到的是, 目前几乎所有的算法都是用来求解SBP的.而在通常情况下, SBP问题是非凸非光滑的.这样一来, 求解SBP问题就会变得比较困难, 想要找到一种可证明收敛性且实际操作可行的算法用来求解SBP问题则更加困难^{[7, 8]}.

广义纳什均衡问题(GNEP)也是一种有多个决策者参与的优化模型, 它与SBP不同的地方在于, 广义纳什均衡问题的多个决策者之间的地位平等, 求解广义纳什均衡问题的算法也发展的较为成熟^[9].

在下一节中, 会给出文献[1]中的一种广义纳什均衡问题的模型, 它会与SBP (1.2) 有很密切的关系.

针对上面提到的SBP模型, 文献[1]中提出了下面的GNEP模型:

$ \begin{equation}\label{eq6} \begin{array}{cl@{\qquad\qquad}cl} \mathop{\rm minimize}\limits_{x, y} & {F\left({x, y} \right)}, & {\mathop{\rm minimize}\limits_{w}} & f\left({x, w} \right), \\ \mbox{s.t.} & {\left({x, y} \right)} \in X\times U, & \mbox{s.t.} & {w\in U}, \\ & {f\left({x, y} \right)} \leq f\left({x, w} \right), & & {g\left({x, w} \right)} \leq 0, \\ & {g\left({x, y} \right)} \leq 0, & & \end{array} \end{equation} $

(2.1)

把控制变量 $x$和 $y$的参与者称为领导者, 其余的参与者称为从属者.令

$ T = \left\{ {\left( {x,y} \right) \in X \times U:g\left( {x,y} \right) \le 0} \right\},H\left( w \right) = \left\{ {\left( {x,y} \right) \in {R^{{n_0}}} \times {R^{{n_1}}}:f\left( {x,y} \right) \le f\left( {x,w} \right)} \right\}, $

则 $V\left( w\right)=T\cap H\left( w \right)$为领导者的可行域.若 $\left({x^{\ast }, y^{\ast }, w^{\ast }} \right)$为GNEP (2.1) 的一个均衡解, 则

$ \left( {{x^ * }, {y^ * }} \right) \in X \times U, f\left( {{x^ * }, {y^ * }} \right) \le f\left( {{x^ * }, {w^ * }} \right), g\left( {{x^ * }, {y^ * }} \right) \le 0, $

(2.2)

$ F\left( {{x^ * }, {y^ * }} \right){\rm{ }} \le F\left( {x, y} \right), \forall \left( {x, y} \right) \in V\left( {{w^ * }} \right), $

(2.3)

$ \ \ \ \ \ w*\in U,g(x*,w*)\le 0, $

(2.4)

$ f\left( {{x^ * }, {w^ * }} \right){\rm{ }} \le f\left( {{x^ * }, w} \right), \forall w \in U \cap K\left( {{x^ * }} \right), $

(2.5)

其中 $V\left( {w^{\ast }} \right)=\left\{ {\left( {u, v}\right)\in X\times U:f\left( {u, v} \right)\leq f\left( {u, w^{\ast }} \right), g\left( {u, v} \right)\leq 0} \right\}$.

定义2.1^[1]  若 $\left( {x^{\ast }, y^{\ast }, w^{\ast }} \right)$为GNEP (2.1) 的一个均衡解, 则

(a) $\left( {x^{\ast }, y^{\ast }} \right)$在SBP (1.2) 的可行域中, 即 $\left( {x^{\ast }, y^{\ast }} \right)\in W$;

(b)若对于满足 $\left( {x, y} \right)\in W, F\left( {x, y}\right)\leq F\left( {x^{\ast }, y^{\ast }} \right)$的任意 $x,g\left( {x, w^{\ast }} \right)\leq 0$成立, 则 $\left( {x^{\ast }, y^{\ast }} \right)$为SBP (1.2) 的一个全局解.

证  由于 $\left( {x^{\ast }, y^{\ast }, w^{\ast }} \right)$为GNEP (2.1) 的一个均衡解, 则 $\left( {x^{\ast }, y^{\ast }, w^{\ast }} \right)$满足(2.2)-(2.5).

(a)由(2.2), (2.4), (2.5) 可知 $\left( {x^{\ast }, y^{\ast }}\right)$满足(1.4), 即 $\left( {x^{\ast }, y^{\ast }} \right)\in W$.

(b)由(a)知(1.4) 式成立, 接下来要证明(1.5) 也成立.

令

$ {T^ * }{\rm{ }} = \left\{ {\left( {x, y} \right) \in {R^{{n_0}}} \times {R^{{n_1}}}:F\left( {x, y} \right) \le F\left( {{x^ * }, {y^ * }} \right)} \right\}, $

(2.6)

$ {\left( {{T^ * }} \right)^c}{\rm{ }} = \left\{ {\left( {x, y} \right) \in {R^{{n_0}}} \times {R^{{n_1}}}:F\left( {x, y} \right) > F\left( {{x^ * }, {y^ * }} \right)} \right\}. $

(2.7)

令 $\left( {\bar{{x}}, \bar{{y}}} \right)$为 $W\cap T^{\ast }$中任意一点, 由假设可知 $g\left( {\bar{{x}}, w^{\ast }} \right)\leq0$, 由此可知 $w^{\ast }\in U\cap K\left( {\bar{{x}}} \right)$, 又由于 $\left( {\bar{{x}}, \bar{{y}}} \right)\in W$, 所以有 $\left( {\bar{{x}}, \bar{{y}}} \right)\in V\left( {w^{\ast}} \right)$, 由 $\left( {\bar{{x}}, \bar{{y}}} \right)$的任意性可知 $W\cap T^{\ast }\subseteq V\left( {w^{\ast }}\right)$, 由(2.3) 知 $F(x^{\ast }, y^{\ast })\leq F\left( {x, y}\right), \forall (x, y)\in W\cap T^{\ast }$, 又 $F(x^{\ast }, y^{\ast }) < F\left( {x, y} \right), \forall \left( {x, y}\right)\in W\cap \left( {T^{\ast }} \right)^{c}$, 而 $W=\left({W\cap T^{\ast }} \right)\cup \left( {W\cap \left( {T^{\ast }}\right)^{c}} \right)$所以有 $F\left( {x^{\ast }, y^{\ast }}\right)\leq F\left( {x, y} \right), \forall \left( {x, y}\right)\in W$, (1.5) 成立.所以 $\left( {x^{\ast }, y^{\ast }}\right)$为SBP (1.2) 的一个全局解.

在很多情况下, 双层规划模型的下层可能存在多个并列参与者, 这些参与者彼此之间没有联系, 这时候双层规划模型就如下所示:

$ \begin{equation}\label{eq13} \begin{array}{cl} \min\limits_{x, y_{1}, y_{2}\cdots , y_{n}} & F(x, y_{1}, y_{2}\cdots, y_{n}), \\ \mbox{s.t.} & {x\in X}, \\ & {y_{1}} \in S_{1} (x), \\ & {y_{2}} \in S_{2} (x), \\ & ~~\quad \vdots \\ & {y_{n}} \in S_{n} (x), \\ \end{array} \end{equation} $

(3.1)

其中 $F:R^{m_{0} }\times R^{m_{1} }\times R^{m_{2} }\cdots \times R^{m_{n} }\to R, X\subset R^{m_{0} }$, $S_{1} (x)$, $S_{{\rm 2}}(x), \cdots, S_{n} (x)$分别表示 $n$个并列下层的解集, 下层问题为

$ \begin{array}{cl@{\quad}cl@{\qquad}c@{\quad}cl} \min\limits_{w_{1}} & f_{1} (x, w_{1}), & \min\limits_{w_{2}} & f_{2} (x, w_{2}), & & \min\limits_{w_{n}} & f_{n} (x, w_{n}), \\ \mbox{s.t.} & {w_{1} \in U_{1}}, & \mbox{s.t.} & w_{2} \in U_{2}, & \cdots & \mbox{s.t.} & w_{n} \in U_{n}, \\ & {g_{1}} (x, w_{1})\leq 0, & & {g_{2}}(x, w_{2})\leq 0, & & & {g_{n} (x, w_{n})} \leq 0, \\ \end{array} $

其中

$ \begin{matrix} {{f}_{1}}:{{R}^{{{m}_{0}}}}\times {{R}^{{{m}_{1}}}}\to R, {{g}_{1}}:{{R}^{{{m}_{0}}}}\times {{R}^{{{m}_{1}}}}\to {{R}^{{{n}_{1}}}}, {{U}_{1}}\subset {{R}^{{{m}_{1}}}}, \\ {{f}_{2}}:{{R}^{{{m}_{0}}}}\times {{R}^{{{m}_{2}}}}\to R, {{g}_{2}}:{{R}^{{{m}_{0}}}}\times {{R}^{{{m}_{2}}}}\to {{R}^{{{n}_{2}}}}, {{U}_{2}}\subset {{R}^{{{m}_{2}}}}, \\ \vdots \\ {{f}_{n}}:{{R}^{{{m}_{0}}}}\times {{R}^{{{m}_{n}}}}\to R, {{g}_{n}}:{{R}^{{{m}_{0}}}}\times {{R}^{{{m}_{n}}}}\to {{R}^{{{n}_{n}}}}, {{U}_{n}}\subset {{R}^{{{m}_{n}}}}, \\ \end{matrix} $

若 $(x^{\ast }, y_{1}^{\ast }, y_{2}^{\ast } \cdots, y_{n}^{\ast})$为SBP (3.1) 的全局解, 则

$ \begin{array}{*{20}{l}} {({x^*},y_1^*,y_2^*, \cdots ,y_n^*) \in X \times {U_1} \times {U_2} \times \cdots \times {U_n},}\\ {{f_1}({x^*},y_1^*) \le {f_1}({x^*},{y_1}),\forall {y_1} \in {U_1} \cap {K_1}({x^*}),{g_1}({x^*},y_1^*) \le 0,}\\ {{f_2}({x^*},y_2^*) \le {f_2}({x^*},{y_2}),\forall {y_2} \in {U_2} \cap {K_2}({x^*}),{g_2}({x^*},y_2^*) \le 0,}\\ {\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \vdots }\\ {{f_n}({x^*},y_n^*) \le {f_n}({x^*},{y_n}),\forall {y_n} \in {U_n} \cap {K_n}({x^*}),{g_n}({x^*},y_n^*) \le 0,} \end{array} $

(3.2)

$ F({{x}^{*}}, y_{1}^{*}, y_{2}^{*}, \cdots, y_{n}^{*})\le F(x, {{y}_{1}}, {{y}_{2}}, \cdots, {{y}_{n}}), \forall (x, {{y}_{1}}, {{y}_{2}}, \cdots, {{y}_{n}})\in W, $

(3.3)

其中

$ \begin{eqnarray*} W&= &\{(u, v_{1}, v_{2}\cdots , v_{n}) \in X\times U_{1} \times U_{2}\times \cdots \times U_{n}: \\ &&f_{1} (u, v_{1} {\rm)}\leq f_{1} \left({u, w_{1}} \right),~~\forall w_{1} \in U_{1} \cap K_{1} (u), g_{1} (u, v_{1})\leq 0; \\ &&f_{2} (u, v_{2} {\rm)}\leq f_{2} \left({u, w_{2}} \right),~~\forall w_{2} \in U_{2} \cap K_{2} (u), g_{2} (u, v_{2})\leq 0; \\ &&~~~~~~~~~~~~~~~~~~~~~~~~~~~~ \vdots \\ &&f_{n} (u, v_{n} {\rm)}\leq f_{n} \left({u, w_{n}} \right),~~\forall w_{n} \in U_{n} \cap K_{n} (u), g_{n} (u, v_{n})\leq 0 \}, \\ K_{n} (x)&=&\{v\in R^{m_{n}} : g_{n} (x, v)\leq 0\}. \end{eqnarray*} $

对于这种双层规划模型, 可以用同样的方法给出如下的GNEP模型.

领导者:

$ \begin{array}{*{20}{l}} {\mathop {\min }\limits_{x,{y_1},{y_2}, \cdots {y_n}} \;\;\;\;\;\;\;F(x,{y_1},{y_2} \cdots ,{y_n}),}\\ {\;\;\;\;{\rm{s}}.{\rm{t}}.\;\;\;\;\;\;\;\;\;\;(x,{y_1},{y_2}, \cdots ,{y_n}) \in X \times {U_1} \times {U_2} \cdots \times {U_n},}\\ {\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{f_1}(x,{y_1}) \le {f_1}(x,{w_1}),\quad {g_1}(x,{y_1}) \le 0,}\\ {\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{f_2}(x,{y_2}) \le {f_2}(x,{w_2}),\quad {g_2}(x,{y_2}) \le 0,}\\ {\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \vdots }\\ {\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{f_n}(x,{y_n}) \le {f_n}(x,{w_n}),\quad {g_n}(x,{y_n}) \le 0,} \end{array} $

(3.4)

从属者:

$ \begin{array}{cl@{\quad}cl@{\quad}c@{\quad}cl} \min\limits_{w_{1}} & f_{1} (x, w_{1}), & \min\limits_{w_{2}} & f_{2} (x, w_{2}), & & \min\limits_{w_{n}} & f_{n} (x, w_{n}), \\ \mbox{s.t.} & w_{1} \in U_{1}, & \mbox{s.t.} & {w_{2} \in U_{2}}, & \cdots & \mbox{s.t.} & w_{n} \in U_{n}, \\ & {g_{1}} (x, w_{1})\leq 0, & & g_{2} (x, w_{2}) \leq 0, & & & {g_{n}} (x, w_{n})\leq 0, \end{array} $

同样的, 把控制变量 $x, y_{1}, y_{2}, \cdots, y_{n}$的参与者称为领导者, 其他所有参与者称为从属者.令

$ \begin{array}{l} \;\;\;\;\;\;T\; = \{ (x,{y_1},{y_2}, \cdots ,{y_n}) \in X \times {U_1} \times {U_2} \times \cdots \times {U_n}:\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;{g_1}(x,{y_1}) \le 0,{g_2}(x,{y_2}) \le 0, \cdots ,{g_n}(x,{y_n}) \le 0,\} \\ H(W) = \{ (x,{y_1},{y_2}, \cdots ,{y_n}) \in {R^{{m_0}}} \times {R^{{m_1}}} \times {R^{{m_2}}} \times \cdots \times {R^{{m_n}}}:{f_1}(x,{y_1}) \le {f_1}(x,{w_1}),\\ \;\;\;\;\;\;\;\;\;\;\;\;\;{f_2}(x,{y_2}) \le {f_2}(x,{w_2}), \cdots ,{f_n}(x,{y_n}) \le {f_n}(x,{w_n})\} , \end{array} $

则 $V(W) = T\cap H(W)$为领导者的可行域.

若 $(x^{\ast }, y_{1}^{\ast }, y_{2}^{\ast }, \cdots, y_{n}^{\ast}, w_{1}^{\ast }, w_{2}^{\ast }, \cdots, w_{n}^{\ast})$为GNEP (3.4) 的一个均衡解, 则

$ \begin{array}{*{20}{l}} {({x^*},y_1^*,y_2^*, \cdots ,y_n^*) \in X \times {U_1} \times {U_2} \times \cdots \times {U_n},}\\ {{f_1}({x^*},y_1^*) \le {f_1}({x^*},w_1^*),{g_1}({x^*},y_1^*) \le 0,}\\ {{f_{\rm{2}}}({x^*},y_{\rm{2}}^*) \le {f_{\rm{2}}}({x^*},w_{\rm{2}}^*),{g_{\rm{2}}}({x^*},y_{\rm{2}}^*) \le 0,}\\ {\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \vdots }\\ {{f_n}({x^*},y_n^*) \le {f_n}({x^*},w_n^*),{g_n}({x^*},y_n^*) \le 0,} \end{array} $

(3.5)

$ F({{x}^{*}}, y_{1}^{*}, y_{2}^{*}, \cdots, y_{n}^{*}), F(x, {{y}_{1}}, {{y}_{2}}, \cdots, {{y}_{n}}), \forall (x, {{y}_{1}}, {{y}_{2}}, \cdots, {{y}_{n}})\in V({{W}^{*}}), $

(3.6)

$ w_{1}^{*}\in {{U}_{1}}, {{g}_{1}}({{x}^{*}}, w_{1}^{*})\le 0, w_{2}^{*}\in {{U}_{2}}, {{g}_{2}}({{x}^{*}}, w_{2}^{*})\le 0, \cdots, w_{n}^{*}\in {{U}_{n}}, {{g}_{n}}({{x}^{*}}, w_{n}^{*})\le 0, $

(3.7)

$ \begin{array}{*{20}{l}} {{f_1}({x^*},w_1^*) \le {f_1}({x^*},{w_1}),\forall {w_1} \in {U_1} \cap {K_1}({x^*}),}\\ {{f_2}({x^*},w_2^*) \le {f_2}({x^*},{w_2}),\forall {w_2} \in {U_2} \cap {K_2}({x^*}),}\\ {\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \vdots }\\ {{f_n}({x^*},w_n^*) \le {f_n}({x^*},{w_n}),\forall {w_n} \in {U_n} \cap {K_n}({x^*}).} \end{array} $

(3.8)

类似于定理2.1, 可以证明:

定理3.1  若 $(x^{\ast }, y_{1}^{\ast }, y_{2}^{\ast }, \cdots, y_{n}^{\ast }, w_{1}^{\ast }, w_{2}^{\ast }, \cdots, w_{n}^{\ast })$为GNEP (3.4) 的一个均衡解, 则

(a) $(x^{\ast }, y_{1}^{\ast }, y_{2}^{\ast }, \cdots, y_{n}^{\ast })$在SBP (3.1) 的可行域中, 即 $(x^{\ast }, y_{1}^{\ast }, y_{2}^{\ast }, \cdots, y_{n}^{\ast })\in W$;

(b)若对于满足 $(x, y_{1}, y_{2} \cdots y_{n}) \in W$, $F(x, y_{1}, y_{2}, \cdots, y_{n} \leq F(x^{{\rm \ast }}, y_{_{1}}^{{\rm \ast }}, y_{_{2} }^{\ast}, \cdots, y_{_{n} }^{\ast})$的任意 $x$, $g_{1} (x, w_{1}^{\ast } )\leq 0, g_{2} (x, w_{2}^{\ast } )\leq 0, \cdots, g_{n}(x, w_{n}^{\ast } )\leq 0$均成立, 则 $(x^{\ast }, y_{1}^{\ast },y_{2}^{\ast }, \cdots, y_{n}^{\ast } )$为SBP (3.1) 的一个全局解.

证  由于 $(x^{\ast }, y_{1}^{\ast }, y_{2}^{\ast }, \cdots, y_{n}^{\ast }, w_{1}^{\ast }, w_{2}^{\ast }, \cdots, w_{n}^{\ast })$为GNEP (3.4) 的一个均衡解, 则(3.5)-(3.8) 式满足.

(a)由(3.5), (3.7), (3.8) 式知 $(x^{\ast }, y_{1}^{\ast }, y_{2}^{\ast }, \cdots, y_{n}^{\ast })$满足(3.2), 即 $(x^{\ast },y_{1}^{\ast }, y_{2}^{\ast }, \cdots, y_{n}^{\ast })\in W$.

(b)由(a)知, (3.2) 式成立, 接下来要证明(3.3) 也成立:令

$ \begin{eqnarray*} T^{\ast} &=& \{(x, y_{1} , y_{2}, \cdots, y_{n})\in R^{m_{0} }\times R^{m_{1} }\times R^{m_{2} }\times\cdots \times R^{m_{n} }: F(x, y_{1} , y_{2}, \cdots, y_{n}) \\ &&\leq F(x^{\ast }, y_{1}^{\ast } , y_{2}^{\ast }, \cdots, y_{n}^{\ast })\}, \\ (T^{\ast})^{c} &=& \{(x, y_{1} , y_{2}, \cdots, y_{n})\in R^{m_{0} }\times R^{m_{1} }\times R^{m_{2} }\times\cdots \times R^{m_{n} }: F(x, y_{1} , y_{2} \cdots y_{n})\\ &&> F(x^{\ast }, y_{1}^{\ast } , y_{2}^{\ast }, \cdots, y_{n}^{\ast })\}. \end{eqnarray*} $

令 $(\bar{{x}}, \bar{{y}}_{1}, \bar{{y}}_{2}, \cdots, \bar{{y}}_{n} )$为 $W\cap T^{{\rm \ast }}$中任意一点, 由(b)中假设可知 $g_{1} (\bar{{x}}, w_{1}^{\ast } )\leq 0, g_{2}(\bar{{x}}, w_{2}^{\ast } )\leq 0, \cdots, g_{n} (\bar{{x}}, w_{n}^{\ast } )\leq 0$均成立.所以 $w_1^ * \in {U_1}{\rm{ }} \cap {\mathit{K}_1}(\overline x ),w_2^ * \in {U_2} \cap {K_2}(\overline x ), \cdots ,w_n^ * \in {U_n} \cap {K_n}(\overline x )$, 又由于 $(\bar{{x}}, \bar{{y}}_{1}, \bar{{y}}_{2},\cdots, \bar{{y}}_{n} )\in W$, 所以有 $(\bar{{x}}, \bar{{y}}_{1}, \bar{{y}}_{2}, \cdots, \bar{{y}}_{n} )\in V(W^{\ast})$, 由 $(\bar{{x}}, \bar{{y}}_{1}, \bar{{y}}_{2}, \cdots, \bar{{y}}_{n} )$的任意性知 $W \cap {T^ * } \subseteq \mathit{V}({W^ * })$.

由(3.6) 式知 $F(x^{\ast }, y_{1}^{\ast }, y_{2}^{\ast }, \cdots, y_{n}^{\ast })\leq F(x, y_{1}, y_{2}, \cdots, y_{n} ), \forall(x, y_{1}, y_{2}, \cdots, y_{n} )\in W\cap T^{{\rm \ast }}, $

又

$ F({{x}^{*}}, y_{1}^{*}, y_{2}^{*}, \cdots, y_{n}^{*}) < F(x, {{y}_{1}}, {{y}_{2}}, \cdots, {{y}_{n}}), \forall (x, {{y}_{1}}, {{y}_{2}}, \cdots, {{y}_{n}})\in W\cap {{({{T}^{*}})}^{c}}, $

而 $W=\left( {W\cap T^{\ast }} \right)\cup \left( {W\cap \left({T^{\ast }} \right)^{c}} \right), $所以有

$ F({{x}^{*}}, y_{1}^{*}, y_{2}^{*}, \cdots, y_{n}^{*})\le F(x, {{y}_{1}}, {{y}_{2}}\cdots {{y}_{n}}), \forall (x, {{y}_{1}}, {{y}_{2}}\cdots {{y}_{n}})\in W, $

(3.3) 式成立.所以 $(x^{\ast }, y_{1}^{\ast }, y_{2}^{\ast }, \cdots, y_{n}^{\ast } )$为SBP (3.1) 的一个全局解.证毕.

算法设计中要求 $T$非空, $X, U_{1}, U_{2}, \cdots, U_{n} $为紧集^[10].

在上一节中, 为SBP (3.1) 和GNEP (3.4) 之间建立了一定的联系, 这样一来, 就可以通过寻找GNEP (3.4) 的均衡解来求解SBP (3.1).文献[1]中给出了只有一个从属者情况下的GNEP (2.1) 的算法, 对其稍加修改^[1], 可以得到如下算法1.

给出初始的 $(x^{0}, w_{1}^{0}, w_{2}^{0}, \cdots, w_{n}^{0})\in T$, 令 $k=0$.

步骤1  计算 $(x^{k+1}, y_{1}^{k+1}, y_{2}^{k+1}, \cdots, y_{n}^{k+1} )$, 它是下述优化问题的解

$ \begin{array}{*{35}{l}} \underset{x,{{y}_{1}},{{y}_{2}},\cdots ,{{y}_{n}}}{\mathop{\rm{min}}}\,\ \ F(x,{{y}_{1}},{{y}_{2}},\cdots ,{{y}_{n}}), \\ \ \ \ \ \rm{s}.\rm{t}.\ \ \ \ \ \ (\mathit{x},{{\mathit{y}}_{\rm{1}}},{{\mathit{y}}_{\rm{2}}},\cdots ,{{\mathit{y}}_{\mathit{n}}})\in \mathit{X}\times {{\mathit{U}}_{\rm{1}}}\times {{\mathit{U}}_{\rm{2}}}\cdots \times {{\mathit{U}}_{\mathit{n}}}, \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ {{f}_{1}}(x,{{y}_{1}})\le {{f}_{1}}({{x}^{k}},w_{1}^{k}),\quad {{g}_{1}}(x,{{y}_{1}})\le 0, \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ {{f}_{2}}(x,{{y}_{2}})\le {{f}_{2}}({{x}^{k}},w_{2}^{k}),\quad {{g}_{2}}(x,{{y}_{2}})\le 0, \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ {{f}_{n}}(x,{{y}_{n}})\le {{f}_{n}}({{x}^{k}},w_{n}^{k}),\quad {{g}_{n}}(x,{{y}_{n}})\le 0, \\ \end{array} $

步骤2  计算 $(w_{1}^{k+1}, w_{2}^{k+1} \cdots, w_{n}^{k+1})$, 它是下述优化问题的解

$ \begin{array}{cl@{\quad}cl@{\quad}c@{\quad}cl} \min\limits_{w_{1} } & f_{1} (x^{k+1}, w_{1}), & {\min\limits_{w_{2} } } & f_{2} (x^{k+1}, w_{2}), & & \min\limits_{w_{n} } & f_{n} (x^{k+1}, w_{n}), \\ \mbox{s.t.} & w_{1} \in U_{1}, & \mbox{s.t.} & {w_{2} \in U_{2} }, & \cdots & \mbox{s.t.} & {w_{n} } \in U_{n}, \\ & {g_{1}} (x^{k+1}, w_{1})\leq 0, & & {g_{2} (x^{k+1}, w_{2})}, & & & {g_{n}} (x^{k+1}, w_{n})\leq 0, \\ \end{array} $

终止准则:若 $f_{1} (x^{k}, y^{k})=f_{1} (x^{k}, w_{1}^{k} ), f_{2} (x^{k}, y^{k})=f_{2} (x^{k}, w_{2}^{k} ), \cdots, f_{n}(x^{k}, y^{k})=f_{n} (x^{k}, w_{n}^{k} )$, 停止; 否则令 $k=k+1$, 转步骤1 (实际计算中可以取适当的精度).

下面定理给出了上述算法1的一些基本性质.

定理4.1  令 $\{(x^{k}, y_{1}^{k}, y_{2}^{k}，\cdots, y_{n}^{k}, w_{1}^{k}, w_{2}^{k}, \cdots, w_{n}^{k} )\}$为算法1产生的序列, 则

(a)算法1是明确定义的;

(b) $\forall k\ge 0,{{f}_{1}}({{x}^{k+1}},w_{1}^{k+1})\le {{f}_{1}}({{x}^{k}},w_{1}^{k}),{{f}_{2}}({{x}^{k+1}},w_{2}^{k+1})\le {{f}_{2}}({{x}^{k}},w_{2}^{k}),\cdots ,{{f}_{n}}({{x}^{k+1}},w_{n}^{k+1})\le {{\mathit{f}}_{n}}({{x}^{k}},w_{n}^{k});$

(c) $\forall k\geq 1, F(x^{k+1}, y_{1}^{k+1}, y_{2}^{k+1}, \cdots, y_{n}^{k+{\rm 1}} )\geq F(x^{k}, y_{1}^{k}, y_{2}^{k}, \cdots, y_{n}^{k})$;

(d) $\forall k\geq {\rm 1}$, $(x^{k}, w_{1}^{k}, w_{2}^{k}, \cdots w_{n}^{k})$都在SBP (3.1) 的可行域中;

(e)算法1产生的序列 $\{(x^{k}, y_{1}^{k}, y_{2}^{k}, \cdots, y_{n}^{k}, w_{1}^{k}, w_{2}^{k}, \cdots, w_{n}^{k})\}$有界, 并且算法1经过有限步迭代终止或者其极限点满足终止条件, 序列 $\{f_{1}(x^{k}, w_{1}^{k} )\}, \{f_{2} (x^{k}, w_{2}^{k})\}, \cdots, \{f_{n} (x^{k}, w_{n}^{k} )\}$等都收敛.

证  (a)由于 $\{(x^{k}, y_{1}^{k}, y_{2}^{k} \cdots, y_{n}^{k}, w_{1}^{k}, w_{2}^{k} \cdots, w_{n}^{k} )\}$为算法1产生的序列, 所以步骤1的可行域中至少存在点 $(x^{k}, w_{1}^{k}, w_{2}^{k} \cdots, w_{n}^{k})$, 步骤2的可行域中至少存在点 $y_{1}^{k}, y_{2}^{k} \cdots, y_{n}^{k} $, 由魏尔斯特拉斯定理知, 步骤1和步骤2明确定义.

(b)由于 $y_{1}^{k}, y_{2}^{k} \cdots, y_{n}^{k} $为步骤2可行域中的点, 所以 $f_{1} (x^{k+1}, w_{1}^{k+1} )\leq f_{1}(x^{k+1}, y_{1}^{k+1} ), $

$ {{f}_{2}}({{x}^{k+1}},w_{2}^{k+1})\le {{f}_{2}}({{x}^{k+1}},y_{2}^{k+1}),\cdots ,{{f}_{n}}({{x}^{k+1}},w_{n}^{k+1})\le {{f}_{n}}({{x}^{k+1}},y_{n}^{k+1}). $

又由步骤1知

$ {{f}_{1}}({{x}^{k+1}}, y_{1}^{k+1})\le {{f}_{1}}({{x}^{k}}, w_{1}^{k}), {{f}_{2}}({{x}^{k+1}}, y_{2}^{k+1})\le {{f}_{2}}({{x}^{k}}, w_{2}^{k}), \cdots, {{f}_{n}}({{x}^{k+1}}, y_{n}^{k+1})\le {{f}_{n}}({{x}^{k}}, w_{n}^{k}), $

得 $\forall k\ge 0,{{f}_{1}}({{x}^{k+1}},w_{1}^{k+1})\le {{f}_{1}}({{x}^{k}},w_{1}^{k}),{{f}_{2}}({{x}^{k+1}},w_{2}^{k+1})\le {{f}_{2}}({{x}^{k}},w_{2}^{k}),\cdots ,{{f}_{n}}({{x}^{k+1}},w_{n}^{k+1})\le {{\mathit{f}}_{n}}({{x}^{k}},w_{n}^{k}).$

(c)在步骤1中, $f_{1} (x^{k}, w_{1}^{k} ), f_{2} (x^{k}, w_{2}^{k} ), {\rm \cdots, }f_{n} (x^{k}, w_{n}^{k} )$为边界条件, 而又由(b)知

$ \{{{f}_{1}}({{x}^{k}}, w_{1}^{k})\}, \{{{f}_{2}}({{x}^{k}}, w_{2}^{k})\}, \cdots, \{{{f}_{n}}({{x}^{k}}, w_{n}^{k})\} $

等序列都是单调非增的, 即步骤1中的边界单调非增, 所以步骤1的可行域的大小单调非增, 所以可以得到

$ \forall k\ge 1, F({{x}^{k+1}}, y_{1}^{k+1}, y_{2}^{k+1}, \cdots, y_{n}^{k+\text{1}})\ge F({{x}^{k}}, y_{1}^{k}, y_{2}^{k}, \cdots, y_{n}^{k}). $

(d)由于 $w_{1}^{k+1}, w_{2}^{k+1}, \cdots, w_{n}^{k+1} $为步骤2的最优点, 通过观察对比可以发现 $\forall k\geq 1, (x^{k}, w_{1}^{k}, w_{2}^{k}, \cdots, w_{n}^{k})$都在SBP (3.1) 的可行域中.

(e)由 $X, U_{1}, U_{2}, \cdots, U_{n} $的紧性可知, 算法1产生的序列有界.若算法1经过有限步迭代后不终止, 则由(b)以及紧性的假设可知, 序列 $\{f_{1}(x^{k}, w_{1}^{k} )\}, \{f_{2}(x^{k}, w_{2}^{k} )\}, \cdots, \{f_{n} (x^{k}, w_{n}^{k} )\}$都收敛, 所以有 $\lim\limits_{k\to \infty } f_{1} (x^{k}, w_{1}^{k})-f_{1} (x^{k+1}, w_{1}^{k+1} )=0, \cdots, \lim\limits_{k\to \infty} f_{n} (x^{k}, w_{n}^{k} )-f_{n} (x^{k+1}, w_{n}^{k+1} )=0$等成立, 综合(b)可知 $\lim\limits_{k\to \infty } f_{1} (x^{k+1}, y_{1}^{k+1} )-f_{1} (x^{k+1}, w_{1}^{k+1} )=0, \cdots, \lim\limits_{k\to \infty } f_{n} (x^{k+1}, y_{n}^{k+1} )-f_{n}(x^{k+1}, w_{n}^{k+1} )=0$等成立, 即满足终止条件.证毕.

下面给出算法的数值计算的算例:

例1^[1]

$ \begin{array}{cl@{\qquad}cl} \min\limits_{x, y} & F(x, y)=-(x+y)\wedge 2, & \min\limits_{w} & f(x, w)=(w-1/2)\wedge 2, \\ \mbox{s.t.} & {x\in R}, & \mbox{s.t.} & {w\in R}, \\ & {y\in S(x)}, & & {x\wedge 2+w\wedge 2-1\leq 0}, \end{array} $

其中 $S(x)$为下层的解集.这是一个非常简单的双层规划问题.将其转换为对应的广义纳什均衡问题如下

$ \begin{array}{cl@{\qquad}cl} \min\limits_{x, y} & F(x, y)=-(x+y)\wedge 2, & {\min\limits_{w} } & f(x, w)=(w-1/2)\wedge 2, \\ \mbox{s.t.} & {x\times y\in R\times R}, & \mbox{s.t.} & {w\in R}, \\ & {(y-1/2)\wedge 2\leq (w-1/2)\wedge 2}, & & {x\wedge 2+w\wedge 2-1\leq 0}, \\ & {x\wedge 2+y\wedge 2-1\leq 0}, & & \end{array} $

利用第4节算法1可以计算出该广义纳什均衡问题的均衡点.

而例1中双层规划问题的全局解为(0.8660, 0.5000), 可知算法1实例可行, 而迭代步骤都为两步, 也说明了该算法的效率.

例2^[3]

$ \begin{array}{cl} \min\limits_{x, y_{1}, y_{2} } & F(x, y_{1}, y_{2})=x-2y_{1} +y_{2}, \\ \mbox{s.t.} & {x\in [0, 10]},~~ {y_{1} } \in S_{1} (x),~~ {y_{2} } \in S_{2} (x), \end{array} $

上层

$ \begin{array}{cl@{\qquad}cl} \min\limits_{w_{1} } & f_{1} (x, w_{1})=x-2w_{1}, & {\min\limits_{w_{2} } } & f_{2} (x, w_{2})=2x+w_{2}, \\ \mbox{s.t.} & {w_{1} \in [0, 10]}, & \mbox{s.t.} & {w_{2} \in [0, 10]}, \\ & {x+w_{1} } \leq 5, & & {x-w_{2} } \leq 5, \\ \end{array} $

下层

将其转换为相应的广义纳什均衡问题如下

$ \begin{array}{cl} \min\limits_{x, y_{1}, y_{2} } & F(x, y_{1}, y_{2})=x-2y_{1} +y_{2}, \\ \mbox{s.t.} & x, y_{1}, y_{2} \in [0, 10],~~ x-2y_{1} \leq x-2w_{1},~~ x+y_{1} \leq 5, \\ & 2x+y_{2} \leq 2x+w_{2}, ~~ x-y_{2} \leq 5, \end{array} $

领导者

$ \begin{array}{cl@{\qquad}cl} \min\limits_{w_{1}} & f_{1} (x, w_{1})=x-2w_{1}, & {\min\limits_{w_{2}}} & f_{2} (x, w_{2})=2x+w_{2}, \\ \mbox{s.t.} & {w_{1} \in [0, 10]}, & \mbox{s.t.} & {w_{2} \in [0, 10]}, \\ & {x+w_{1}} \leq 5, & & {x-w_{2}} \leq 5. \end{array} $

从属者

利用第4节算法1可以计算出该广义纳什均衡问题的均衡点.

而例2中双层问题的解为(0, 5, 0), 同样可知算法1可行, 迭代步骤为1, 也说明了算法的效率.

本文虽然将一类多并列下层的双层规划模型和一类广义纳什均衡问题建立了联系, 但是还是有很多的不足之处.例如定理2.1, 3.1中的条件有些苛刻, 且在实际计算中不好对其进行判断, 最好能够对该条件进行修改, 给出更宽泛且易于判断的条件.