本文考虑如下非线性互补约束均衡问题(MPEC):

$ \min f(x, y)\\ \mbox{s.t.} g_{j}(x, y)\geq 0, \quad w_{j}=F_{j}(x, y), \quad 0\leq w\perp y\geq 0, $

(1.1)

其中$f:R^{n+m_{2}}\rightarrow R$, $g_{j}:R^{n+m_{2}}\rightarrow R$, $j=1, \cdots, m_{1}$, $F_{j}:R^{n+m_{2}}\rightarrow R$, $j=1, \cdots, m_{2}$, 二阶连续可微, $w\perp y$表示向量$w$与$y$垂直.该问题在经济模型, 工程设计等领域有着广泛的应用, 近年来关于该类问题的研究及应用见文献[1]-[3].

显然, 若将互补约束条件$w\perp y$视为$w^{T}y=0$, 则均衡问题(MPEC)(1.1) 等价于一个光滑非线性规划问题.然而, 文献文献[4]指出:即使没有约束$g(x, y)\geq 0$, 且函数$F(x, y)$具有很好的性质, 对于该光滑非线性规划问题, 较弱的MFCQ条件在任意可行点处都不满足, 故非线性规划一些经典的算法一般不能直接应用到均衡问题上来.关于均衡问题的研究, 文献[5]-[7]利用带扰动参数的互补函数, 通过求解一系列光滑扰动问题来成功逼近原均衡问题的解.在渐近弱退化条件下, 这类扰动问题所产生序列的聚点称为原问题的稳定点.

本文通过构造新的互补函数, 利用逐次逼近思想, 为问题(1.1) 提出新的光滑化技巧.

易知

$ y\geq 0, w\geq 0, y^{T}w=0\Leftrightarrow \min\{y_{j}, w_{j}\}=0, j=1, \cdots, m_{2}. $

(1.2)

如文献[2], 定义函数$\phi(y_{j}, w_{j}, u)=-u \ln(e^{-\frac{y_{j}}{u}}+e^{-\frac{w_{j}}{u}}), j=1, \cdots, m_{2}$, 有

$ \mathop {\lim }\limits_{u \to 0} \phi ({y_j},{w_j},u) = \mathop {\lim }\limits_{u \to 0} [ - u\ln ({e^{ - \frac{{{y_j}}}{u}}} + {e^{ - \frac{{{w_j}}}{u}}})] = \min \{ {y_j},{w_j}\} = 0,j = 1, \cdots ,{m_2}. $

(1.3)

由(1.3), 很自然定义

$ \mathop {\lim }\limits_{u \to 0} \phi ({y_j},{w_j},u) = \phi ({y_j},{w_j},0),j = 1, \cdots ,{m_2}. $

(1.4)

由$\phi$的定义, 有

$ \begin{array}{l} \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\nabla \phi (y,w,u) = {\left( \begin{array}{l} \;\;\;\;\;\;\;{\bf{0}}\\ {\nabla _y}\phi (y,w,u)\\ {\nabla _w}\phi (y,w,u) \end{array} \right)_{(n + 2{m_2}) \times 1}}\\ = {\left( {\begin{array}{*{20}{c}} {{\bf{0}},\frac{{\partial \phi ({y_1},{w_1},u)}}{{\partial {y_1}}}, \cdots ,\frac{{\partial \phi ({y_{{m_2}}},{w_{{m_2}}},u)}}{{\partial {y_{{m_2}}}}},\frac{{\partial \phi ({y_1},{w_1},u)}}{{\partial {w_1}}}, \cdots ,\frac{{\partial \phi ({y_{{m_2}}},{w_{{m_2}}},u)}}{{\partial {w_{{m_2}}}}}} \end{array}} \right)^T} \end{array} $

(1.5)

借助于互补函数$\phi$, 下面我们提出如下非线性规划$(NLP_{u})$:

$ \begin{array}{l} \min \;\;\;f(x,y)\\ {\rm{s}}{\rm{.t}}{\rm{.}}\;\;\;\;\;{g_j}(x,y) \ge 0,j = 1, \cdots ,{m_1},\\ \;\;\;\;\;\;\;\;{c_j}(x,y,w) = 0,j = 1, \cdots ,{m_2},\\ \;\;\;\;\;\;\;\;\phi ({y_j},{w_j},u) = 0,\quad j = 1, \cdots ,{m_2}, \end{array} $

(1.6)

其中$c_{j}(x, y, w)=w_{j}-F_{j}(x, y), j=1, \cdots, m_{2}$.当$u\rightarrow 0$, 由(1.2) 及(1.3), 易知问题$(NLP_{u})$(1.6) 是问题(MPEC)(1.1) 的光滑近似.

本文通过一个光滑函数$\phi(y_{j}, w_{j}, u)=-u \ln(e^{-\frac{y_{j}}{u}}+e^{-\frac{w_{j}}{u}})\in R$, 把问题(MPEC)(1.1) 转化为一带参数的一般优化问题, 基于文献[8]的思想, 提出了一个新的光滑QP-free算法.该算法具有如下优点:

(ⅰ)罚参数更新比文献[10]简单;

(ⅱ)在不要求Hessian阵估计正定的假设条件下, 算法仍具有超线性收敛性.

令$z=(x, y, w)$, $p=(x, y)$, $q=(y, w)$, $L_1=\{1, \cdots, m_{1}\}$, $L_2=\{1, \cdots, m_{2}\}$, 记$X$为问题(1.6) 的可行集, 即$X:=\{z:g_j(p)\geq 0, j\in L_1, c_j(z)=0, j\in L_2, \phi(q_j, u)=0, j\in L_2\}.$

类似文献[8], 将问题$(NLP_{u})(1.6)$转化为序列不等式约束优化问题$(NLP_{\rho})$:

$ \begin{array}{l} \min \;\;\;\;\;\;{f_\rho }(x,y,w)\\ {\rm{s}}{\rm{.t}}{\rm{.}}\;\;\;\;\;\;\;\;\;{g_j}(x,y) \ge 0,\;\;\;j \in {L_1},\\ \;\;\;\;\;\;\;\;\;\;\;\;\;{c_j}(x,y,w) \ge 0,\;\;j \in {L_2},\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\phi ({y_j},{w_j},u) \ge 0,\;\;j \in {L_2}, \end{array} $

(2.1)

其中$\rho=(\rho_1, \rho_2)$, $f_{\rho}(x, y, w)=f(x, y)+\rho_1\sum\limits_{j\in L_2 }c_{j}(x, y, w)+ \rho_2\sum\limits_{j\in L_2 }\phi(y_{j}, w_{j}, u)$, $c_{j}(x, y, w)=w_{j}-F_{j}(x, y), j\in L_2$.

研究问题$(NLP_{\rho})(2.1)$易知, $\rho$惩罚满足$c_{j}(x, y, w)> 0$, $j\in L_2$, $\phi(y_{j}, w_{j}, u)> 0$, $j\in L_2$的迭代, 而问题$(NLP_{\rho})(2.1)$的可行性能保证$c_{j}(x, y, w)\geq 0$, $j\in L_2$, $\phi(y_{j}, w_{j}, u)\geq 0$, $j\in L_2$.故$\rho$充分大, 能保证问题$(NLP_{u})(1.6)$的可行性.事实上, 当采用精确罚函数时, 无需$\rho$趋向无穷, 就能收敛到问题$(NLP_{u})(1.6)$的一解.

记${\rm{ }}\tilde {X}:=\{z:g_{j}(p)\geq 0, j\in L_1, \quad c_{j}(z)\geq 0, j\in L_2, \quad \phi(q_{j}, u)\geq 0, j\in L_2 \}, $同时, 记$I^{1}(p)$, $I^{2}(z)$, $I^{3}(q, u)$分别对应于$g$, $c$, $\phi$的积极集, 即

$ \begin{array}{l} {I^1}(p) = \{ j \in {L_1}:{g_j}(p) = 0\} ;{I^2}(z) = \{ j \in {L_2}:{c_j}(z) = 0\} ;\\ {I^3}(q,u) = \{ j \in {L_2}:\phi ({q_j},u) = 0\} . \end{array} $

为简化叙述, 记

$ \begin{array}{l} \nabla g_{j}(p) =\left( \begin{array}{c} \frac {\partial g_{j}(p)}{\partial y_{1}}, \cdots, \frac {\partial g_{j}(p)}{\partial y_{m_2}}, \frac {\partial g_{j}(p)}{\partial w_{1}}, \cdots, \frac {\partial g_{j}(p)}{\partial w_{m_2}}, \textbf{0} \end{array} \right)_{(n+2m_2)\times 1}^{T}, j\in L_1, \end{array} $

$ \begin{array}{l} \nabla c_{j}(z) =\left( \begin{array}{c} \frac {\partial c_{j}(z)}{\partial x_{1}}, \cdots, \frac {\partial c_{j}(z)}{\partial x_{n}}, \frac {\partial c_{j}(z)}{\partial y_{1}}, \cdots, \frac {\partial c_{j}(z)}{\partial y_{m_2}}, \frac {\partial c_{j}(z)}{\partial w_{1}}, \cdots, \frac {\partial c_{j}(z)}{\partial w_{m_2}} \end{array} \right)_{(n+2m_2)\times 1}^{T}, j\in L_2, \end{array} $

$ \begin{array}{l} \nabla \phi(q_{j}, u) =\left( \begin{array}{c} \textbf{0}, \frac {\partial \phi (q_{j}, u)}{\partial y_{1}}, \cdots, \frac {\partial \phi (q_{j}, u)}{\partial y_{m_2}}, \frac {\partial \phi (q_{j}, u)}{\partial w_{1}}, \cdots, \frac {\partial \phi (q_{j}, u)}{\partial w_{m_2}} \end{array} \right)_{(n+2m_2)\times 1}^{T}, j\in L_2. \end{array} $

首先, 给出如下三个基本假设:

H 2.1  问题(1.1)的可行域非空.

H 2.2  函数$f(p)$, $g_{j}(p), j\in L_1 $, $c_{j}(z), j\in L_2$, $\phi(q_{j}, u), j\in L_2$连续可微.

H 2.3  对任意的$z\in X$, (ⅰ)向量$\{ \nabla g_{j}(p)\mid j\in I^{1}(p) \}\cup \{ \nabla c_{j}(z)\mid j\in I^{2}(z) \}\cup \{ \nabla \phi(q_{j}, u)\mid j\in I^{3}(q, u) \} $线性无关; (ⅱ)若$z\notin X$, 则不存在常数$b_1> 0$, $b_2> 0$, 纯量$\beta^{1, j}\geq 0$, $ j\in I^{1}(p)$, $\beta^{2, j}\geq 0$, $j\in I^{2}(z)$, $\beta^{3, j}\geq 0$, $j\in I^{3}(q, u)$使得

$ \sum\limits_{j\in L_2 }b_1 \nabla c_{j}(z)+ \sum\limits_{j\in L_2 } b_2 \nabla \phi(q_{j}, u)= \sum\limits_{j\in I^{1}(p) } \beta^{1, j} \nabla g_{j}(p)+ \sum\limits_{j\in I^{2}(z) } \beta^{2, j} \nabla c_{j}(z) \\ \hspace{8.2cm} + \sum\limits_{j\in I^{3}(q, u) }\beta^{3, j} \nabla \phi(q_{j}, u). $

(2.2)

假设条件H 2.3 (ⅱ)用于证明(2.14) 方程中系数矩阵非奇异.

在算法前, 先研究问题$(NLP_{u})(1.6)$与问题$(NLP_{\rho})(2.1)$的关系.

$z$称为问题$(NLP_{u})(1.6)$的一K-T点, 若存在乘子$\lambda^{1}\in R^{m_1}$, $\lambda^{2}, \lambda^{3}\in R^{m_2}$满足

$ h(p)-A(p)^{T}\lambda^{1}-B(z)^{T}\lambda^{2}-T(q, u)^{T}\lambda^{3}=\textbf{0}, $

(2.3)

$ g(p)\geq 0, \quad c(z)=0, \quad \phi(q, u)=0, $

(2.4)

$ \lambda^{1, j} g_{j}(p)=0, \quad j\in L_1, $

(2.5)

$ \lambda^{1}\geq 0, $

(2.6)

其中

$ h(p)= \left( \begin{array}{c} \nabla_{x}f(x, y), \nabla_{y}f(x, y), \textbf{0} \end{array} \right)_{(n+2m_2)\times 1}^{T}, $

$ \begin{array}{l} A{(p)^T} = \left( \begin{array}{l} \frac{{\partial {g_1}(p)}}{{\partial {x_1}}}\;\;\;\;\; \cdots \;\;\;\;\;\frac{{\partial {g_{{m_1}}}(p)}}{{\partial {x_1}}}\\ \;\;\;\;\; \vdots \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \vdots \\ \frac{{\partial {g_1}(p)}}{{\partial {x_n}}}\;\;\;\;\; \cdots \;\;\;\;\;\frac{{\partial {g_{{m_1}}}(p)}}{{\partial {x_n}}}\\ \frac{{\partial {g_1}(p)}}{{\partial {y_1}}}\;\;\;\;\; \cdots \;\;\;\;\;\frac{{\partial {g_{{m_1}}}(p)}}{{\partial {y_1}}}\\ \;\;\;\;\; \vdots \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \vdots \\ \frac{{\partial {g_1}(p)}}{{\partial {y_{{m_2}}}}}\;\;\;\;\; \cdots \;\;\;\;\;\frac{{\partial {g_{{m_1}}}(p)}}{{\partial {y_{{m_2}}}}}\\ \;\;\;\;{\bf{0}}\;\;\;\;\;\;\;\;\;\; \cdots \;\;\;\;\;\;\;\;\;\;\;{\bf{0}} \end{array} \right),B{(z)^T} = \left( \begin{array}{l} \frac{{\partial {c_1}(z)}}{{\partial {x_1}}}\;\;\;\;\; \cdots \;\;\;\;\;\frac{{\partial {c_{{m_2}}}(z)}}{{\partial {x_1}}}\\ \;\;\;\;\; \vdots \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \vdots \\ \frac{{\partial {c_1}(z)}}{{\partial {x_n}}}\;\;\;\;\;\;\;\;\;\;\;\;\;\frac{{\partial {c_{{m_2}}}(z)}}{{\partial {x_n}}}\\ \frac{{\partial {c_1}(z)}}{{\partial {y_1}}}\;\;\;\;\; \cdots \;\;\;\;\;\frac{{\partial {c_{{m_2}}}(z)}}{{\partial {y_1}}}\\ \;\;\;\;\; \vdots \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \vdots \\ \frac{{\partial {c_1}(z)}}{{\partial {y_{{m_2}}}}}\;\;\;\;\; \cdots \;\;\;\;\;\frac{{\partial {c_{{m_2}}}(z)}}{{\partial {y_{{m_2}}}}}\\ \frac{{\partial {c_1}(z)}}{{\partial {w_1}}}\;\;\;\;\;\;\;\;\;\;\;\;\;\frac{{\partial {c_{{m_2}}}(z)}}{{\partial {w_1}}}\\ \;\;\;\;\; \vdots \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \vdots \\ \frac{{\partial {c_1}(z)}}{{\partial {w_{{m_2}}}}}\;\;\;\;\;\;\;\;\;\;\;\;\;\;\frac{{\partial {c_{{m_2}}}(z)}}{{\partial {w_{{m_2}}}}} \end{array} \right)\\ T{(q,u)^T} = \left( {\begin{array}{*{20}{c}} {{\bf{0}},diag\left( {\frac{{\partial \phi ({q_j},u)}}{{\partial {y_j}}},j \in {L_2}} \right),diag\left( {\frac{{\partial \phi ({q_j},u)}}{{\partial {w_j}}},j \in {L_2}} \right)} \end{array}} \right)_{(n + 2{m_2}) \times {m_2}}^T. \end{array} $

若存在乘子$\lambda^{1}\in R^{m_1}$, $\lambda^{2}, \lambda^{3}\in R^{m_2}$使得(2.3)-(2.5) 成立, 则$z$称为问题$(NLP_{u})(1.6)$的稳定点.

下面, 对给定的$\rho=(\rho_1, \rho_1)$, $z\in{\rm{ }}\tilde{X}$称为问题$(NLP_{\rho})$(2.1) 的一K-T点, 若存在乘子$\lambda^{1}\in R^{m_1}$, $\lambda^{2}, \lambda^{3}\in R^{m_2}$, 使得

$ h(p)+B(z)^{T}(\rho_{1}e)+T(q, u)^{T}(\rho_{2}e) -A(p)^{T}\lambda^{1}-B(z)^{T}\lambda^{2}-T(q, u)^{T}\lambda^{3}=\textbf{0}, $

(2.7)

$ g(p)\geq 0, \quad c(z)\geq 0, \quad \phi(q, u)\geq 0, $

(2.8)

$ \lambda^{1, j} g_{j}(p)=0, j\in L_1, \quad \lambda^{2, j} c_{j}(z)=0, j\in L_2, \quad \lambda^{3, j} \phi(q_{j}, u)=0, j\in L_2, $

(2.9)

$ \lambda^{1}\geq 0, \quad \lambda^{2}\geq 0, \quad \lambda^{3}\geq 0, $

(2.10)

其中$ e=( \begin{array}{c} { 1}, {\cdots}, {1} \end{array} )^{T} \in R^{m_2} $.若存在乘子$\lambda^{1}\in R^{m_1}$, $\lambda^{2}, \lambda^{3}\in R^{m_2}$使得(2.7)-(2.9) 成立, 则$z$称为问题$(NLP_{\rho})$(2.1) 的一稳定点.

记$\mu=(\mu^{1}, \mu^{2}, \mu^{3})$, 则$(NLP_{\rho})(2.1)$的对数障碍函数如下:

$ \begin{array}{l} \beta(z, u, \rho, \mu)=f(p)+\rho_1\sum\limits_{j\in L_2 }c_{j}(z)+ \rho_2\sum\limits_{j\in L_2 }\phi(q_{j}, u)\\ \hspace{3.0cm}-\sum\limits_{j\in L_1 } \mu^{1, j} \ln(g_{j}(p))- \sum\limits_{j\in L_2} \mu^{2, j} \ln(c_{j}(z))- \sum\limits_{j\in L_2 } \mu^{3, j} \ln(\phi(q_{j}, u)) , \end{array} $

其中$\mu^{1}>0\in R^{m_1}$, $\mu^{2}, \mu^{3}>0\in R^{m_2}$, 其梯度为:

$ \begin{array}{l} \bigtriangledown_{z} \beta(z, u, \rho, \mu)= h(p)+B(z)^{T}(\rho_{1}e)+T(q, u)^{T}(\rho_{2}e)\\ \hspace{3.3cm}-A(p)^{T}G(p)^{-1}\mu^{1} -B(z)^{T}C(z)^{-1}\mu^{2} -T(q, u)^{T} \Phi (q, u)^{-1} \mu^{3}, \end{array} $

(2.11)

其中$G(p)=diag(g_{j}(p), j\in L_1)$, $C(z)=diag(c_{j}(z), j\in L_2)$, $\Phi (q, u)=diag(\phi(q_{j}, u), j\in L_2)$.

问题$(NLP_{\rho})(2.1)$能通过$\min\beta(z, u, \rho, \mu)$, $\mu\rightarrow 0$求解.由(2.11), 令$\lambda=(\lambda^1, \lambda^2, \lambda^3)$, 定义$\lambda^1=G(p)^{-1}\mu^{1}$, $\lambda^2=C(z)^{-1}\mu^{2}$, $\lambda^3=\Phi (q, u)^{-1} \mu^{3}$, 能视为与$(NLP_{\rho})(2.1)$的解有关的K-T乘子, 等式(2.11) 的右边为$(NLP_{\rho})(2.1)$拉格朗日函数的梯度在$(z, \lambda^1, \lambda^2, \lambda^3)$处的值.

由对偶内点法的思想, 求解下列关于$(z, \lambda)$的非线性系统, $\lambda=(\lambda^1, \lambda^2, \lambda^3)$:

$ h(p)-A(p)^{T}\lambda^{1}-B(z)^{T}(\lambda^{2}-\rho_{1}e) -T(q, u)^{T}(\lambda^{3}-\rho_{2}e)=\textbf{0}, $

(2.12)

$ \mu^{1}-G(p)\lambda^1=0, \mu^{2}-C(z)\lambda^2=0, \mu^{3}-\Phi (q, u)\lambda^3=0, $

(2.13)

该非线性系统由拟牛顿迭代求解, $\mu=(\mu^{1}, \mu^{2}, \mu^{3})$:

$ \begin{array}{l} {\bf{N}}\left( {{\bf{z}},\lambda ,{\bf{H}},{\bf{u}},\rho ,\mu } \right){\bf{:}}\left( \begin{array}{l} \;\;\; - H\;\;\;\;\;A{(p)^T}\;\;B{(z)^T}\;\;T{(q,u)^T}\\ {Y^1}A(p)\;\;\;G(p)\;\;\;\;\;\;{\bf{0}}\;\;\;\;\;\;\;\;\;\;{\bf{0}}\\ {Y^2}B(z)\;\;\;\;\;{\bf{0}}\;\;\;\;\;\;\;\;\;C(z)\;\;\;\;\;\;\;{\bf{0}}\\ {Y^3}T(q,u)\;\;{\bf{0}}\;\;\;\;\;\;\;\;\;\;{\bf{0}}\;\;\;\;\;\;\Phi (q,u) \end{array} \right)\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{\rm{ = }}\left( \begin{array}{l} h(p) - A{(p)^T}{\lambda ^1} - B{(z)^T}({\lambda ^2} - {\rho _1}e) - T{(q,u)^T}({\lambda ^3} - {\rho _2}e)\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{\mu ^1} - G(p){\lambda ^1}\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{\mu ^2} - C(z){\lambda ^2}\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{\mu ^3} - \Phi (q,u){\lambda ^3} \end{array} \right) \end{array} $

(2.14)

其中$Y^{1}=diag(\lambda^{1, j}, j\in L_1)$, $Y^{2}=diag(\lambda^{2, j}, j\in L_2)$, $Y^{3}=diag(\lambda^{3, j}, j\in L_2)$, $H$为$(NLP_{\rho})(2.1)$拉格朗日函数Hessian阵的近似.

算法基于文献[9]的内点法思想求解问题$(NLP_{\rho})(2.1)$, 对固定的$\rho> 0$.关键技术是如何调整$\rho$, 使得迭代渐近满足$c(z)=0$, $\phi(q, u)=0$, 算法用了一个比文献[10]更为简单的更新准则.当等式约束违反时, $\rho> 0$应增加, 但当$\rho> 0$不受控制地增加时, 可能达不到问题$(NLP_{\rho})(2.1)$的K-T点.为防止这种现象, 要求下列三个条件成立($r_1, r_2, r_3 $为正数):

(ⅰ) $ \left\| \Delta z^{k}_{0} \right\| \leq r_1 $, 表明对问题$(NLP_{\rho_k})(2.1)$稳定点的逼近;

(ⅱ) $\lambda^2_{k}+\Delta \lambda^{2}_{0, k} \ngeq r_{2}e$, $\lambda^3_{k}+\Delta \lambda^{3}_{0, k} \ngeq r_{2}e$, 即在极限点处, 并不是所有的$c_{j}(z)$, $\phi(q_{j}, u)$都成为积极约束;

(ⅲ) $\lambda^1_{k}+\Delta \lambda^{1}_{0, k}\geq r_{3}e$, $\lambda^2_{k}+\Delta \lambda^{2}_{0, k}\geq r_{3}e$, $\lambda^3_{k}+\Delta \lambda^{3}_{0, k}\geq r_{3}e$, 即当$\rho_{k}$增加得非常快时, $\lambda^1_{k}$, $\lambda^2_{k}$或$\lambda^3_{k}$没有分量趋向于$-\infty$.

算法2.1

步骤0  初始化:

给定$z^0\in {\rm{ }}\tilde{X}_0$, $u_0> 0$, $\rho_0> 0$, $\lambda^{1, j}_{0}\in (0, t_{\max}]$, $j\in L_1 $, $\lambda^{2, j}_{0}, \lambda^{3, j}_{0}\in (0, t_{\max}]$, $j\in L_2 $, $H_0\in R^{(n+2m_2)\times (n+2m_2)}$为一对称正定阵.选取参数$\xi\in (0, \frac{1}{2})$, % $\beta\in (0, 1)$ $\eta_1\in (0, 1]$, $\eta_2\in (0, 1]$, $\eta_3\in (0, 1]$, $r_1> 0$, $r_2> 0$, $r_3> 0$, $\nu> 2$, $\theta \in (0, 1)$, $\delta> 1$, $\varrho\in (0, 1)$, $\tau \in (2, 3) $ $\kappa \in (0, 1)$, $l \in (0, 1)$, $t_{\max} > 0$.令$k=0$.

步骤1  通过求解N($z^{k}$, $\lambda_{k}$, $H_{k}$, $u_{k}$, $\rho_{k}$, 0)}计算$(\Delta z^{k}_{0}, \Delta \lambda^{1}_{0, k}, \Delta \lambda^{2}_{0, k}, \Delta\lambda^{3}_{0, k})$.

若$\Delta z^{k}_{0}=0$, $u_{k}<\varepsilon$, 算法停止!否则令$u_{k}=\frac{1}{2}u_{k}$, 转步步骤2.

步骤2   考察上面提到的三个条件:若三个条件同时成立, 则令$\rho_{k+1}=\delta\rho_{k}$, $z^{k+1}=z^{k}$, $\lambda^{1}_{k+1}=\lambda^{1}_{k}$, $\lambda^{2}_{k+1}=\lambda^{2}_{k}$, $\lambda^{3}_{k+1}=\lambda^{3}_{k}$, $H_{k+1}=H_{k}$, 置$k=k+1$, 转步骤1.否则, 转步骤3.

步骤3   通过求解 $\textbf{N}(z^{k}, \lambda_{k}, H_{k}, u_{k}, \rho_{k}, \mu_k)$ 计算 $(\Delta z^{k}_{1}, \Delta \lambda^{1}_{1,k}, \Delta \lambda^{2}_{1,k}, \Delta\lambda^{3}_{1,k})$,其中 $ \mu_k=(\mu^{1}_k, \mu^{2}_k, \mu^{3}_k) =(\left\| \Delta z^{k}_{0} \right\|^{\nu}\lambda^{1}_{k}, \left\| \Delta z^{k}_{0} \right\|^{\nu}\lambda^{2}_{k}, \left\| \Delta z^{k}_{0} \right\|^{\nu}\lambda^{3}_{k} )$.

步骤4  令

$ \Delta z^{k}=(1-\varphi_{k})\Delta z^{k}_{0} +\varphi_{k}\Delta z^{k}_{1}, \Delta \lambda^{1}_{k}= (1-\varphi_{k}) \Delta \lambda^{1}_{0, k} +\varphi_{k} \Delta \lambda^{1}_{1, k} , \\ \Delta \lambda^{2}_{k}= (1-\varphi_{k}) \Delta \lambda^{2}_{0, k} +\varphi_{k} \Delta \lambda^{2}_{1, k} , \Delta \lambda^{3}_{k}= (1-\varphi_{k}) \Delta \lambda^{3}_{0, k} +\varphi_{k} \Delta\lambda^{3}_{1, k} , $

(2.15)

$ {\varphi ^k} = \left\{ \begin{array}{l} 1,\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;若\nabla {f_{{\rho _k}}}{({z^k})^T}\Delta z_1^k \le \theta \nabla {f_{{\rho _k}}}{({z^k})^T}\Delta z_0^k,\\ (1 - \theta )\frac{{\nabla {f_{{\rho _k}}}{{({z^k})}^T}\Delta z_0^k}}{{\nabla {f_{{\rho _k}}}{{({z^k})}^T}(\Delta z_0^k - \Delta z_1^k)}},\;\;{否则} \end{array} \right. $

(2.16)

步骤5  令

$ I^1_{k}= \{j\in L_1:g_{j}(p^k)\leq \lambda^{1, j}_{k}+\Delta\lambda^{1, j}_{k} \}, I^2_{k}= \{j\in L_2:c_{j}(z^k)\leq \lambda^{2, j}_{k}+\Delta \lambda^{2, j}_{k} \}, \\ I^3_{k}= \{j\in L_2:\phi(q_{j}^k, u_k)\leq \lambda^{3, j}_{k}+\Delta \lambda^{3, j}_{k} \}, $

(2.17)

$ J^1_{k}= \{j\in L_1:\lambda^{1, j}_{k}+\Delta \lambda^{1, j}_{k} \leq -g_{j}(p^k) \}, J^2_{k}= \{j\in L_2:\lambda^{2, j}_{k}+\Delta\lambda^{2, j}_{k} \leq -c_{j}(z^k) \}, \\ J^3_{k}= \{j\in L_2:\lambda^{3, j}_{k}+\Delta \lambda^{3, j}_{k} \leq -\phi(q_{j}^k, u_k) \}. $

(2.18)

若$ J^1_{k}\cup J^2_{k}\cup J^3_{k}= \emptyset$, 通过求解下列最小二乘问题计算修正方向$\Delta{\rm{ }}\tilde{z}^k$:

$ \begin{array}{l} \min \;\;\;\;\frac{1}{2}\Delta {{\tilde z}^{kT}}{H_k}\Delta {{\tilde z}^k}\\ {\rm{s}}{\rm{.t}}{\rm{.}}\;\;\;\;\;\;{g_j}({p^k} + \Delta {p^k}) + \nabla {g_j}{({p^k})^T}\Delta {{\tilde p}^k} = {\psi _k},\;\;\forall j \in I_k^1,\\ \;\;\;\;\;\;\;\;\;{c_j}({z^k} + \Delta {z^k}) + \bigtriangledown{c_j}{({z^k})^T}\Delta {{\tilde z}^k} = {\psi _k},\;\;\;\;\forall j \in I_k^2,\\ \;\;\;\;\;\;\;\;\;\phi (q_j^k + \Delta q_j^k,{u_k}) + \nabla \phi {(q_j^k,{u_k})^T}\Delta \tilde q_j^k = {\psi _k},\;\;\;\forall j \in I_k^3, \end{array} $

(2.19)

其中

$ \begin{array}{l} \begin{array}{*{20}{l}} {\;\;\;\;\;{p^k} = ({x^k},{y^k}),\Delta {p^k} = (\Delta {x^k},\Delta {y^k}),\Delta {{\tilde p}^k} = (\Delta {{\tilde x}^k},\Delta {{\tilde y}^k}),} \end{array}\\ \;\;\;\;\;\begin{array}{*{20}{l}} {q_j^k = (y_j^k,w_j^k),\Delta q_j^k = (\Delta y_j^k,\Delta w_j^k),\Delta \widetilde {q_j^k} = (\Delta \tilde y_j^k,\Delta \tilde w_j^k),} \end{array}\\ \begin{array}{*{20}{l}} {{z^k} = ({x^k},{y^k},{w^k}),\Delta {z^k} = (\Delta {x^k},\Delta {y^k},\Delta {w^k}),\Delta {{\tilde z}^k} = (\Delta {{\tilde x}^k},\Delta {{\tilde y}^k},\Delta {{\tilde w}^k}),} \end{array}\\ {\psi _k} = \max \{ {\left\| {{z^k}} \right\|^\tau },\mathop {\max }\limits_{j \in I_k^1} {\left| {\frac{{\lambda _k^{1,j}}}{{\lambda _k^{1,j} + \Delta \lambda _k^{1,j}}} - 1} \right|^\kappa }{\left\| {\Delta {z^k}} \right\|^2},\mathop {\max }\limits_{j \in I_k^2} {\left| {\frac{{\lambda _k^{2,j}}}{{\lambda _k^{2,j} + \lambda _k^{2,j}}} - 1} \right|^\kappa }{\left\| {{z^k}} \right\|^2},\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\mathop {\max }\limits_{j \in I_k^3} {\left| {\frac{{\lambda _k^{3,j}}}{{\lambda _k^{3,j} + \lambda _k^{3,j}}} - 1} \right|^\kappa }{\left\| {{z^k}} \right\|^2}\} , \end{array} $

(2.20)

若$ J^1_{k}\cup J^2_{k}\cup J^3_{k}\neq \emptyset$或(2.19) 不可行或无界或$ \left\| \Delta {\rm{ }}\tilde{z}^{k} \right\| > \left\|\Delta z^{k} \right\|$, 置$\Delta {\rm{ }}\tilde{z}^{k}=0$.

步骤6  曲线搜索.计算$\left\{1, \varrho, \varrho^2, \ldots\right\}$中满足以下不等式

$ \label{b25} f_{\rho_k}(z^{k}+\alpha\Delta z^{k}+\alpha^2 \Delta{\rm{ }}\tilde{z}^{k}) \leq f_{\rho_k}(z^{k}) +\xi\alpha\nabla f_{\rho_k}(z^k)^{T}\Delta z^{k}, $

(2.21)

$ g_{j}(p^k+\alpha\Delta p^k+\alpha^2 \Delta {\rm{ }}\tilde{p}^{k}) \geq \eta_1 g_{j}(p^k), \quad \forall j\in J^1_{k}, $

(2.22)

$ c_{j}(z^k+\alpha\Delta z^k+\alpha^2\Delta {\rm{ }}\tilde{z}^{k}) \geq \eta_2 c_{j}(z^k), \quad \forall j\in J^2_{k}, $

(2.23)

$ \phi(q^k_j+\alpha\Delta q^k_j+\alpha^2 \Delta {\rm{ }}\tilde{q}^k_j, u_k) \geq \eta_3 \phi(q^k_j, u_k), \quad \forall j\in J^3_{k}, $

(2.24)

$ g_{j}(p^k+\alpha\Delta p^k+\alpha^2\Delta {\rm{ }}\tilde{p}^{k}) >0, \quad \forall j\in L_1, $

(2.25)

$ c_{j}(z^k+\alpha\Delta z^k+\alpha^2 \Delta {\rm{ }}\tilde{z}^{k}) >0, \quad \forall j\in L_2, $

(2.26)

$ \phi(q^k_j+\alpha\Delta q^k_j+\alpha^2 \Delta {\rm{ }}\tilde{q}^k_j, u_k) >0, \quad \forall j\in L_2. $

(2.27)

的最大值$\alpha_k$.

步骤7  更新.令$z^{k+1}=z^k+\alpha\Delta z^k+\alpha^2 \Delta{\rm{ }}\tilde{z}^{k}$.若$ J^1_{k}\cup J^2_{k}\cup J^3_{k}= \emptyset$, 置

$ \lambda^{1, j}_{k+1} =\min \{ \max\{\left\| \Delta z^{k} \right\|^{2}, \lambda^{1, j}_{k}+\Delta \lambda^{1, j}_{k}\}, t_{\max} \}, \quad j\in L_1, $

(2.28)

$ \lambda^{2, j}_{k+1} =\min \{ \max\{\left\| \Delta z^{k} \right\|^{2}, \lambda^{2, j}_{k}+\Delta \lambda^{2, j}_{k}\}, t_{\max} \}, \quad j\in L_2, $

(2.29)

$ \lambda^{3, j}_{k+1} =\min \{ \max\{\left\| \Delta z^{k} \right\|^{2}, \lambda^{3, j}_{k}+\Delta \lambda^{3, j}_{k}\}, t_{\max} \}, \quad j\in L_2; $

(2.30)

否则, 置$ \lambda^{1, j}_{k+1}= \lambda^{1, j}_{0}$, $j\in L_1$, $ \lambda^{2, j}_{k+1}= \lambda^{2, j}_{0}$, $j\in L_2$, $ \lambda^{3, j}_{k+1}= \lambda^{3, j}_{0}$, $j\in L_2$.令$\rho_{k+1}=\rho_{k}$, 更新$H_{k}$为对称正定阵.置$k=k+1$, 转步骤1.

本节首先讨论算法的全局收敛性, 先给出如下一较弱假设条件.

H 3.1  给定任意指标集$K$使得序列$\{z^{k}\}$有界, 且存在常数$\sigma_1$, $\sigma_2> 0$, 对任意$k\in K$满足: $ \left\| H_k \right\|\leq \sigma_2, $

$ v^{T} \bigg(H_k +\sum\limits_{j\in L_1} \frac{\lambda^{1, j}_{k}}{g_{j}(p^k)} \nabla g_{j}(p^k) \nabla g_{j}(p^k)^{T} +\sum\limits_{j\in L_2} \frac{\lambda^{2, j}_{k}}{c_{j}(z^k)} \nabla c_{j}(z^k) \nabla c_{j}(z^k)^{T}\\ \hspace{1.3cm} +\sum\limits_{j\in L_2} \frac{\lambda^{3, j}_{k}}{\phi(q^k_j, u_k)} \nabla\phi(q^k_j, u_k) \nabla \phi(q^k_j, u_k)^{T} \bigg)v \geq \sigma_1 \left\| v \right\|^2 , \quad \forall v\in R^n. $

引理3.1  搜索方向$\Delta z^{k}$满足

$ \nabla f_{\rho_k}(z^k)^{T}\Delta z^{k} \leq \theta \nabla f_{\rho_k}(z^k)^{T}\Delta z^{k}_{0} \leq -\sigma_1 \theta \left\| \Delta z^{k}_{0} \right\|^{2}, $

(3.1)

且

$ \nabla g_{j}(p^k)^{T} \Delta z^{k}>0, \forall j \in J^1_{k}, \nabla c_{j}(z^k)^{T} \Delta z^{k}>0, \forall j \in J^2_{k}, \nabla \phi(q^k_j, u_k)^{T} \Delta z^{k}>0, \forall j \in J^3_{k}. $

(3.2)

证明  由步骤1, 有

$ -H_{k} \Delta z^{k}_{0} + A(p^{k})^{T}\Delta \lambda^{1}_{0, k} + B(z^{k})^{T} \Delta \lambda^{2}_{0, k} + T(q^{k}, u_{k})^{T} \Delta\lambda^{3}_{0, k} = h(p^{k})-A(p^{k})^{T}\lambda^{1}_{k}\\ \hspace{4cm} -B(z^{k})^{T}(\lambda^{2}_{k}-\rho_{1, k}e) -T(q^{k}, u_{k})^{T}(\lambda^{3}_{k}-\rho_{2, k}e), $

(3.3)

$ Y^{1}_{k}A(p^{k}) \Delta z^{k}_{0} + G(p^{k}) \Delta \lambda^{1}_{0, k} =-G(p^{k}) \lambda^{1}_{k}, $

(3.4)

$ Y^{2}_{k} B(z^{k}) \Delta z^{k}_{0} +C(z^{k}) \Delta \lambda^{2}_{0, k} =-C(z^{k})\lambda^{2}_{k}, $

(3.5)

$ Y^{3}_{k} T(q^{k}, u_{k}) \Delta z^{k}_{0} +\Phi (q^{k}, u_{k})\Delta \lambda^{3}_{0, k} =-\Phi (q^{k}, u_{k})\lambda^{3}_{k}, $

(3.6)

令$S_{k}:= H_{k} +A(p^{k})^{T} G(p^{k})^{-1} Y^{1}_{k}A(p^{k}) +B(z^{k})^{T} C(z^{k})^{-1} Y^{2}_{k} B(z^{k}) +T(q^{k}, u_{k})^{T} \Phi (q^{k}, u_{k})^{-1} Y^{3}_{k} T(q^{k}, u_{k}), $故有

$ \nabla f_{\rho_k}(z^k)=-S_{k} \Delta z^{k}_{0}. $

而由假设H3.1, 有$ \nabla f_{\rho_k}(z^k)^{T} \Delta z^{k}_{0} =- (\Delta z^{k}_{0})^{T} S_{k} \Delta z^{k}_{0} \leq -\sigma_1 \left\| \Delta z^{k}_{0} \right\|^{2}. $

根据(2.16), 若$\nabla f_{\rho_k}(z^k)^{T}\Delta z^{k}_{1} \leq \theta \nabla f_{\rho_k}(z^k)^{T}\Delta z^{k}_{0}$, $\varphi_k=1$, 故

$ \Delta z^{k}=\Delta z^{k}_{1}, \quad \nabla f_{\rho_k}(z^k)^{T}\Delta z^{k} \leq \theta \nabla f_{\rho_k}(z^k)^{T}\Delta z^{k}_{0}. $

若$ \nabla f_{\rho_k}(z^k)^{T}\Delta z^{k}_{1} > \theta \nabla f_{\rho_k}(z^k)^{T}\Delta z^{k}_{0}$, 有

$ \begin{array}{l} \nabla f_{\rho_k}(z^k)^{T} \Delta z^{k} =(1-\varphi_{k}) \nabla f_{\rho_k}(z^k)^{T}\Delta z^{k}_{0} +\varphi_{k} \nabla f_{\rho_k}(z^k)^{T}\Delta z^{k}_{1} = \theta \nabla f_{\rho_k}(z^k)^{T}\Delta z^{k}_{0}, \end{array} $

故(3.1) 式成立.而由步骤3, 有

$ -H_{k} \Delta z^{k}_{1} + A(p^{k})^{T}\Delta \lambda^{1}_{1, k} + B(z^{k})^{T} \Delta \lambda^{2}_{1, k} + T(q^{k}, u_{k})^{T} \Delta\lambda^{3}_{1, k} = h(p^{k})-A(p^{k})^{T}\lambda^{1}_{k}\\ \hspace{4cm} -B(z^{k})^{T}(\lambda^{2}_{k}-\rho_{1, k}e) -T(q^{k}, u_{k})^{T}(\lambda^{3}_{k}-\rho_{2, k}e), $

(3.7)

$ Y^{1}_{k}A(p^{k}) \Delta z^{k}_{1} + G(p^{k}) \Delta \lambda^{1}_{1, k} =\left\| \Delta z^{k}_{0} \right\|^{\nu}\lambda^{1}_{k}-G(p^{k}) \lambda^{1}_{k}, $

(3.8)

$ Y^{2}_{k} B(z^{k}) \Delta z^{k}_{1} +C(z^{k}) \Delta \lambda^{2}_{1, k} =\left\| \Delta z^{k}_{0} \right\|^{\nu}\lambda^{2}_{k}-C(z^{k})\lambda^{2}_{k}, $

(3.9)

$ Y^{3}_{k} T(q^{k}, u_{k}) \Delta z^{k}_{1} +\Phi (q^{k}, u_{k})\Delta \lambda^{3}_{1, k} =\left\| \Delta z^{k}_{0} \right\|^{\nu}\lambda^{3}_{k}-\Phi (q^{k}, u_{k})\lambda^{3}_{k}, $

(3.10)

又由(2.18), $\forall j\in J^{1}_k $, $\lambda^{1, j}_{k}+\Delta \lambda^{1, j}_{k} \leq -g_{j}(p^k)$, 则有

$ \begin{array}{l} \nabla g_{j}(p^k)^{T} \Delta z^{k}= -\frac{(\Delta \lambda^{1, j}_{k}+ \lambda^{1, j}_{k}) g_{j}(p^k)}{ \lambda^{1, j}_{k}} +\left\| \Delta z^{k}_{0} \right\|^{\nu} \varphi_{k} \geq \frac{g_{j}^2(p^k)}{\lambda^{1, j}_{k}} +\left\| \Delta z^{k}_{0} \right\|^{\nu} \varphi_{k} >0. \end{array} $

类似如上分析, 有$ \nabla c_{j}(z^k)^{T} \Delta z^{k}>0, \forall j \in J^2_{k}, \quad \nabla \phi(q^k_j, u_k)^{T} \Delta z^{k}>0, \forall j \in J^3_{k}, $故(3.2) 式成立.

H 3.2  序列$\{ z^k \}$的一聚点$z^{*}$为问题$(NLP_{\bar \rho})(2.1)$的一孤立K-T点, 且在$z^{*}$处: (ⅰ)严格互补条件成立; (ⅱ)乘子$\lambda^1_{*}$, $\lambda^2_{*}$, $\lambda^3_{*}$满足$\lambda^{1, j}_{*}\leq t_{\max}$, $j\in L_1$, $\lambda^{2, j}_{*}, \lambda^{3, j}_{*}\leq t_{\max}$, $j\in L_2$.

命题3.1  若假设H 2.1-H 3.2成立, 由算法产生的无穷序列$\{ z^k \}$有界, 则$\{ z^k \}$收敛到问题$(NLP_{\bar \rho})(2.1)$的一K-T点$z^{*}$.且对$k\rightarrow \infty$, 有

(ⅰ) $ \{\Delta z^{k} \}\rightarrow 0 $, $\{\lambda^1_{k}+\Delta \lambda^1_{k}\}\rightarrow \lambda^1_{*}$, $\{\lambda^2_{k}+\Delta \lambda^2_{k}\}\rightarrow \lambda^2_{*}$, $\{\lambda^3_{k}+\Delta \lambda^3_{k}\}\rightarrow \lambda^3_{*}$;

(ⅱ) $J^1_{k}=J^2_{k}=J^3_{k}=\emptyset$, $I^1_{k}=I^1(p^*)$, $I^2_{k}=I^2(z^*)$, $I^3_{k}=I^3(q^*, 0)$;

(ⅲ) $\{\lambda^1_{k}\}\rightarrow \lambda^1_{*}$, $\{\lambda^2_{k}\}\rightarrow \lambda^2_{*}$, $\{\lambda^3_{k}\}\rightarrow \lambda^3_{*}$.

证明  证明类似文献[9]中命题4.2的证明.

定理3.1  若假设H2.1-H 3.2成立, 算法产生一无穷序列$\{ z^k \}$, 在$\{ z^k \}$的任一聚点$z^*$处非退化条件成立: $(y^*_{j}, w^*_{j})\neq (0, 0)$, $j\in L_2$, 则$z^*$为问题$(MPEC)(1.1)$的一稳定点.

证明  由命题3.1及(1.3), 有

$ h(p^{*}) -A(p^{*})^{T}\lambda ^1_{*} -B(z^{*})^{T} (\lambda^2_{*}-\overline{\rho}_1e) -T(q_j^{*}, 0)^{T} (\lambda^3_{*}-\overline{\rho}_2e) =0, \\ {\lambda}^{1, j}_{*} g_{j}(p^{*})=0, j\in L_1, \phi(q_j^{*}, 0)=\min\{y^*_{j}, w^*_{j}\}=0, j\in L_2. $

(3.11)

记$I_{y^*}(z^{*})=\{j\in L_2| w^*_{j}> 0 =y^*_{j}\}$, $I_{w^*}(z^{*})=\{j\in L_2| y^*_{j}> 0 =w^*_{j}\}$, 令

$ {\bar \pi ^*} = \left\{ \begin{array}{l} \frac{{\lambda _*^3 - {{\bar \rho }_2}e}}{{w_j^*}},j \in {I_{{y^*}}}({z^*}),\\ \frac{{\lambda _*^3 - {{\bar \rho }_2}e}}{{y_j^*}},j \in {I_{{w^*}}}({z^*}). \end{array} \right. $

根据(3.11) 及(1.2), 有

$ \begin{array}{l} h(p^{*}) -A(p^{*})^{T}\lambda ^1_{*} -B(z^{*})^{T} s^{*} -V(q^{*})^{T} \overline{\pi}^* =0, \\ {\lambda}^{1, j}_{*} g_{j}(p^{*})=0, j\in L_1, 0 \leq y^*_{j}\perp w^*_{j} \geq 0, j\in L_2, \end{array} $

其中$V(q^{*})=(0, diag(w^*_{j}), diag(y^*_{j}))$, $j\in L_2$, $w^*_{j}=F_j(x^*, y^*)$, $j\in L_2$, 这表明$z^{*}$是问题$(MPEC)(1.1)$的一稳定点.

记$\lambda^1_{*}$, $s^{*}$, $\pi^{*}$是与$z^{*}$有关的问题$(NLP_u)(1.6)$的K-T乘子, 其中$s^{*}=\lambda^2_{*}-\overline{\rho}_1e$, $\pi^{*}=\lambda^3_{*}-\overline{\rho}_2e$.$(NLP_u)(1.6)$的拉格朗日函数如下:

$ L(z, \lambda^1, s, \pi)= f(x, y)-\lambda^{1T} g(p) - s^T c(z)- \pi^T \phi(q, u), $

对应的乘子为$\lambda^{1}$, $s=\lambda^2-\rho_1 e$, $\pi=\lambda^3-\rho_2 e$, 与$(NLP_\rho)(2.1)$的拉格朗日函数相同, 即,

$ \begin{array}{l} L_\rho(z, \lambda^1, \lambda^2, \lambda^3)= f(x, y) + \rho_1\sum\limits_{j\in L_2 }c_{j}(z) +\rho_2\sum\limits_{j\in L_2 }\phi(q_{j}, u) -\lambda^{1T} g(p) - \lambda^{2T} c(z)- \lambda^{3T} \phi(q, u). \end{array} $

为证明算法的超线性收敛性, 另作如下假设:

H3.3  函数$f(p)$, $g_j(p)$, $j\in L_1$, $c_j(z), \phi(q_{j}, u)$, $j\in L_2$, 三阶连续可微; 在$z^{*}$处二阶充分性条件成立, 即$\nabla_{zz}^2 L(z^{*}, \lambda^1_{*}, s^{*}, \pi^{*})$在如下空间上正定:

$ \begin{array}{l} \{ v\in R^{n+2m_2} | \nabla g_{j}(p^{*})^{T} v=0, j\in L_1, \nabla c_{j}(z^{*})^{T} v=0, j\in L_2, \nabla \phi(q_j^{*}, 0)^{T} v=0, j\in L_2 \}. \end{array} $

H3.4  矩阵序列$\{H_k\}$满足

$ \begin{array}{l} \left\| P_k (H_k-\nabla_{zz}^2 L(z^{*}, \lambda^1_{*}, s^{*}, \pi^{*})) \Delta z^k \right\| =o( \left\| \Delta z^{k} \right\|), \end{array} $

其中$P_k =I_{n+2m_2}-R_k(R_k^T R_k)^{-1}R_k^T$, $ R_k= [ \nabla g_{j}(p^{k}), j\in I^1({p^*}), \nabla c_{j}(z^{k}), j\in I^2({z^*}), \nabla \phi(q_j^{k}, u_{k}), j\in I^3({q^*}, 0) ] \in R^{(n+2m_2)\times (|I^1({p^*})|+|I^2({z^*})|+|I^3({q^*}, 0)|)}.$

引理3.2  当$k$充分大时, $z^{k+1}=z^k+\Delta z^k+ \Delta{\rm{ }}\tilde{z}^{k}$, 即步长$\alpha_k\equiv 1$.

证明  当$k$充分大时, 由命题3.1(ⅱ)知, $J^1_k=J^2_k=J^3_k=\emptyset$, 即只需证

(ⅰ) $ f_{\rho_k}(z^{k}+\Delta z^{k}+ \Delta{\rm{ }}\tilde{z}^{k}) \leq f_{\rho_k}(z^{k}) +\xi\nabla f_{\rho_k}(z^k)^{T}\Delta z^{k}, $

(ⅱ) $ g_{j}(p^k+\Delta p^k+\Delta {\rm{ }}\tilde{p}^{k}) >0, \forall j\in L_1, $\quad $ c_{j}(z^k+\Delta z^k+ \Delta {\rm{ }}\tilde{z}^{k}) >0, \forall j\in L_2, $ $\phi(q^k_j+\Delta q^k_j+ \Delta {\rm{ }}\tilde{q}^k_j, u_k) >0, \forall j\in L_2.$

首先证(ⅰ)成立.根据假设H3.3, 有

$ f_{\rho_k}(z^{k}+\Delta z^{k}+ \Delta{\rm{ }}\tilde{z}^{k}) = f_{\rho_k}(z^{k}) +\nabla f_{\rho_k}(z^{k})^{T} (\Delta z^{k}+ \Delta{\rm{ }}\tilde{z}^{k}) +\frac{1}{2} \Delta z^{kT} \nabla^2_{zz} f_{\rho_k}(z^{k}) \Delta z^{k}\\ \hspace{9cm} + o( \left\|\Delta z^{k}\right\|^2). $

(3.12)

定义$ \lambda^{\prime 1, j}_{k}=\lambda^{1, j}_{k}+\Delta\lambda^{1, j}_{k}, j\in L_1, \lambda^{\prime 2, j}_{k}=\lambda^{2, j}_{k}+\Delta\lambda^{2, j}_{k}, j\in L_2, \lambda^{\prime 3, j}_{k}=\lambda^{3, j}_{k}+\Delta\lambda^{3, j}_{k}, j\in L_2, $

$ \nabla f_{\rho_k}(z^{k})^{T} \Delta z^{k} =-\Delta z^{kT} H_k \Delta z^{k} +\sum\limits_{j\in L_1} \lambda^{\prime 1, j}_{k} \nabla g_{j}(p^{k})^{T}\Delta {p}^{k} +\sum\limits_{j\in L_2} \lambda^{\prime 2, j}_{k} \nabla c_{j}(z^{k})^{T} \Delta {z}^{k}\\ \hspace{8cm} +\sum\limits_{j\in L_2} \lambda^{\prime 3, j}_{k} \nabla \phi(q_j^{k}, u_{k})^{T} \Delta {q}_j^{k}, $

(3.13)

$ \nabla f_{\rho_k}(z^{k})^{T} \Delta {\rm{ }}\tilde{z}^{k} = \sum\limits_{j\in L_1} \lambda^{\prime 1, j}_{k} \nabla g_{j}(p^{k})^{T}\Delta {\rm{ }}\tilde{p}^{k} +\sum\limits_{j\in L_2} \lambda^{\prime 2, j}_{k} \nabla c_{j}(z^{k})^{T} \Delta {\rm{ }}\tilde{z}^{k} +\sum\limits_{j\in L_2} \lambda^{\prime 3, j}_{k} \nabla \phi(q_j^{k}, u_{k})^{T} \Delta {\rm{ }}\tilde{q}_j^{k}. $

(3.14)

由(3.13) 及(3.14), (3.12) 可写为:

$ f_{\rho_k}(z^{k}+\Delta z^{k}+ \Delta{\rm{ }}\tilde{z}^{k}) =f_{\rho_k}(z^{k})-\frac{1}{2}\Delta z^{kT} H_k \Delta z^{k} +\frac{1}{2}\sum\limits_{j\in L_1} \lambda^{\prime 1, j}_{k} \nabla g_{j}(p^{k})^{T}\Delta {p}^{k}\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;+\frac{1}{2}\sum\limits_{j\in L_2} \lambda^{\prime 2, j}_{k} \nabla c_{j}(z^{k})^{T} \Delta {z}^{k} +\frac{1}{2}\sum\limits_{j\in L_2} \lambda^{\prime 3, j}_{k} \nabla \phi(q_j^{k}, u_{k})^{T} \Delta {q}_j^{k}\\ \;\;\;\;\;\;\;\;\;\; \;\;\;\;\;\;\;\;\;\; \;\;\;\;\;\;\;\;\;\;+\frac{1}{2}\Delta z^{kT}(\nabla^2_{zz} f_{\rho_k}(z^{k})-H_k) \Delta z^{k} + o( \left\|\Delta z^{k}\right\|^2) +E^1_{k} +E^2_{k} +E^3_{k}, $

(3.15)

其中$E^1_{k}=\frac{1}{2}\sum\limits_{j\in L_1}\lambda^{\prime1, j}_{k} \nabla g_{j}(p^{k})^{T}\Delta {p}^{k} +\sum\limits_{j\in L_1}\lambda^{\prime1, j}_{k} \nabla g_{j}(p^{k})^{T}\Delta {\rm{ }}\tilde{p}^{k} $, $E^2_{k}=\frac{1}{2}\sum\limits_{j\in L_2} \lambda^{\prime 2, j}_{k} \nabla c_{j}(z^{k})^{T} \Delta {z}^{k} +\sum\limits_{j\in L_2} \lambda^{\prime 2, j}_{k} \nabla c_{j}(z^{k})^{T} \Delta {\rm{ }}\tilde{z}^{k} $, $E^3_{k}=\frac{1}{2}\sum\limits_{j\in L_2} \lambda^{\prime 3, j}_{k} \nabla \phi(q_j^{k}, u_{k})^{T} \Delta {q}_j^{k} +\sum\limits_{j\in L_2} \lambda^{\prime 3, j}_{k} \nabla \phi(q_j^{k}, u_{k})^{T} \Delta {\rm{ }}\tilde{q}_j^{k} $.

$ E^1_{k}=\sum\limits_{j\in I^1({p^*})} [\frac{ \frac{1}{2}(\lambda^{\prime 1, j}_{k})^2}{{\lambda^{ 1, j}_{k}}}-\lambda^{\prime 1, j}_{k}] g_{j}(p^{k}) -\frac{1}{2}\sum\limits_{j\notin I^1({p^*})} \frac{ (\lambda^{\prime 1, j}_{k})^2}{{\lambda^{ 1, j}_{k}}} g_{j}(p^{k})\\ \hspace{4.5cm} -\frac{1}{2}\sum\limits_{j\in L_1} \lambda^{\prime 1, j}_{k} \Delta {p}^{kT} \nabla^2_{zz}g_{j}(p^{k}) \Delta {p}^{k} +o(\left\|\Delta z^{k}\right\|^2). $

(3.16)

$ E^2_{k}, E^3_{k}$形式类似$ E^1_{k}$.

又由于假设H 3.4, 有

$ f_{\rho_k}(z^{k}+\Delta z^{k}+ \Delta{\rm{ }}\tilde{z}^{k}) \leq f_{\rho_k}(z^{k})+\frac{1}{2} \nabla f_{\rho_k}(z^{k})^{T} \Delta z^{k} +o(\left\|\Delta z^{k}\right\|^2). $

又$ \nabla f_{\rho_k}(z^{k})^{T} \Delta z^{k} \leq -\sigma_1 \theta \left\| \Delta z^{k}_{0} \right\|^{2} +o(\left\|\Delta z^{k}\right\|^2) $, 因$0 < \xi < \frac{1}{2}$, 故(ⅰ)成立.

下证(ⅱ)成立.对$j\notin I^1({p^*})$, 因$\{\Delta z^k\}$, $\{\Delta {\rm{ }}\tilde{z}^k\}$都收敛到0, 故$ g_{j}(p^k+\Delta p^k+\Delta {\rm{ }}\tilde{p}^{k})>0$.考虑$j\in I^1({p^*})$, 有

$ \begin{array}{l} g_{j}(p^k+\Delta p^k+\Delta {\rm{ }}\tilde{p}^{k}) = g_{j}(p^k+\Delta p^k) +\nabla g_{j}(p^k+\Delta p^k)^{T} \Delta {\rm{ }}\tilde{p}^{k} +O(\left\|\Delta z^{k}\right\|^2)\\ \hspace{3.2cm} =g_{j}(p^k+\Delta p^k) +\nabla g_{j}(p^k)^{T} \Delta {\rm{ }}\tilde{p}^{k} +O(\left\|\Delta z^{k}\right\| \left\|\Delta{\rm{ }}\tilde{ z}^{k}\right\| ), \end{array} $

故

$ g_{j}(p^k+\Delta p^k+\Delta {\rm{ }}\tilde{p}^{k}) =\psi_k+O \bigg( \max \bigg \{ \left\| \Delta z^{k} \right\|^{3}, \max\limits_{j\in I^1({p^*})\atop} \left| \frac{\lambda^{1, j}_{k}}{\lambda^{1, j}_{k}+\Delta \lambda^{1, j}_{k}}-1 \right| \left\|\Delta z^{k} \right\|^2, \\ \hspace{2cm} \max\limits_{j\in I^2({z^*})\atop} \left| \frac{\lambda^{2, j}_{k}}{\lambda^{2, j}_{k}+\Delta \lambda^{2, j}_{k}}-1 \right| \left\| \Delta z^{k}\right\|^2, \max\limits_{j\in I^3({q^*}, 0)\atop} \left| \frac{\lambda^{3, j}_{k}}{\lambda^{3, j}_{k}+\Delta \lambda^{3, j}_{k}}-1\right| \left\| \Delta z^{k} \right\|^2 \bigg\} \bigg) . $

(3.17)

因$ 2< \tau< 3$, $0< \kappa < 1$, 由(3.17) 及(2.20) 有$ g_{j}(p^k+\Delta p^k+\Delta {\rm{ }}\tilde{p}^{k})>0$.类似的分析, 有$ c_{j}(z^k+\Delta z^k+ \Delta {\rm{ }}\tilde{z}^{k})>0$, $\phi(q^k_j+\Delta q^k_j+ \Delta {\rm{ }}\tilde{q}^k_j, u_k) >0$, $\forall j\in L_2$. (ⅱ)得证.

定理3.2  在上述假设条件下, 若${u_k} = o(\left\| {\Delta {z^K}} \right\|)$, 则无穷序列$\{z^{k}\}$超线性收敛到(MPEC) (1.1) 的稳定点$z^{*}$, 即

$ \left\| z^{k+1}-z^{*} \right\|=o(\left\| z^{k}-z^{*} \right\|). $

证明  证明类似文献[9]中定理4.6的证明.

利用Lingo软件建立模型求得算法对应问题的内点, 算法中的参数选取为$\xi=0.1$, $\eta_1=0.8$, $\eta_2=0.8$, $\eta_3=0.8$, $r1=1$, $r2=1$, $r3=1$, $\nu=3$, $\delta=2$, $\tau=2.5$, $\kappa=0.5$, $H_{0}$为$(n+2m_2)\times (n+2m_2)$的单位阵.数值实验问题来源于文[5], 文[6], 文[11]及文[12].

问题1   (见[5]问题2).

$ \min f(x, y)= \frac{1}{2}((x_{1}+x_{2}+y_{1}-15)^{2}+(x_{1}+x_{2}+y_{2}-15)^{2})\\ \mbox{s.t.}0\leq x\leq 10, w=N^{T}x+M^{T}y+q, 0\leq y\perp w\geq 0, $

$ q = \left( \begin{array}{l} - 36\\ - 25 \end{array} \right),N = \left( \begin{array}{l} 8/3\;\;\;\;2\\ 2\;\;\;\;\;\;5/4 \end{array} \right),M = \left( \begin{array}{l} 2\;\;\;\;\;\;5/4\\ 8/3\;\;\;2 \end{array} \right). $

问题2   (见[6]).

$ \begin{array}{l} \min \;\;\;\;\;f(x,y) = \frac{1}{2}{x^2} + \frac{1}{2}{y^2} + x - y\\ {\rm{s}}{\rm{.t}}{\rm{.}}\;\;\;\;\;\;0 \le (y - x) \bot y \ge 0. \end{array} $

问题3   (见[11]问题4).

$ \min f(x, y)=x^4+ 8y\\ \mbox{s.t.} g_1 (x, y)=x+ y-50 \leq 0, g_2 (x, y)=x^2+ y^2-100 \leq 0, \\ F(x, y)=\frac{1}{2}x^{2}+\frac{1}{2}y^2+x y+10, 0\leq F(x, y)\bot y \geq 0. $

问题4   (见[12] outrata33).

$ \begin{array}{l} \min \;\;\;\;\;f(x,y) = \frac{1}{2}({({y_1} - 3)^2} + {({y_2} - 4)^2} + 10y_4^2)\\ {\rm{s}}{\rm{.t}}{\rm{.}}\;\;\;\;\;\;0 \le x \le 10,\\ \;\;\;\;\;\;\;\;\;0 \le [(1 + 0.2x){y_1} - (3 + 1.333x) - 0.333{y_3} + 2{y_1}{y_4}] \bot {y_1} \ge 0,\\ \;\;\;\;\;\;\;\;\;0 \le [(1 + 0.1x){y_2} - x + {y_3} + 2{y_2}{y_4}] \bot {y_2} \ge 0,\\ \;\;\;\;\;\;\;\;\;0 \le (0.333{y_1} - {y_2} + 1 - 0.1x) \bot {y_3} \ge 0,\\ \;\;\;\;\;\;\;\;\;0 \le (9 + 0.1x - y_1^2 - y_2^2) \bot {y_4} \ge 0. \end{array} $

问题5   (见[12]qpec2).

$ \begin{array}{l} \min \;\;\;\;\;f(x,y) = \sum\limits_{i = 1}^{10} {{{({x_i} - 1)}^2}} + \sum\limits_{j = 1}^{20} {{{({y_j} - 2)}^2}} \\ {\rm{s}}{\rm{.t}}{\rm{.}}\;\;\;\;\;0 \le ({y_1} - {x_1}) \bot {y_1} \ge 0,\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \vdots \\ \;\;\;\;\;\;\;\;\;0 \le ({y_{10}} - {x_{10}}) \bot {y_{10}} \ge 0,\\ \;\;\;\;\;\;\;\;\;0 \le {y_{11}} \bot {y_{11}} \ge 0,;\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \vdots \\ \;\;\;\;\;\;\;\;\;0 \le {y_{20}} \bot {y_{20}} \ge 0. \end{array} $

通过表 1可以看出本文提出的算法是可行的.

对非线性互补约束均衡问题, 通过引入罚函数思想, 将非线性互补约束均衡问题转化为只含不等式约束的参数规划问题, 且当参数充分大时, 转化问题与原问题等价, 从而减少了问题研究的复杂性.基于内点法的思想, 提出了一个光滑QP-free算法求解转化后的光滑非线性规划问题.该QP-free算法具有如下优点:

（1）罚参数更新比文献[10]更简单；

（2）减弱了Hessian阵估计正定的假设条件, 算法仍具有超线性收敛速度.且数值实验结果表明本文提出的算法是可行的.