0 引言

主要研究以下一般形式的互补约束优化问题(MPCC)：

$ \begin{array}{l} \min \;\;f\left( x \right)\\ {\rm{s}}.\;{\rm{t}}.\;\;\;g\left( x \right) \leqslant 0,h\left( x \right) = 0,\\ \;\;\;\;\;\;\;\;G\left( x \right) \geqslant 0,H\left( x \right) \geqslant 0,\\ \;\;\;\;\;\;\;\;G{\left( x \right)^{\rm{T}}}H\left( x \right) = 0. \end{array} $

(1)

其中，f：Rⁿ→R, g：Rⁿ→R^m, h：Rⁿ→R^p, G, H：Rⁿ→R^l为二阶连续可微函数, g(x)≤0, h(x)=0称为一般约束条件, G(x)≥0, H(x)≥0, G(x)^TH(x)=0称为互补约束条件.

互补约束优化是一类重要的均衡约束优化问题(MPEC), 常用于经济学、工程学、交通运输科学、均衡博弈、数学规划理论等领域^[1].为此，众多学者开展了对互补约束优化问题的深入研究.然而, 求解互补约束优化问题是比较困难的.由于互补约束条件的存在, 任何可行点都无法满足非线性规划约束规范的要求, 比如线性独立约束规范(LICQ)、M-F约束规范(MFCQ), 因此求解非线性规划问题的标准理论和算法均不适用于此问题; 此外, 因其可行域复杂, 不具有连通性、闭性和凸性等性质，所以不同于一般的约束优化问题.目前，已有许多解决MPCC的方法, 如光滑化方法^[2-6]、序列二次规划法^[7-8]和松弛法等^[9-11].

光滑化方法是应用最广泛的一类求解问题(1)的方法, 该方法通过引入光滑参数, 用一个光滑函数构造等式或不等式约束近似问题(1)的互补约束条件, 将问题(1)转化为一般的非线性规划近似问题.通过解近似问题的一系列光滑子问题, 得到问题(1)的最优解或某种类型的稳定点.现有的光滑化算法主要利用扰动的F-B函数和最值函数的光滑函数近似互补约束条件.例如, 文献[2]给出了扰动的F-B函数：

$ \varphi \left( {a,b,\varepsilon } \right) = a + b - \sqrt {{a^2} + {b^2} + \varepsilon } , $

其中，a, b为常数, ε为光滑参数, 利用该函数构造等式约束条件近似问题(1)的互补约束条件, 在互补约束优化问题的线性独立约束规范(MPCC-LICQ)和渐进弱非退化条件(AWN)下, 得到了满足二阶必要条件的近似问题稳定点序列收敛于问题(1)的B-稳定点.文献[3]利用最小值函数的光滑近似函数

$ {\varphi _\varepsilon }\left( {a,b} \right) = - \varepsilon \ln \left( {\exp \left( { - a/\varepsilon } \right) + \exp \left( { - b/\varepsilon } \right)} \right), $

得到了问题(1)的光滑近似问题.在MPCC-LICQ和上水平严格互补条件(ULSC)下, 证明了近似问题满足二阶必要条件的稳定点序列收敛于问题(1)的B-稳定点.文献[4]利用绝对值函数的光滑近似函数, 将互补约束条件中的G(z)^TH(z)=0用光滑不等式做近似替换, 在较弱的约束规范MPEC-MFCQ下, 证明了近似问题的任意稳定点序列的聚点收敛于问题(1)的C-稳定点; 若加上额外假设, 上述聚点收敛于问题(1)的M稳定点, 甚至S稳定点.其他更为简单有效的方法有待进一步研究.

基于具有良好性质的光滑函数^[12], 即Sigmoid函数的积分函数, 将互补约束条件光滑化, 利用这一新的光滑化方法, 得到了问题(1)的形式简单的光滑近似问题.当i∈I₀₀(x)={i|G_i(x)=0, H_i(x)=0}, 其中当x为问题(1)的任意可行点时, 给出了不同于AWN和ULSC的假设条件：

$ \mathop {\lim }\limits_{{x_k} \to \bar x,\alpha \to 0} \left[ {\left( {{G_i}\left( {{x_k}} \right) - {H_i}\left( {{x_k}} \right)} \right)/\alpha } \right] < \infty ,i \in {I_{00}}\left( {\bar x} \right), $

(2)

其中α>0为光滑参数.由此对得到的近似问题的稳定点序列{x_k}的收敛性做了详细研究.当α趋于0时, 在MPCC-LICQ和较弱的假设条件(2)下, 证明了光滑近似问题的KKT稳定点序列收敛于原问题的C-稳定点.进一步, 若考虑弱二阶必要条件, 上述KKT稳定点序列则收敛于原问题的S-稳定点.此外, 文献[2-3, 5-6]仅对稳定点的收敛性给出理论证明, 并没有对相应算法进行数值实验.基于此, 本文最后设计了一个光滑化算法, 对MacMPEC测试题库中的一些算例进行一系列数值实验, 在相同的初始条件下, 将得到的结果与文献[4]中算法的结果进行比较, 以验证本文算法的有效性.

1 基础知识

设问题(1)的可行域为F, 对x∈F, 定义以下指标集：

$ {I_{0 + }}\left( {\bar x} \right) = \left\{ {i\left| {{G_i}\left( {\bar x} \right) = 0,{H_i}\left( {\bar x} \right) > 0} \right.} \right\}, $

$ {I_{00}}\left( {\bar x} \right) = \left\{ {i\left| {{G_i}\left( {\bar x} \right) = 0,{H_i}\left( {\bar x} \right) = 0} \right.} \right\}, $

$ {I_{ + 0}}\left( {\bar x} \right) = \left\{ {i\left| {{G_i}\left( {\bar x} \right) > 0,{H_i}\left( {\bar x} \right) = 0} \right.} \right\}. $

定义1 如果向量组：{$\nabla $g_i(x), i∈I_g(x)}, {$\nabla $h_i(x), i=1, 2, …, p}, {$\nabla $G_i(x), I₀₀(x)∪I₀₊(x)}, {$\nabla $H_i(x), i∈I₀₀(x)∪I₊₀(x)}线性无关, 其中I_g(x)={i：g_i(x)=0}，则称问题(1)在可行点x处满足互补约束优化问题线性独立约束规范(MPCC-LICQ).

定义2 设x∈F, λ ∈R^m, μ ∈R^p, u , v ∈R^l, 称

$ \begin{array}{l} L\left( {x,\mathit{\boldsymbol{\lambda }},\mathit{\boldsymbol{\mu }},\mathit{\boldsymbol{u}},\mathit{\boldsymbol{v}}} \right) = f\left( x \right) + {\mathit{\boldsymbol{\lambda }}^{\rm{T}}}g\left( x \right) + {\mathit{\boldsymbol{\mu }}^{\rm{T}}}h\left( x \right) - \\ \;\;\;\;\;\;{\mathit{\boldsymbol{u}}^{\rm{T}}}G\left( x \right) - {\mathit{\boldsymbol{v}}^{\rm{T}}}H\left( x \right) \end{array} $

为问题(1)在x处对应乘子向量λ , μ , u , v 的拉格朗日函数.则有

$ \begin{array}{*{20}{c}} {{\nabla _x}L\left( {x,\mathit{\boldsymbol{\lambda }},\mathit{\boldsymbol{\mu }},\mathit{\boldsymbol{u}},\mathit{\boldsymbol{v}}} \right) = \nabla f\left( x \right) + \nabla g{{\left( x \right)}^{\rm{T}}}\mathit{\boldsymbol{\lambda }} + }\\ {\nabla h{{\left( x \right)}^{\rm{T}}}\mathit{\boldsymbol{\mu }} - \nabla G{{\left( x \right)}^{\rm{T}}}\mathit{\boldsymbol{u}} - \nabla H{{\left( x \right)}^{\rm{T}}}\mathit{\boldsymbol{v}}.} \end{array} $

定义3 设x∈F, 若存在乘子向量λ ∈R^m, μ ∈R^p, u , v ∈R^l，使得

$ \begin{array}{l} {\nabla _x}L\left( {\bar x,\mathit{\boldsymbol{\lambda }},\mathit{\boldsymbol{\mu }},\mathit{\boldsymbol{u}},\mathit{\boldsymbol{v}}} \right) = 0,\mathit{\boldsymbol{\lambda }} \geqslant 0,{\mathit{\boldsymbol{\lambda }}^{\rm{T}}}g\left( {\tilde x} \right) = 0,\\ {u_i} = 0,i \in {I_{ + 0}}\left( {\bar x} \right),\;\;\;\;{v_i} = 0,i \in {I_{ + 0}}\left( {\bar x} \right), \end{array} $

则称x是问题(1)的W-稳定点.

(1) 如果x是W-稳定点，并且u_iv_i≥0, i∈I₀₀(x), 则称x是问题(1)的C-稳定点.

(2) 如果x是W-稳定点，并且u_i>0, v_i>0或u_iv_i=0, u_iv_i=0, i∈I₀₀(x), 则称x是问题(1)的M-稳定点.

(3) 如果x是W-稳定点，并且u_i≥0, v_i≥0, i∈I₀₀(x), 则称x是问题(1)的S-稳定点.

2 新的光滑化近似函数及性质

考虑互补约束条件

$ a \geqslant 0,b \geqslant 0,ab = 0. $

(3)

可以证明式(3)等价于

$ \min \left\{ {a,b} \right\} = 0. $

(4)

进一步, 可以证明式(4)等价于

$ a - {\left( {a - b} \right)_ + } = 0, $

(5)

其中，(a-b)₊=max{a-b, 0}.

由文献[12]知，非光滑函数

$ {\left( x \right)_ + } = \max \left( {x,0} \right), $

(6)

可由以下光滑的Sigmoid函数的积分函数近似：

$ p\left( {x,\alpha } \right) = x + \alpha \ln \left( {1 + {{\rm{e}}^{ - \frac{x}{\alpha }}}} \right), $

(7)

其中, x为实数, α为光滑参数, 且α>0.由文献[12], 光滑函数p(x, α)具有以下性质：

引理1 设p(x, α)由式(7)定义, 则有

(ⅰ) p(x, α)关于α递增, 且有

$ {\left( x \right)_ + } \leqslant p\left( {x,\alpha } \right) \leqslant {\left( x \right)_ + } + \alpha \ln 2. $

(ⅱ)当α趋于0时, (x)₊≈p(x, α).

(ⅲ)对任意x∈Rⁿ, α>0, 0≤p′_α(x, α)≤ln 2.

由引理1, 式(5)可用下式近似表示：

$ a - \max \left\{ {a - b,0} \right\} \approx a - \left( {a - b} \right) - \alpha \ln \left( {1 + {{\rm{e}}^{ - \frac{{a - b}}{\alpha }}}} \right) = 0, $

(8)

即互补约束条件(3)可近似表示为

$ b - \alpha \ln \left( {1 + {{\rm{e}}^{\left( { - \frac{1}{\alpha }} \right)\left( {a - b} \right)}}} \right) = 0. $

(9)

对于α>0, 定义光滑函数Φ(x, α)：Rⁿ×R⁺→R^l,

$ \mathit{\Phi }\left( {x,\alpha } \right) = \left( {\begin{array}{*{20}{c}} {{\mathit{\Phi }_1}\left( {x,\alpha } \right)}\\ \vdots \\ {{\mathit{\Phi }_l}\left( {x,\alpha } \right)} \end{array}} \right), $

其中，

$ {\mathit{\Phi }_i}\left( {x,\alpha } \right) = {H_i}\left( x \right) - \alpha \ln \left( {1 + {{\rm{e}}^{ - \frac{1}{\alpha }\left( {{G_i}\left( x \right) - {H_i}\left( x \right)} \right)}}} \right). $

(10)

根据以上分析, 问题(1)中的互补约束条件：

$ G\left( x \right) \geqslant 0,H\left( x \right) \geqslant 0,G{\left( x \right)^{\rm{T}}}H\left( x \right) = 0, $

可由Φ(x, α)=0替换.

于是, 得到问题(1)的一个新的光滑近似问题：

$ \begin{array}{l} \min \;\;\;f\left( x \right),\\ {\rm{s}}.\;{\rm{t}}.\;g\left( x \right) \leqslant 0,h\left( x \right) = 0, \end{array} $

(11)

$ \mathit{\Phi }\left( {x,\alpha } \right) = 0. $

定义近似问题的可行域为F_α, 下面分析近似函数Φ(x, α)的相关性质.

引理2 设Φ_i(x, α), i=1, 2, …, l, 由式(10)的定义, 则有

(ⅰ)对任意α>0, Φ_i(x, α)关于x连续可微.

(ⅱ)计算可得Φ_i(x, α)的梯度,

$ {\nabla _x}{\mathit{\Phi }_i}\left( {x,\alpha } \right) = {\xi _i}\left( {x,\alpha } \right)\nabla {G_i}\left( x \right) + {\eta _i}\left( {x,\alpha } \right)\nabla {H_i}\left( x \right), $

(12)

$ \begin{array}{l} \nabla _x^2{\mathit{\Phi }_i}\left( {x,\alpha } \right) = {\xi _i}\left( {x,\alpha } \right){\nabla ^2}{G_i}\left( x \right) + \\ \;\;\;\;\;\;{\eta _i}\left( {x,\alpha } \right){\nabla ^2}{H_i}\left( x \right) - \frac{1}{\alpha }\left( {{\xi _i}\left( {x,\alpha } \right) - \xi _i^2\left( {x,\alpha } \right)} \right) \times \\ \;\;\;\;\;\;\left( {\nabla {G_i}\left( x \right)\nabla {G_i}{{\left( x \right)}^{\rm{T}}} - \nabla {H_i}\left( x \right)\nabla {G_i}{{\left( x \right)}^{\rm{T}}}} \right) + \\ \;\;\;\;\;\;\frac{1}{\alpha }{\xi _i}\left( {x,\alpha } \right){\eta _i}\left( {x,\alpha } \right) \times \left( {\nabla {G_i}\left( x \right)\nabla {H_i}{{\left( x \right)}^{\rm{T}}} - } \right.\\ \;\;\;\;\;\;\left. {\nabla {H_i}\left( x \right)\nabla {H_i}{{\left( x \right)}^{\rm{T}}}} \right). \end{array} $

(13)

其中，

$ {\xi _i}\left( {x,\alpha } \right) = \frac{{{{\rm{e}}^{\left( { - \frac{1}{\alpha }} \right)\left( {{G_i}\left( x \right) - {H_i}\left( x \right)} \right)}}}}{{1 + {{\rm{e}}^{\left( { - \frac{1}{\alpha }} \right)\left( {{G_i}\left( x \right) - {H_i}\left( x \right)} \right)}}}}, $

(14)

$ {\eta _i}\left( {x,\alpha } \right) = 1 - \frac{{{{\rm{e}}^{\left( { - \frac{1}{\alpha }} \right)\left( {{G_i}\left( x \right) - {H_i}\left( x \right)} \right)}}}}{{1 + {{\rm{e}}^{\left( { - \frac{1}{\alpha }} \right)\left( {{G_i}\left( x \right) - {H_i}\left( x \right)} \right)}}}}, $

(15)

且ξ_i(x, α)∈(0, 1), η_i(x, α)∈(0, 1), ξ_i(x, α)+η_i(x, α)=1.∀i=1, 2, …, l, ξ_i(x, α), η_i(x, α)连续可微.

(ⅲ)设x_k∈Rⁿ, k∈N , 且当k→∞时, x_k→x∈F, 若对于i∈I₀₀(x),

$ \mathop {\lim }\limits_{{x_k} \to \bar x,\alpha \to 0} \left[ {\left( {{G_i}\left( {{x_k}} \right) - {H_i}\left( {{x_k}} \right)} \right)/\alpha } \right] < \infty , $

则

$ \mathop {\lim }\limits_{{x_k} \to \bar x,\alpha \to 0} {\nabla _x}{\mathit{\Phi }_i}\left( {{x_k},\alpha } \right) = {{\bar \xi }_i}\left( {\bar x} \right)\nabla {G_i}\left( {\bar x} \right) + {{\bar \eta }_i}\left( {\bar x} \right)\nabla {H_i}\left( {\bar x} \right), $

其中，

$ {{\bar \xi }_i}\left( {\bar x} \right) = \mathop {\lim }\limits_{{x_k} \to \bar x,\alpha \to 0} {\xi _i}\left( {{x_k},\alpha } \right) \in \left[ {0,1} \right], $

$ {{\bar \eta }_i}\left( {\bar x} \right) = \mathop {\lim }\limits_{{x_k} \to \bar x,\alpha \to 0} {\eta _i}\left( {{x_k},\alpha } \right) \in \left[ {0,1} \right], $

$ {{\bar \xi }_i}\left( {\bar x} \right) + {{\bar \eta }_i}\left( {\bar x} \right) = 1. $

且当i∈I₀₊(x)时, ξ_i(x)=1, η_i(x)=0;当i∈I₊₀(x)时, ξ_i(x)=0, η_i(x)=1;当i∈I₀₀(x)时, ξ_i(x)∈(0, 1), η_i(x)∈(0, 1).

证明  (ⅰ)由式(10)中Φ_i(x_k, α)的定义, 可得结论(ⅰ).

(ⅱ)通过计算可得结论(ⅱ).

(ⅲ)由式(14)、(15)可知

$ {{\bar \xi }_i}\left( {\bar x} \right) + {{\bar \eta }_i}\left( {\bar x} \right) = 1,\;\;\;i \in \left\{ {1,2, \cdots ,l} \right\}, $

若i∈I₀₊(x),

$ \begin{array}{l} {\xi _i}\left( {{x_k},\alpha } \right) = \frac{{{{\rm{e}}^{\left( { - \frac{1}{\alpha }} \right)\left( {{G_i}\left( {{x_k}} \right) - {H_i}\left( {{x_k}} \right)} \right)}}}}{{1 + {{\rm{e}}^{\left( { - \frac{1}{\alpha }} \right)\left( {{G_i}\left( {{x_k}} \right) - {H_i}\left( {{x_k}} \right)} \right)}}}} = \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\frac{1}{{\frac{1}{{{{\rm{e}}^{\left( { - \frac{1}{\alpha }} \right)\left( {{G_i}\left( {{x_k}} \right) - {H_i}\left( {{x_k}} \right)} \right)}}}} + 1}}, \end{array} $

$ \begin{array}{l} {\eta _i}\left( {{x_k},\alpha } \right) = 1 - \frac{{{{\rm{e}}^{\left( { - \frac{1}{\alpha }} \right)\left( {{G_i}\left( {{x_k}} \right) - {H_i}\left( {{x_k}} \right)} \right)}}}}{{1 + {{\rm{e}}^{\left( { - \frac{1}{\alpha }} \right)\left( {{G_i}\left( {{x_k}} \right) - {H_i}\left( {{x_k}} \right)} \right)}}}} = \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\frac{1}{{1 + {{\rm{e}}^{\left( { - \frac{1}{\alpha }} \right)\left( {{G_i}\left( {{x_k}} \right) - {H_i}\left( {{x_k}} \right)} \right)}}}}. \end{array} $

当α→0, x_k→x时, ξ_i(x)=1, η_i(x)=0.同理, 若i∈I₊₀(x), 当α→0, x_k→x时, ξ_i(x)=0, η_i(x)=1.

若i∈I₀₀(x), 已知ξ_i(x), η_i(x)∈[0, 1], ξ_i(x)+η_i(x)=1.若$\mathop {{\rm{lim}}}\limits_{{x_k} \to \overline x, \alpha \to 0} [({G_i}({x_k})-{H_i}({x_k}))/\alpha] < \infty $设

$ \mathop {\lim }\limits_{{x_k} \to \bar x,\alpha \to 0} \left[ {\left( {{G_i}\left( {{x_k}} \right) - {H_i}\left( {{x_k}} \right)} \right)/\alpha } \right] = a \in \left( { - \infty ,\infty } \right), $

那么，

$ {{\bar \xi }_i}\left( {\bar x} \right) = \mathop {\lim }\limits_{{x_k} \to \bar x,\alpha \to 0} {\xi _i}\left( {{x_k},\alpha } \right) = \frac{{\exp \left( { - a} \right)}}{{1 + \exp \left( { - a} \right)}} \ne 0, $

$ \begin{array}{l} {{\bar \eta }_i}\left( {\bar x} \right) = \mathop {\lim }\limits_{{x_k} \to \bar x,\alpha \to 0} {\eta _i}\left( {{x_k},\alpha } \right) = \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;1 - \frac{{\exp \left( { - a} \right)}}{{1 + \exp \left( { - a} \right)}} = \frac{1}{{1 + \exp \left( { - a} \right)}} \ne 0, \end{array} $

所以ξ_i(x)∈(0, 1), η_i(x)∈(0, 1).故结论(ⅲ)成立.

在常用于互补约束优化问题算法收敛性分析的假设条件下, 渐进弱非退化条件(AWN)是最弱的.利用F-B函数进行光滑化时, 若不满足AWN, 则难以得到期望的收敛性结果^[5].结合本文提出的光滑函数本身的结构特点, 可避免在F-B光滑化方法中遇到的问题.由文献[2], 若条件$\widehat \xi$_i(x)$\widehat \eta$_i(x)≠0, i∈I₀₀(x), 则稳定点序列x_k满足AWN条件, 且该条件可粗略地表示为互补约束函数列G_i(x_k)和H_i(x_k)以相同数量级收敛于0.

由引理2结论(ⅲ)的证明可知, 在较弱的条件

$ \mathop {\lim }\limits_{{x_k} \to \bar x,\alpha \to 0} \left[ {\left( {{G_i}\left( {{x_k}} \right) - {H_i}\left( {{x_k}} \right)} \right)/\alpha } \right] < \infty $

下, ξ_i(x)η_i(x)≠0, i∈I₀₀(x)成立.且由上述条件, 本文的光滑化方法不要求G_i(x_k)和H_i(x_k)以相同数量级收敛于0, 即需要的收敛性条件更弱, 因此得到的收敛性理论结果具有更广泛的适用性.下面通过一个互补约束的例子加以说明.

例1 已知x∈R , 设互补约束为

$ G\left( x \right) = {G_1}\left( x \right) = x,H\left( x \right) = {H_1}\left( x \right) = {x^2}, $

$ G{\left( x \right)^{\rm{T}}}H\left( x \right) = 0, $

易得其可行域为{0}.

设x=0, x_k∈Rⁿ, k∈N , 且k→∞时, x_k→x, 则$\mathop {{\rm{lim}}}\limits_{{x_k} \to \overline x } G({x_k}) = \mathop {{\rm{lim}}}\limits_{{x_k} \to \overline x } {x_k} = \overline x = 0$, $\mathop {{\rm{lim}}}\limits_{{x_k} \to \overline x } H({x_k}) = \mathop {{\rm{lim}}}\limits_{{x_k} \to \overline x } x_k^2 = {\overline x ^2} = 0$, 但G(x_k)和H(x_k)不以相同的数量级趋向于0.

对于光滑的F-B函数

$ {\mathit{\Phi }_\alpha }\left( x \right) = G\left( x \right) + H\left( x \right) - \sqrt {{G^2}\left( x \right) + {H^2}\left( x \right) + \alpha } , $

由文献[2]中的引理3.1, 将Φ_α(x)=0近似为G(x)^TH(x)=$\frac{\alpha }{2}$, 于是有

$ \begin{array}{l} {{\hat \xi }_i}\left( {\bar x} \right) = \mathop {\lim }\limits_{{x_k} \to \bar x,\alpha \to 0} \frac{{{H_i}\left( {{x_k}} \right)}}{{{G_i}\left( {{x_k}} \right) + {H_i}\left( {{x_k}} \right)}} = \\ \;\;\;\;\;\;\;\;\;\;\;\mathop {\lim }\limits_{{x_k} \to \bar x,\alpha \to 0} \frac{{{{H'}_i}\left( {{x_k}} \right)}}{{{{G'}_i}\left( {{x_k}} \right) + {{H'}_i}\left( {{x_k}} \right)}} = 0, \end{array} $

其中i=1.所以, $\widehat \xi $_i(x)$\widehat \eta $_i(x)≠0, i∈I₀₀(x)不成立, 即序列{x_k}不满足AWN条件.

对于本文提出的光滑化方法, 有

$ \begin{array}{l} \mathop {\lim }\limits_{{x_k} \to \bar x,\alpha \to 0} \left[ {\left( {{G_i}\left( {{x_k}} \right) - {H_i}\left( {{x_k}} \right)} \right)/\alpha } \right] = \\ \;\;\;\;\;\;\;\mathop {\lim }\limits_{{x_k} \to \bar x,\alpha \to 0} \left( {{{G'}_i}\left( {{x_k}} \right) + {{H'}_i}\left( {{x_k}} \right)} \right) = \\ \;\;\;\;\;\;\;\mathop {\lim }\limits_{{x_k} \to \bar x,\alpha \to 0} 1 - 2{x_k} = 1. \end{array} $

且${\overline \xi _i}(\overline x ) = \frac{{{e^{ -1}}}}{{1 + {e^{ -1}}}} \ne 0$, ${\overline \eta _i}(\overline x ) = \frac{1}{{1 + {e^{ -1}}}} \ne 0$,

因此, ξ_i(x)η_i(x)≠0, i∈I₀₀(x).

3 收敛性分析

设$\widehat x $是近似问题(11)的局部最优解.因问题(11)是一般的非线性规划问题, 所以在$\widehat x $处的线性独立约束规范成立下, 存在拉格朗日乘子向量λ ∈R^m, λ ≥0, μ ∈R^p, v ∈R^l, 使得

$ \begin{array}{*{20}{c}} {\nabla f\left( {\hat x} \right) + \nabla g{{\left( {\hat x} \right)}^{\rm{T}}}\mathit{\boldsymbol{\lambda }} + \nabla h{{\left( {\hat x} \right)}^{\rm{T}}}\mathit{\boldsymbol{\mu + }}{\nabla _x}\mathit{\Phi }{{\left( {\hat x,\alpha } \right)}^{\rm{T}}}\mathit{\boldsymbol{v}} = 0,}\\ {{\lambda _i} \geqslant 0,{\lambda _i}{g_i}\left( x \right) = 0,i = 1,2, \cdots ,m.} \end{array} $

记$\overline L (x,\alpha ,\mathit{\boldsymbol{\lambda }},\mathit{\boldsymbol{\mu }},\mathit{\boldsymbol{v}}) = f(x) + \sum\limits_{i = 1}^m {{\lambda _i}{g_i}(x)} + \sum\limits_{i = 1}^p {{\mu _i}{h_i}(x)} + \sum\limits_{i = 1}^l {{\mu _i}{\mathit{\Phi }_\mathit{i}}(x,\alpha )} $.若$\nabla $_xL($\widehat x$, α, λ, μ, v)=0, 且d^T$\nabla $_x²L($\widehat x$, α, λ , μ , v )d≥0, ∀d∈C_α($\widehat x$), 其中，

$ \begin{array}{l} {C_\alpha }\left( {\hat x} \right) = \left\{ {d \in {R^n}\left| {\nabla {g_i}{{\left( {\hat x} \right)}^{\rm{T}}}d = 0} \right.,\;\;\;i \in {I_g}\left( {\hat x} \right),} \right.\\ \;\;\;\;\;\;\;\;\;\;\;\;\nabla {h_i}{\left( {\hat x} \right)^{\rm{T}}}d = 0,\;\;\;\;i \in 1,2, \cdots ,p,\\ \;\;\;\;\;\;\;\;\;\;\;\;\left. {{\nabla _x}{\mathit{\Phi }_i}{{\left( {\hat x,\alpha } \right)}^{\rm{T}}}d = 0,i \in 1,2, \cdots ,l} \right\}. \end{array} $

则称近似问题(11)在$\widehat x$处满足弱二阶必要条件.

引理3 设x∈F, 若在x处MPCC-LICQ成立, 且$\mathop {{\rm{lim}}}\limits_{{x_k} \to \overline x, \alpha \to 0} [({G_i}({x_k})-{H_i}({x_k}))/\alpha] < \infty$, 则存在α>0和x的某个邻域U(x), 对任意α∈(0, α), x∈U(x)∩F_α, 近似问题(11)在x处满足LICQ.

证明 因为问题(1)在x处满足MPCC-LICQ, 由定义知, {$\nabla $g_i(x), i∈I_g(x)}, {$\nabla $h_i(x), i=1, 2, …, p}, {$\nabla $G_i(x), I₀₀(x)∪I₀₊(x)}, {$\nabla $H_i(x), i∈I₀₀(x)∪I₊₀(x)}线性无关.由文献[13]性质2.2知，存在x的邻域U(x)及α>0, 使得对α∈(0, α), ∀x∈U(x)∩F_α, 有

$ \begin{array}{l} \left\{ {\nabla {g_i}\left( x \right),i \in {I_g}\left( {\bar x} \right)} \right\},\left\{ {\nabla {h_i}\left( x \right),i = 1,2, \cdots ,p} \right\},\\ \left\{ {\nabla {G_i}\left( x \right),{I_{00}}\left( {\bar x} \right) \cup {I_{0 + }}\left( {\bar x} \right)} \right\},\left\{ {\nabla {H_i}\left( x \right),i \in {I_{00}}\left( {\bar x} \right)} \right.\\ \left. { \cup {I_{0 + }}\left( {\bar x} \right)} \right\} \end{array} $

(16)

线性无关.

否则, 假设对任意邻域U(x), 式(16)线性相关, 则必存在一个序列{x_k}_k=1^∞⊂Rⁿ, 其中当k→∞时, x_k→x, 存在‖(λ^k, μ^k, α^k, β^k)‖=1, 使得

$ \begin{array}{l} \sum\limits_{i \in {I_g}\left( {\bar x} \right)} {\lambda _i^k\nabla {g_i}\left( {{x_k}} \right)} + \sum\limits_{i = 1}^p {\mu _i^k\nabla {h_i}\left( {{x_k}} \right)} - \\ \sum\limits_{i \in {I_{00}}\left( {\bar x} \right) \cup {I_{0 + }}\left( {\bar x} \right)} {\alpha _i^k\nabla {G_i}\left( {{x_k}} \right)} - \sum\limits_{i \in {I_{00}}\left( {\bar x} \right) \cup {I_{ + 0}}\left( {\bar x} \right)} {\beta _i^k\nabla {H_i}\left( {{x_k}} \right)} = 0. \end{array} $

不失一般性, 假设当k→∞时, λ^k→λ^*, μ^k→μ^*, α^k→α^*, β^k→β^*, 则有

$ \begin{array}{l} \sum\limits_{i \in {I_g}\left( {\bar x} \right)} {{\lambda ^ * }\nabla {g_i}\left( {\bar x} \right)} + \sum\limits_{i = 1}^p {{\mu ^ * }\nabla {h_i}\left( {\bar x} \right)} - \\ \sum\limits_{i \in {I_{00}}\left( {\bar x} \right) \cup {I_{0 + }}\left( {\bar x} \right)} {{\alpha ^ * }\nabla {G_i}\left( {\bar x} \right)} - \sum\limits_{i \in {I_{00}}\left( {\bar x} \right) \cup {I_{ + 0}}\left( {\bar x} \right)} {{\beta ^ * }\nabla {H_i}\left( {\bar x} \right)} = 0, \end{array} $

(17)

且

$ \left\| {\left( {{\lambda ^ * },{\mu ^ * },{\alpha ^ * },{\beta ^ * }} \right)} \right\| = 1, $

(18)

但式(18)与{$\nabla $g_i(x), i∈I_g(x)}, {$\nabla $h_i(x), i=1, 2, …, p}, {$\nabla $G_i(x), I₀₀(x)∪I₀₊(x)}, {$\nabla $H_i(x), i∈I₀₀(x)∪I₊₀(x)}线性无关矛盾.

下证对∀x∈U(x)∩F_α, 近似问题(11)满足LICQ.

任取x∈U(x)∩F_α, 假设存在λ_i(i=1, 2, …, m), μ_i(i=1, 2, …, p), γ_i(i=1, 2…, l), 使得

$ \sum\limits_{i \in {I_g}\left( {\bar x} \right)} {{\lambda _i}\nabla {g_i}\left( {\bar x} \right)} + \sum\limits_{i = 1}^p {{\mu _i}\nabla {h_i}\left( {\bar x} \right)} + \sum\limits_{i = 1}^l {{\gamma _i}{\nabla _x}{\mathit{\Phi }_i}\left( {x,\alpha } \right)} = 0, $

(19)

即

$ \begin{array}{l} \sum\limits_{i \in {I_g}\left( {\bar x} \right)} {{\lambda _i}\nabla {g_i}\left( {\bar x} \right)} + \sum\limits_{i = 1}^p {{\mu _i}\nabla {h_i}\left( {\bar x} \right)} + \sum\limits_{i = 1}^l {{\gamma _i}{\xi _i}\left( {x,\alpha } \right)} \times \\ \nabla {G_i}\left( x \right) + \sum\limits_{i = 1}^l {{\gamma _i}{\eta _i}\left( {x,\alpha } \right)\nabla {H_i}\left( x \right)} = 0. \end{array} $

(20)

由引理2中的结论(ⅲ), 对于i∈I₊₀(x), 当α→0时, ξ_i(x, α)→0, η_i(x, α)→1;对于i∈I₀₊(x), 当α→0时, ξ_i(x, α)→1, η_i(x, α)→0.当α→0, x→x时, 式(20)可变为

$ \begin{array}{*{20}{c}} {\sum\limits_{i \in {I_g}\left( {\bar x} \right)} {{\lambda _i}\nabla {g_i}\left( {\bar x} \right)} + \sum\limits_{i = 1}^p {{\mu _i}\nabla {h_i}\left( {\bar x} \right)} + \sum\limits_{i \in {I_{00}}\left( {\bar x} \right) \cup {I_{0 + }}\left( {\bar x} \right)} {{\gamma _i}{\xi _i}\left( {\bar x} \right)} \times }\\ {\nabla {G_i}\left( x \right) + \sum\limits_{i \in {I_{00}}\left( {\bar x} \right) \cup {I_{ + 0}}\left( {\bar x} \right)} {{\gamma _i}{\eta _i}\left( {\bar x} \right)\nabla {H_i}\left( {\bar x} \right)} = 0.} \end{array} $

令u_i=-γ_iξ_i(x, α), v_i=-γ_iη_i(x, α), 与式(16)线性无关, 则有λ_i=0, i∈I_g(x), μ_i=0, i=1, 2, …, p, u_i=0, v_i=0, i=1, 2, …, l.由引理2, ξ_i(x, α), η_i(x, α)不同时为0, 所以γ_i=0, i=1, 2, …, l.因此, 对∀x∈U(x)∩F_α, {$\nabla $g_i(x), i∈I_g(x)}, {$\nabla $h_i(x), i=1, 2, …, p}, {$\nabla $_xΦ_i(x, α), i=1, 2, …, l}线性无关, 即近似问题(11)在x处满足LICQ.

定理1 在问题(11)中, 令α=α_k>0, 设{x_k}为问题(11)的KKT稳定点序列.如果x∈F是x_k的聚点, 在x处MPCC-LICQ成立, 且

$ \mathop {\lim }\limits_{{x_k} \to \bar x,\alpha \to 0} \left[ {\left( {{G_i}\left( {{x_k}} \right) - {H_i}\left( {{x_k}} \right)} \right)/\alpha } \right] < \infty , $

则当α_k趋于0时, x是问题(1)的C-稳定点.

证明 由{x_k}为问题(11)的KKT稳定点序列, 假设存在唯一的拉格朗日乘子λ^k, μ^k, γ^k, 使得

$ \begin{array}{l} \nabla f\left( {{x_k}} \right) + \sum\limits_{i = 1}^m {\lambda _i^k\nabla {g_i}\left( {{x_k}} \right)} + \sum\limits_{i = 1}^p {\mu _i^k\nabla {h_i}\left( {{x_k}} \right)} + \\ \;\;\;\;\;\;\;\sum\limits_{i = 1}^l {\gamma _i^k{\nabla _x}{\mathit{\Phi }_i}\left( {{x_k},{\alpha _k}} \right)} = 0, \end{array} $

(21)

$ {\lambda ^k} \geqslant 0,\lambda _i^k{g_i}\left( {{x_k}} \right) = 0,\;\;\;\;i = 1,2, \cdots ,m, $

(22)

$ \begin{array}{l} {g_i}\left( {{x_k}} \right) \leqslant 0,i = 1,2, \cdots ,m,\;\;\;\;{h_i}\left( {{x_k}} \right) = 0,i = 1,2,\\ \cdots ,p,{\mathit{\Phi }_i}\left( {{x_k},{\alpha _k}} \right) = 0,i = 1,2, \cdots ,l. \end{array} $

(23)

由式(21)得

$ \begin{array}{l} - \nabla f\left( {{x_k}} \right) = \sum\limits_{i = 1}^m {\lambda _i^k\nabla {g_i}\left( {{x_k}} \right)} + \sum\limits_{i = 1}^p {\mu _i^k\nabla {h_i}\left( {{x_k}} \right)} + \\ \;\;\;\;\;\;\;\sum\limits_{i = 1}^l {\gamma _i^k{\nabla _x}{\mathit{\Phi }_i}\left( {{x_k},{\alpha _k}} \right)} = \sum\limits_{i = 1}^m {\lambda _i^k\nabla {g_i}\left( {{x_k}} \right)} + \\ \;\;\;\;\;\;\;\sum\limits_{i = 1}^p {\mu _i^k\nabla {h_i}\left( {{x_k}} \right)} + \sum\limits_{i = 1}^l {\gamma _i^k{\xi _i}\left( {{x_k},{\alpha _k}} \right)\nabla {G_i}\left( {{x_k}} \right)} + \\ \;\;\;\;\;\;\;\sum\limits_{i = 1}^l {\gamma _i^k{\eta _i}\left( {{x_k},{\alpha _k}} \right)\nabla {H_i}\left( {{x_k}} \right)} . \end{array} $

(24)

定义u_i^k=-γ_iξ_i(x_k, α_k), v_i^k=-γ_iη_i(x_k, α_k), 则由式(24)得

$ \begin{array}{l} - \nabla f\left( {{x_k}} \right) = \sum\limits_{i = 1}^m {\lambda _i^k\nabla {g_i}\left( {{x_k}} \right)} + \sum\limits_{i = 1}^p {\mu _i^k\nabla {h_i}\left( {{x_k}} \right)} - \\ \;\;\;\;\;\;\;\;\sum\limits_{i = 1}^l {\mu _i^k\nabla {G_i}\left( {{x_k}} \right)} - \sum\limits_{i = 1}^l {v_i^k\nabla {H_i}\left( {{x_k}} \right)} . \end{array} $

(25)

下证式(25)中的乘子序列{(λ_i^k, μ_i^k, u_i^k, v_i^k)}有界.

如果{(λ_i^k, μ_i^k, u_i^k, v_i^k)}无界, 那么必存在一个子集K, 对任意k∈K, 有

$ \frac{\left( {{\lambda }^{k}},{{\mu }^{k}},{{u}^{k}},{{v}^{k}} \right)}{\left\| \left( {{\lambda }^{k}},{{\mu }^{k}},{{u}^{k}},{{v}^{k}} \right) \right\|}\xrightarrow[k\to \infty ]{k\in K}\left( {\lambda }',{\mu }',{u}',{v}' \right). $

当i∉I_g(x)时, 即g_i(x) < 0, 由x_k→x和g(x)的连续性, 当k充分大时, g_i(x_k) < 0, 又由式(22), 故当i∉I_g(x)时, λ_i^k=0, 所以λ′_i=0.式(25)两边同时除以‖(λ^k, μ^k, u^k, v^k)‖并取极限, 当k→∞时, 有

当i∉I_g(x)时, 即g_i(x) < 0, 由x_k→x和g(x)的连续性, 当k充分大时, g_i(x_k) < 0, 又由式(22), 故当i∉I_g(x)时, λ_i^k=0, 所以λ′_i=0.式(25)两边同时除以‖(λ^k, μ^k, u^k, v^k)‖并取极限, 当k→∞时, 有

$ \begin{array}{l} \sum\limits_{i \in {I_g}\left( {\bar x} \right)} {{{\lambda '}_i}\nabla {g_i}\left( {\bar x} \right)} + \sum\limits_{i = 1}^p {{{\mu '}_i}\nabla {h_i}\left( {\bar x} \right)} - \\ \sum\limits_{i \in {I_{00}}\left( {\bar x} \right) \cup {I_{0 + }}\left( {\bar x} \right)} {{{\mu '}_i}\nabla {G_i}\left( {\bar x} \right)} - \sum\limits_{i \in {I_{00}}\left( {\bar x} \right) \cup {I_{ + 0}}\left( {\bar x} \right)} {{{v'}_i}\nabla {H_i}\left( {\bar x} \right)} = 0. \end{array} $

由u_i^k, v_i^k的定义及引理2中的结论(ⅲ), 当i∈I₊₀(x)时, u_i′=0, 当i∈I₀₊(x)时, v_i′=0.(λ′, μ′, u′, v′)≠0与在x处满足MPCC-LICQ矛盾, 所以{(λ_i^k, μ_i^k, u_i^k, v_i^k)}有界.

不失一般性, 设{(λ_i^k, μ_i^k, u_i^k, v_i^k)}收敛于(λ, μ, u, v).由式(22), λ_i≥0, x∈F, λ_i^T$\nabla $g_i(x)=0, i=1, 2, …, m.设

$ \begin{array}{l} \mathop {\lim }\limits_{k \to \infty } \lambda _i^k = {{\bar \lambda }_i},\;\;\;\;i \in {I_g}\left( {\bar x} \right),\mathop {\lim }\limits_{k \to \infty } \mu _i^k = {{\bar \mu }_i},i = 1,2, \cdots ,p,\\ \mathop {\lim }\limits_{k \to \infty } u_i^k = {{\bar u}_i},\;\;\;\;\;\mathop {\lim }\limits_{k \to \infty } v_i^k = {{\bar v}_i},i = 1,2, \cdots ,l. \end{array} $

当i∈I₊₀(x)时, 即G_i(x)>0, H_i(x)=0, 故当k充分大时, 有G_i(x_k)>H_i(x_k).由

$ {\xi _i}\left( {{x_k},{\alpha _k}} \right) = \frac{{{{\rm{e}}^{ - \frac{1}{{{\alpha _k}}}\left( {{G_i}\left( {{x_k}} \right) - {H_i}\left( {{x_k}} \right)} \right)}}}}{{1 + {{\rm{e}}^{ - \frac{1}{{{\alpha _k}}}\left( {{G_i}\left( {{x_k}} \right) - {H_i}\left( {{x_k}} \right)} \right)}}}}, $

且当k→∞时, x_k→x, α_k→0,

$ \mathop {\lim }\limits_{k \to \infty } {{\rm{e}}^{ - \frac{1}{{{\alpha _k}}}\left( {{G_i}\left( {{x_k}} \right) - {H_i}\left( {{x_k}} \right)} \right)}} = 0, $

可得$\mathop {{\rm{lim}}}\limits_{k \to \infty }$ ξ_i(x_k, α_k)=0, 从而得u_i=0.同理, 当i∈I₀₊(x)时, 可得v_i=0.由g, h, G, H连续可微, 对式(25)两边取极限, 得

$ \begin{array}{*{20}{c}} {\nabla f\left( {\bar x} \right) + \sum\limits_{i \in {I_g}\left( {\bar x} \right)} {{{\bar \lambda }_i}\nabla {g_i}\left( {\bar x} \right)} + \sum\limits_{i = 1}^p {{{\bar \mu }_i}\nabla {h_i}\left( {\bar x} \right)} - }\\ {\sum\limits_{i \in {I_{00}}\left( {\bar x} \right) \cup {I_{0 + }}\left( {\bar x} \right)} {{{\bar u}_i}\nabla {G_i}\left( {\bar x} \right)} - \sum\limits_{i \in {I_{00}}\left( {\bar x} \right) \cup {I_{ + 0}}\left( {\bar x} \right)} {{{\bar v}_i}\nabla {H_i}\left( {\bar x} \right)} = 0.} \end{array} $

又u_i^kv_i^k=(γ_i^k)²ξ_i(x_k, α_k)η_i(x_k, α_k), 且由引理2中的结论(ⅲ), 当k→∞时, ξ_i(x)∈(0, 1), η_i(x)∈(0, 1), i∈I₀₀(x), 所以u_iv_i=γ_i²ξ_i(x)η_i(x)≥0, i∈I₀₀(x).即证得x是问题(1)的C-稳定点.

定理2 设α=α_k>0, {x_k}是问题(11)的KKT稳定点序列, 且问题(11)在x_k处满足弱二阶必要条件.如果x∈F是{x_k}的聚点, 在x处MPCC-LICQ成立, 且

$ \mathop {\lim }\limits_{{x_k} \to \bar x,\alpha \to 0} \left[ {\left( {{G_i}\left( {{x_k}} \right) - {H_i}\left( {{x_k}} \right)} \right)/\alpha } \right] < \infty , $

则当{α_k}趋于0时, x是问题(1)的S-稳定点.

证明 由定理1知, x是问题(1)的C-稳定点.假设x不是问题(1)的S-稳定点, 那么必存在i₀∈I₀₀(x), 使得

$ {{\bar u}_{{i_0}}} = \mathop {\lim }\limits_{k \to \infty } \left( { - \gamma _{{i_0}}^k{\xi _{{i_0}}}\left( {{x_k},{\alpha _k}} \right)} \right) < 0, $

$ {{\bar v}_{{i_0}}} = \mathop {\lim }\limits_{k \to \infty } \left( { - \gamma _{{i_0}}^k{\eta _{{i_0}}}\left( {{x_k},{\alpha _k}} \right)} \right) < 0. $

由引理2, 当k→∞时, ξ_i0(x_k, α_k)→ξ_i0(x)>0, η_i0(x_k, α_k)→η_i0(x)>0.

因为在x处MPCC-LICQ成立, 由引理3及$\nabla $g, $\nabla $h, $\nabla $G, $\nabla $H连续, I_g(x_k)⊆I_g(x)可知, 由$\nabla $g_i(x_k), $\nabla $h_i(x_k), $\nabla $G_i(x_k), $\nabla $H_i(x_k)组成的矩阵为列满秩矩阵, 因此可取有界序列{d_k}, 使得

$ \nabla {g_i}{\left( {{x_k}} \right)^{\rm{T}}}{d_k} = 0,\;\;\;i \in {I_g}\left( {{x_k}} \right), $

$ \nabla {h_i}{\left( {{x_k}} \right)^{\rm{T}}}{d_k} = 0,\;\;\;\;i = 1,2, \cdots ,p, $

$ \nabla {G_i}{\left( {{x_k}} \right)^{\rm{T}}}{d_k} = 0,\;\;\;i \in \left\{ {1,2, \cdots ,l,} \right\}\backslash {i_0}, $

$ \nabla {H_i}{\left( {{x_k}} \right)^{\rm{T}}}{d_k} = 0,\;\;\;i \in \left\{ {1,2, \cdots ,l,} \right\}\backslash {i_0}, $

$ \nabla {G_{{i_0}}}{\left( {{x_k}} \right)^{\rm{T}}}{d_k} = {\eta _{{i_0}}}\left( {{x_k},{\alpha _k}} \right), $

$ \nabla {H_{{i_0}}}{\left( {{x_k}} \right)^{\rm{T}}}{d_k} = - {\xi _{{i_0}}}\left( {{x_k},{\alpha _k}} \right). $

下证d_k∈C_αk(x_k), 其中，C_αk(x_k)={d_k∈Rⁿ|$\nabla $g_i(x_k)^Td_k=0, i∈I_g(x_k), $\nabla $h_i(x_k)^Td_k=0, i=1, 2, …, p, $\nabla $_xΦ_i(x_k, α_k)^Td_k=0, i∈1, 2, …, l}.由引理2中的结论(ⅱ)得,

$ \begin{array}{l} {\nabla _x}\mathit{\Phi }{\left( {{x_k},{\alpha _k}} \right)^{\rm{T}}}{d_k} = \left( {{\xi _i}\left( {{x_k},{\alpha _k}} \right)\nabla {G_i}{{\left( {{x_k}} \right)}^{\rm{T}}} + } \right.\\ \;\;\;\;\;\;\;\left. {{\eta _i}\left( {{x_k},{\alpha _k}} \right)\nabla {H_i}{{\left( {{x_k}} \right)}^{\rm{T}}}} \right){d_k} = \\ \;\;\;\;\;\;\;{\xi _i}\left( {{x_k},{\alpha _k}} \right)\nabla {G_i}{\left( {{x_k}} \right)^{\rm{T}}}{d_k} + \\ \;\;\;\;\;\;\;{\eta _i}\left( {{x_k},{\alpha _k}} \right)\nabla {H_i}{\left( {{x_k}} \right)^{\rm{T}}}{d_k}, \end{array} $

当i≠i₀时, $\nabla $_xΦ(x_k, α_k)^Td_k=0,

当i=i₀时,

$ \begin{array}{l} {\nabla _x}\mathit{\Phi }{\left( {{x_k},{\alpha _k}} \right)^{\rm{T}}}{d_k} = {\xi _{{i_0}}}\left( {{x_k},{\alpha _k}} \right){\eta _{{i_0}}}\left( {{x_k},{\alpha _k}} \right) - \\ \;\;\;\;\;\;{\eta _{{i_0}}}\left( {{x_k},{\alpha _k}} \right){\xi _{{i_0}}}\left( {{x_k},{\alpha _k}} \right) = 0. \end{array} $

综上可得$\nabla $_xΦ(x_k, α_k)^Td_k=0, i=1, 2…, l.因此d_k∈C_αk(x_k).

由在任意点x_k处弱二阶必要条件成立，得

$ d_k^{\rm{T}}\nabla _x^2\bar L\left( {{x_k},{\alpha _k},{\lambda _k},{\mu _k},{\gamma _k}} \right){d_k} \geqslant 0, $

(26)

即

$ \begin{array}{l} d_k^{\rm{T}}{\nabla ^2}f\left( {{x_k}} \right){d_k} + \sum\limits_{i \in {I_g}\left( {{x_k}} \right)} {\lambda _i^kd_k^{\rm{T}}{\nabla ^2}{g_i}\left( {{x_k}} \right){d_k}} + \\ \sum\limits_{i = 1}^p {\mu _i^kd_k^{\rm{T}}{\nabla ^2}{h_i}\left( {{x_k}} \right){d_k}} + \sum\limits_{i = 1}^l {\gamma _i^kd_k^T\nabla _x^2{\mathit{\Phi }_i}\left( {{x_k},{\alpha _k}} \right){d_k}} \geqslant 0. \end{array} $

由引理2中的结论(ⅱ),

$ \begin{array}{l} d_k^{\rm{T}}\nabla _x^2{\mathit{\Phi }_i}\left( {{x_k},{\alpha _k}} \right){d_k} = {\xi _i}\left( {{x_k},{\alpha _k}} \right)d_k^{\rm{T}}{\nabla ^2}{G_i}\left( {{x_k}} \right){d_k} + \\ \;\;\;\;\;\;\;\;\;\;{\eta _i}\left( {{x_k},{\alpha _k}} \right)d_k^{\rm{T}}{\nabla ^2}{H_i}\left( x \right){d_k} - \frac{1}{{{\alpha _k}}}\left( {{\xi _i}\left( {{x_k},{\alpha _k}} \right) - } \right.\\ \;\;\;\;\;\;\;\;\;\;\left. {\xi _i^2\left( {{x_k},{\alpha _k}} \right)} \right)\left( {d_k^{\rm{T}}\nabla {G_i}\left( {{x_k}} \right)\nabla {G_i}{{\left( {{x_k}} \right)}^{\rm{T}}}{d_k} - } \right.\\ \;\;\;\;\;\;\;\;\;\;\left. {d_k^{\rm{T}}\nabla {H_i}\left( {{x_k}} \right)\nabla {G_i}{{\left( {{x_k}} \right)}^{\rm{T}}}{d_k}} \right) + \\ \;\;\;\;\;\;\;\;\;\;\frac{1}{{{\alpha _k}}}{\xi _i}\left( {{x_k},{\alpha _k}} \right){\eta _i}\left( {{x_k},{\alpha _k}} \right)\left( {d_k^{\rm{T}}\nabla {G_i}\left( {{x_k}} \right)\nabla {H_i}\left( {{x_k}} \right){d_k} - } \right.\\ \;\;\;\;\;\;\;\;\;\;\left. {d_k^{\rm{T}}\nabla {H_i}\left( {{x_k}} \right)\nabla {H_i}{{\left( {{x_k}} \right)}^{\rm{T}}}{d_k}} \right). \end{array} $

当i≠i₀时,

$ \begin{array}{l} d_k^{\rm{T}}\nabla _x^2{\mathit{\Phi }_i}\left( {{x_k},{\alpha _k}} \right){d_k} = {\xi _i}\left( {{x_k},{\alpha _k}} \right)d_k^{\rm{T}}{\nabla ^{\rm{2}}}{G_i}\left( {{x_k}} \right){d_k} + \\ \;\;\;\;\;\;\;\;{\eta _i}\left( {{x_k},{\alpha _k}} \right)d_k^{\rm{T}}{\nabla ^{\rm{2}}}{H_i}\left( x \right){d_k}. \end{array} $

当i= i ₀时,

$ \begin{array}{l} d_k^{\rm{T}}\nabla _x^2{\mathit{\Phi }_i}\left( {{x_k},{\alpha _k}} \right){d_k} = {\xi _{{i_0}}}\left( {{x_k},{\alpha _k}} \right)d_k^{\rm{T}}{\nabla ^{\rm{2}}}{G_{{i_0}}}\left( {{x_k}} \right){d_k} + \\ \;\;\;\;\;\;\;\;{\eta _{{i_0}}}\left( {{x_k},{\alpha _k}} \right)d_k^{\rm{T}}{\nabla ^2}{H_{{i_0}}}\left( x \right){d_k} - \frac{1}{{{\alpha _k}}}{\xi _{{i_0}}}\left( {{x_k},{\alpha _k}} \right){\eta _{{i_0}}}\left( {{x_k},{\alpha _k}} \right). \end{array} $

故

$ \begin{array}{l} d_k^{\rm{T}}\nabla _x^2L\left( {{x_k},{\alpha _k},{\lambda _k},{\mu _k},{\gamma _k}} \right){d_k} = \\ \;\;\;\;\;d_k^{\rm{T}}{\nabla ^2}f\left( {{x_k}} \right){d_k} + \sum\limits_{i \in {I_g}\left( {\bar x} \right)} {\lambda _i^kd_k^{\rm{T}}{\nabla ^2}{g_i}\left( {{x_k}} \right){d_k}} + \\ \;\;\;\;\;\sum\limits_{i = 1}^p {\mu _i^kd_k^{\rm{T}}{\nabla ^2}{h_i}\left( {{x_k}} \right){d_k}} + \\ \;\;\;\;\;\sum\limits_{i = 1}^l {\gamma _i^k\left( {{\xi _i}\left( {{x_k},{\alpha _k}} \right)d_k^{\rm{T}}{\nabla ^2}{G_i}\left( {{x_k}} \right){d_k} + } \right.} \\ \;\;\;\;\;\left. {{\eta _i}\left( {{x_k},{\alpha _k}} \right)d_k^{\rm{T}}{\nabla ^2}{H_i}\left( {{x_k}} \right){d_k}} \right) - \\ \;\;\;\;\;\frac{1}{{{\alpha _k}}}\gamma _{{i_0}}^k{\xi _{{i_0}}}\left( {{x_k},{\alpha _k}} \right){\eta _{{i_0}}}\left( {{x_k},{\alpha _k}} \right). \end{array} $

(27)

由{d_k}的有界性, f, g, h, G和H的二阶连续可微性及定理1中关于乘子有界性的证明, 可知式(27)中除了$\frac{{ -1}}{{{\alpha _k}}}$γ^k_i0ξ_i0(x_k, α_k)η_i0(x_k, α_k)项外, 其他项均有界.由于limk→∞-γ^k_i0ξ_i0(x_k, α_k)=$\mathop {{\rm{lim}}}\limits_{k \to \infty }$ u^k_i0=u_i0 < 0, 又ξ_i0(x_k, α_k) ∈(0, 1), 所以$\mathop {{\rm{lim}}}\limits_{k \to \infty }$ γ^k_i0=γ_i0>0.由引理2中的结论(ⅲ), 当k充分大时, $\mathop {{\rm{lim}}}\limits_{k \to \infty }$ξ_i0(x_k, α_k)=ξ_i0(x), $\mathop {{\rm{lim}}}\limits_{k \to \infty }$ η_i0(x_k, α_k)=η_i0(x), 且ξ_i0(x)∈(0, 1), η_i0(x)∈(0, 1), 故

$ - \frac{1}{{{\alpha _k}}}\gamma _{{i_0}}^k{\xi _{{i_0}}}\left( {{x_k},{\alpha _k}} \right){\eta _{{i_0}}}\left( {{x_k},{\alpha _k}} \right) \to - \infty , $

与式(26)矛盾, 故u_i0≥0.同理v_i0≥0.所以x是问题(1)的S-稳定点.

4 数值实验

算法1 (光滑化算法)

步0 给定初始可行点x₁∈Rⁿ, α₁>0, ε_stop, β∈(0, 1).令k：=1.

步1 令α_k为当前的光滑参数, 求解问题(11), 定义其最优解为x_k.

步2 计算l_k, 若l_k < ε_stop, 算法终止.否则令α_k+1：=β α_k, x_k+1：=x_k, k：=k+1, 转步1.其中，

$ \begin{array}{l} {l_k} = \max \left\{ {\left\| {\max \left\{ {g\left( {{x_k}} \right),0} \right\}} \right\|,\left\| {h\left( {{x_k}} \right)} \right\|,} \right.\\ \;\;\;\;\;\;\left. {\left\| {\min \left\{ {G\left( {{x_k}} \right),H\left( {{x_k}} \right)} \right\}} \right\|} \right\}. \end{array} $

算法1用l_k作为终止条件衡量解的准确性^[4].当l_k=0时, x_k是问题(1)的一个可行点.由算法1, 在一些假设条件下, x_k也是问题(11)的一个稳定点.进一步, 由定理1及定理2, x_k是问题(1)的一个近似最优解, 并且当l_k越接近0时, 解的准确性越高.

下面对MacMPEC测试题库^[14]中的一些算例进行数值实验.对于同样的问题, 在相同初始条件下, 将算法1得到的结果与文献[4]中相应算法(记为算法2)得到的结果进行了比较.所有算法程序均在内存为2.00 GB, CPU为2.13 GHz的笔记本电脑上运行, 操作系统为Windows7, Matlab版本为R2014a, 用其优化工具箱中的内置fmincon函数求解问题(11).

实验中, 取终止条件为ε_stop≤10^-6; 取初始的光滑参数α₁=1, β=0.1, 为得到相同的最优解, 取算例bilevel 1的初始光滑参数α₁=0.001，且同一算例初值相同.实验结果见表 1，表 1分别给出了问题的名称、测试问题的维数(n, m, l)、选取的初值x₁、目标函数的最优值f^*、最优解x^*、外迭代的次数k₁、内迭代的总次数k₂、终止条件l_k1等, 其中初值和最优解只给出了原问题的变量x对应的向量.

从表 1可以看出, 算法1求解问题(1)是有效的，所有算例均得到了和算法2较一致的最优值和最优解, 并且除算例desilva外, 算法1仅需用较少的迭代次数就可得到与算法2相同的近似最优值和最优解.另外, 通过算法1得到的终止条件l_k的16个算例中有11个其计算结果更接近0, 说明x^*是问题(1)的一个近似最优解, 且解的准确性更高.

考虑到表 1中算例的维数均低于20, 为此，在MacMPEC测试题库中选取了4个高维算例, 如表 2所示，此4个高维算例用算法1求解，均能在较短的时间t内得到较精确的近似最优解.

5 总结

利用Sigmoid函数的积分函数构造等式约束近似互补约束条件, 提出了一种新的光滑化方法, 得到了形式简单、有效可行的互补约束优化问题的光滑近似算法.对由近似问题得到的KKT稳定点序列的收敛性进行了进一步的理论研究, 给出了不同于AWN和ULSC的条件.证明了当光滑参数趋于0时, 近似问题的KKT稳定点序列收敛于MPCC的C稳定点；若同时考虑弱二阶必要条件, 则近似问题的KKT稳定点序列收敛于原问题的S-稳定点.进一步, 对提出的方法进行了包含高维算例的一系列数值实验, 并将运算结果与其他算法的结果进行了比较, 进一步验证了本文算法的有效性.然而，仍有大量工作值得今后继续研究：如在更弱的条件下, 即在MFCQ、ACQ或SCQ下, 能否得到同样的收敛结果; 前人均先假设近似问题的稳定点序列存在, 然而原问题应满足什么条件才能保证该假设成立; 以及利用提出的算法对更多大规模算例进行数值实验，这些均有待进一步研究.