二层规划问题因为广泛的实际应用而倍受关注^{[1, 2]}, 然而即使约束条件是线性的, 二层规划问题的求解仍然是NP难的.一般是利用下层规划的KKT条件将二层规划转化为单层规划.由于互补松弛条件的存在使得约束规格不成立^[3-6], 从而很多传统的非线性规划的解法无法应用.因此, 我们对于转化后的单层问题给出扰动, 然后讨论扰动问题的解、收敛性以及与原二层规划解之间的关系.人工神经网络是一非线性动力学系统, 它具有大规模并行协同处理能力.利用神经网络方法求解最优化问题近年来发展迅速^[7].本文讨论了二层规划问题一种神经网络方法, 最后是相关的数据实验.

考虑二层规划问题：

$ \begin{eqnarray*} &&({\hbox{UP}})~~~~~~~~~~ \underset{x\in X}{\mathop{\min }}\, F(x, y), \\ && ~~~~~~~~~~{\hbox{s.t.}}~~~~~G(x, y)\ge 0, ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ({\hbox{BLP}}) \\ &&({\hbox{LP}})~~~~~~~~~~ \underset{y\in Y}{\mathop{\min }}\, f(x, y), \nonumber \\ && ~~~~~~~~~~{\hbox{s.t.}}~~~~~g(x, y)\ge 0, \end{eqnarray*} $

其中

$ F, f:{{R}^{{{n}_{1}}+{{n}_{2}}}}\to R，G:{{R}^{{{n}_{1}}+{{n}_{2}}}}\to {{R}^{{{m}_{1}}}}，g:{{R}^{{{n}_{1}}+{{n}_{2}}}}\to {{R}^{{{m}_{2}}}}，X\subset R^{{{n}_{1}}}，Y\subset R^{{{n}_{2}}} $

是二阶连续可微函数, (UP), (LP)分别表示上、下层规划, 分别是上、下层规划的决策变量.

本文中我们假设: (A1) 对任意给定$x\in \{x|\exists y, {\hbox{s.t.}}~~G(x, y)\ge 0g(x, y)\ge 0\}$, 下层规划(LP)是满足MFCQ的凸规划.

(A2) BLP问题的约束域$S=\{(x, y): G(x, y)\ge 0, g(x, y)\ge 0\} $是非空紧集.

在(A1) 和(A2) 条件下, BLP可变为

$ \begin{eqnarray*} &&~~~~~~~~~~~~~~\underset{x, y, \lambda }{\mathop{\min }}\, \quad F(x, y), \\ &&~~~~~~~~~{\hbox{s.t.}}~~~~~G(x, y)\ge 0, \\ &&~~~~~~~~~~~~~~{{\nabla }_{y}}L(x, y, \lambda )=0, ~~~~~~~~~~~~~~~~~~~~~~~( {\hbox{SP}} )\\ &&~~~~~~~~~~~~~~{{\lambda }^{T}}g(x, y)=0, \\ &&~~~~~~~~~~~~~~g(x, y)\ge 0, \\ &&~~~~~~~~~~~~~~\lambda \ge 0, \end{eqnarray*} $

其中${{\lambda }^{T}}g(x, y)=0$叫互补松弛条件, $L(x, y, \lambda)=f(x, y)+\lambda \cdot g(x, y)$是下层规划的Lagrange函数.显然问题属于MPEC.然而, MPEC问题在可行域内任何点均不满足MFCQ约束规格(Mangasarian-Fromovitz Constraint Qualification), 更不用说线性独立规格(LICQ).为此, 我们引进MPEC-LICQ定义.

为方便起见, 引进以下记号:记${x}'=(x, y, \lambda), {{G}_{I}}={{I}_{G}}=\left\{ i\left| {{G}_{i}}=0 \right. \right\}, K=\left\{ k\left| {{\lambda }_{k}}=0 \right. \right\}$.

定义1  对于MPEC问题, 除互补松弛条件以外, 其他积极约束条件线性独立我们称为MPEC-LICQ, 对于SP是

$ \begin{eqnarray} \begin{aligned} M=\left( \begin{aligned} & \ \ {{\nabla }_{x}}{{G}_{I}}\quad \quad \quad \quad \quad {{\nabla }_{y}}{{G}_{I}}\quad \quad \quad \quad 0\quad \nonumber\\ & {{\nabla }_{x}}f+\nabla _{yx}^{2}{{\lambda }^{T}}g\quad {{\nabla }_{y}}f+\nabla _{yy}^{2}{{\lambda }^{T}}g\quad {{\nabla }_{y}}{{g}_{{{K}^{C}}}} \\ & \quad {{\nabla }_{x}}{{g}_{J}}\quad \quad \quad \quad \quad {{\nabla }_{y}}{{g}_{J}}\quad \quad \quad \quad 0 \\ \end{aligned} \right) \end{aligned} \end{eqnarray} $

行满秩.

定义2  对于MPEC问题

$ \begin{eqnarray} \begin{aligned} & \min f(x, y) \\ &{\hbox{s.t.}}\quad \min \{g{}_{1}(x, y), g{}_{2}(x, y)\}=0, \nonumber\\ \end{aligned} \end{eqnarray} $

若$z$满足$\{\nabla {{g}_{i}}(z)\cdot d\left| i:{{g}_{i}}(z)=0\}=0, i=1, 2 \right.$, 称点为$B$ -稳定点.

因为许多传统非线性规划算法依赖于线性独立约束规格(LICQ), 而MPEC问题可行域内所有点均不满足, 为了避免这一困难, 我们考虑扰动的规划问题:

$ \begin{eqnarray*} &&~~~~~~~~~\underset{x, y, \lambda }{\mathop{\min }}\, \quad F(x, y), \nonumber\\ &&{\hbox{s.t.}}~~~~~G(x, y)\ge 0, \\ &&~~~~~~~~~{{\nabla }_{y}}L(x, y, \lambda )=0, ~~~~~~~~~~~~~~~~\left( {\hbox{SP}} \right)\\ &&~~~~~~~~~{{\lambda }^{T}}g(x, y)\le {{\varepsilon }_{n}}, \\ &&~~~~~~~~~g(x, y)\ge 0, \\ &&~~~~~~~~~\lambda \ge 0. \end{eqnarray*} $

由文献[4, 6], 有下述命题.

命题1  如果在BLP问题的可行点${{\bar{{x}'}}_{n}}$处MPEC-LICQ成立, 则存在${{\bar{{x}'}}_{n}}$的邻域$U$以及$\varepsilon >0$, 使得LICQ在任一点$z\in U\cap F({\hbox{S}}{{\overset{{}}{\mathop{{\hbox{P}}}}\, }_{{{\varepsilon }_{n}}}})$成立^[4].

定理1  若${{\bar{{x}'}}_{n}}$是的$B$ -稳定点, 且在${{\bar{{x}'}}_{n}}$处MPEC-LICQ、二阶充分条件成立, 则${{\bar{{x}'}}_{n}}$是BLP问题的局部最优解, 且存在${{\bar{{x}'}}_{n}}$的邻域$U$和$\bar{\varepsilon }$, 使得对${{\varepsilon }_{n}} < \bar{\varepsilon }$有唯一的稳定点${{\bar{{x}'}}_{n}}, {{\bar{{x}'}}_{n}}\to \bar{{x}'}$.

定理1的证明  当${{\bar{{x}'}}_{n}}$是SP的$B$ -稳定点且二阶充分条件成立时, ${{\bar{{x}'}}_{n}}$是SP的严格局部极小值点, 此时

$ \begin{eqnarray} \begin{aligned} BD=\left\{ d\left| \begin{aligned} & {{d}^{T}}\nabla {{G}_{j}}(\bar{{x}'})\ \left\{ \begin{aligned} & \ge 0({{\gamma }_{j}}=0), \\ & =0({{\gamma }_{j}}>0), \\ \end{aligned} \right.~~j\in {{J}_{G}}(\bar{{x}'}), \nonumber\\ & {{d}^{T}}\nabla {{g}_{i}}(\bar{{x}'})\ \left\{ \begin{aligned} & \ge 0({{\eta }_{i}}=0), \\ & =0({{\eta }_{i}}>0), \\ \end{aligned} \right.~~i\in {{I}_{g}}(\bar{{x}'}), \\ & {{d}^{T}}\nabla {{\lambda }_{i}}(\bar{{x}'})\ \left\{ \begin{aligned} & \ge 0({{\upsilon }_{j}}=0), \\ & =0({{\upsilon }_{j}}>0), \\ \end{aligned} \right.~~i\in {{I}_{\lambda }}(\bar{{x}'}), \\ & {{d}^{T}}\nabla {{g}_{i}}(\bar{{x}'})=0, \ i\in {{I}_{g}}\backslash {{I}_{\lambda }}, \\ & {{d}^{T}}\nabla {{\lambda }_{i}}(\bar{{x}'})=0, \ i\in {{I}_{\lambda }}\backslash {{I}_{g}}. \end{aligned} \right. \right\} \end{aligned} \end{eqnarray} $

由文献[4]中的定理4.1, 可知结论成立.这里的条件并不难达到, 事实上文献[4]中指出, 对于SP问题的函数空间, 有稠密子集${{P}_{0}}$, 使得在${{P}_{0}}$中SP的所有可行点MPEC-LICQ成立, 且对于局部极小点${{\bar{{x}'}}_{n}}$, 二阶充分条件成立^[4].

在$S{{P}_{{{\varepsilon }_{n}}}}$中, 记

$ \begin{eqnarray} \begin{aligned} c({x}')=\left\{ \begin{aligned} & -G(x, y), \\ & {{\lambda }^{T}}g(x, y)-{{\varepsilon }_{n}}，q({x}')={{\nabla }_{y}}L(x, y, \lambda ), \nonumber\\ & -g(x, y), \\ & -\lambda, \end{aligned} \right. \end{aligned} \end{eqnarray} $

则${\hbox{S}}{{{\hbox{P}}}_{{{\varepsilon }_{n}}}}$问题可以改写为

$ \begin{eqnarray} \begin{aligned} \begin{aligned} & ~~~\underset{{{x}'}}{\mathop{\min }}\, \quad F({x}'), \nonumber\\ & {\hbox{s.t.}}\text{ }\left\{ \begin{aligned} & c({x}')\le 0, \\ & q({x}')=0. \\ \end{aligned} \right. \end{aligned} \end{aligned} \end{eqnarray} $

本文利用文献[7]的方法，结合上述扰动思想，求解二层规划问题的一般方法为$E({x}', \upsilon, \mu)=F({x}')+{{\upsilon }^{T}}q({x}')+{{\mu }^{T}}c({x}')\mu $神经网络动态方程为

$ \begin{eqnarray} \begin{aligned} \left\{ \begin{aligned} & \frac{d{x}'}{dt}=-{{\nabla }_{{{x}'}}}L({x}', \upsilon, \mu ), \\ & \frac{d\upsilon }{dt}={{\nabla }_{\upsilon }}L({x}', \upsilon, \mu ), \\ & \frac{d\mu }{dt}={{\nabla }_{\mu }}L({x}', \upsilon, \mu ), \end{aligned} \right. \end{aligned} \end{eqnarray} $

(3.1)

写成标量的形式是

$ \begin{eqnarray} \begin{aligned} \left\{ \begin{aligned} \frac{d{{{{x}'}}_{i}}}{dt}= &-\frac{\partial F({x}')}{\partial {{{{x}'}}_{i}}}-\upsilon \frac{\partial ({{f}_{y}}({x}')+\lambda {{g}_{y}}({x}'))}{\partial {{{{x}'}}_{i}}}\\ &+\sum\limits_{i=1}^{{{m}_{1}}}{\mu _{k}^{2}\frac{\partial {{G}_{k}}({x}')}{\partial {{{{x}'}}_{i}}}-\sum\limits_{i=1}^{{{m}_{2}}}{\mu _{k}^{2}\frac{\partial {{g}_{k}}({x}')}{\partial {{{{x}'}}_{i}}}-\sum\limits_{i=1}^{{{m}_{2}}}{\mu _{k}^{2}\frac{\partial ({{\lambda }_{k}}{{g}_{k}}({x}')-{{\varepsilon }_{n}})}{\partial {{{{x}'}}_{i}}}}}}, \\ \frac{d\upsilon }{dt}= &{{f}_{y}}({x}')+\lambda {{g}_{y}}({x}'), \\ \frac{d{{\mu }_{k}}}{dt}= &-G(x, y){{\mu }_{k}}\quad \quad (k=1, \, 2, \ \cdots {{m}_{1}}), \nonumber\\ \frac{d{{\mu }_{k}}}{dt}= &({{\lambda }^{T}}g(x, y)-{{\varepsilon }_{n}}){{\mu }_{k}}\quad (k={{m}_{1}}+1, \, {{m}_{1}}+2, \ \cdots {{m}_{1}}+{{m}_{2}}), \\ \frac{d{{\mu }_{k}}}{dt}= & -g(x, y)\quad (k={{m}_{1}}+{{m}_{2}}+1, \, {{m}_{1}}+{{m}_{2}}+2, \ \cdots {{m}_{1}}+2{{m}_{2}}. \end{aligned} \right. \end{aligned} \end{eqnarray} $

定理2  如果在BLP问题的可行点${{\bar{{x}'}}_{n}}$处MPEC-LICQ成立, 且${\hbox{S}}{{{\hbox{P}}}_{{{\varepsilon }_{n}}}}$满足二阶充分条件, 则${{\bar{{x}'}}_{n}}$是系统(3.1) 的稳定点.

定理2的证明  若${{\bar{{x}'}}_{n}}$处MPEC-LICQ成立, 则存在${{\bar{{x}'}}_{n}}$的邻域$U$以及$\varepsilon >0$, 使得LICQ在任一点$z\in U\cap F({\hbox{S}}{{\overset{{}}{\mathop{{\hbox{P}}}}\, }_{{{\varepsilon }_{n}}}})$成立^[2], 又${\hbox{S}}{{{\hbox{P}}}_{{{\varepsilon }_{n}}}}$满足二阶充分条件, ${{\bar{{x}'}}_{n}}$是BLP问题的局部最优解, 且存在${{\bar{{x}'}}_{n}}$的邻域$U$和$\bar{\varepsilon }$, 使得对${{\varepsilon }_{n}} < \bar{\varepsilon }, {\hbox{S}}{{{\hbox{P}}}_{{{\varepsilon }_{n}}}}$有唯一的稳定点${{\bar{{x}'}}_{n}}{{\bar{{x}'}}_{n}}\to \bar{{x}'}$.

由KKT条件知, ${{\bar{{x}'}}_{n}}$是$E({x}', \upsilon, \mu)$的鞍点, 即${{\bar{{x}'}}_{n}}$是$E({x}', \upsilon, \mu)$的稳定点, 由可微函数极值点的必要条件知定理成立.

利用Matlab 6.5中的ode45命令, 取${{\varepsilon }_{n}}=0.001$.

例1  

$ \begin{eqnarray} \begin{aligned} & ~~~~\max {{f}_{1}}(x, y)=-x, \\ & {\hbox{s.t.}} \text{ }x\ge 0, \\ & ~~~~\max {{f}_{2}}(x, y)=-y, \nonumber\\ & {\hbox{s.t.}} \text{ }x+y\ge 2, \\ &~~~~ \text{ }x-y\le 0, \\ & ~~~~\text{ }y\ge 0, \end{aligned} \end{eqnarray} $

结果是$x = -0.0000, 2.0000, 1.0000, 0.0000.$

例2  

$ \begin{eqnarray} \begin{aligned} & ~~~~~~\underset{x\ge 0}{\mathop{\min }}\, \ \ F(x, y)=-{{x}_{1}}^{2}-3{{x}_{2}}^{2}-4{{y}_{1}}+{{y}_{2}}^{2}, \\ & {\hbox{s.t.}}\quad \ {{x}_{1}}^{2}+2{{x}_{2}}\le 4, \\ & ~~~~~~\underset{y\ge 0}{\mathop{\min }}\, \ \ f(x, y)=2{{x}_{1}}^{2}+{{y}_{1}}^{2}-5{{y}_{2}}, \\ & ~~~~~~ \text{ }{{x}_{1}}^{2}-2{{x}_{1}}+{{x}_{2}}^{2}-2{{y}_{1}}+{{y}_{2}}\ge -3, \\ & ~~~~~~ \text{ }{{x}_{2}}+3{{y}_{1}}-4{{y}_{2}}\ge 4, \end{aligned} \end{eqnarray} $

(4.1)

可得$x = 0.0000, 2.0000, 1.8750, 0.9062, 0, 1.2500, fval = -18.6787. $