本文研究如下形式的半无限规划离散化问题:

$ {\rm (P)}\qquad \min f(x)\ \ {\rm s.t.} \ \ x\in X=\{x\in R^n|\ g(x, t)\leq 0, \ \forall t\in T\}.$

其中$f: R^n\rightarrow R$连续可微, $g:R^n\times T\rightarrow R$关于变量$x$连续可微, $T$为区间$[a, b]$的有限离散子集, 其形式如下:

$T=\{t |\ t=a+i\cdot\frac{b-a}{l}, i=0, 1, 2, \cdots, l\}, $

其中$l$为正整数(视$[a, b]$的长度而定, $\geq 100$), 表示其离散水平.半无限规划离散化问题在工程设计、优化控制和半无限规划算法设计(作为子问题)中具有重要应用, 如文献[1-3].许多学者对此作了研究, 如文献[4-10].

基于标准非线性规划中经典的序列二次规划(SQP)算法, Panier和Tits在文献[4]中对问题(P)构建了一个二次规划(QP)子问题, 对其约束指标集进行了修正, 线搜索采用两阶段方法^[11], 算法结构简单, 在一定条件下可证明算法具有全局收敛性.然而, 该QP子问题目标函数中不含有二阶导数逼近信息, 算法达不到超线性收敛.为进一步向超线性收敛分析靠拢, 本文对文[4]中求解问题(P)的算法进行改进:在QP子问题目标函数中引进Lagrange函数Hesse阵的正定近似阵$H_k$; 约束指标集修正技术中进一步包含$H_k$的校正信息^[5]; 线搜索构建中包含$H_k$信息.改进后, 从另一角度论证算法的全局收敛性.

对于任意的$x\in R^n$, 本节使用如下记号:

$ \varphi(x)=\max\{0, g(x, t), t\in T\}, \\ T_0(x)=\{t\in T |\ g(x, t)=\varphi(x)\}, T_0^+(x)=\{t\in T |\ g(x, t)=\varphi(x), \varphi(x)>0\}. $

无特殊说明, 以下假设均成立.

假设2.1 函数$f: R^n \rightarrow R$与$g(\cdot, t):R^n\times T\rightarrow R$均一阶连续可微.

设$x^k\in R^n, T_k\subseteq T, $定义$\varphi_k=\max\{0, g(x^k, t), t\in T_k\}, \phi(x^k)=\max\limits_{t\in T_k}g(x^k, t)$.如果$T_0(x^k)\subseteq T_k\subseteq T$, 则$\varphi_k=\varphi(x^k)$.为计算搜索方向, 考虑如下QP子问题

$\begin {aligned} \left. \begin {array} {lll}&\min&z +\frac{1}{2}d^{T}H_{k}d, \\ {{\rm QP}(x^k, H_k, T_k)} \ \ \ \ \ \ \&{\rm s.t.}&\nabla {f(x^{k})}^{T}d\leq z+\gamma\varphi_k, \\ && g(x^{k}, t)+\nabla_x g(x^{k}, t)^Td\leq z+\varphi_k, \ t\in T_k, \end{array} \right. \end {aligned}$

(2.1)

其中$\gamma$为正常数, $H_k$对称正定.

引理2.1 若$x^k\in R^n$, 则问题(2.1) 有唯一最优解, 且等价于其KKT点.

参考文献[7, 引理2.1]可完成引理2.1的证明.其中有关特殊QP子问题解的唯一性证明见文献[12].为方便起见, 记$(d^{k}, z_{k})$为问题(2.1) 的唯一最优解, 亦即KKT点, 则存在乘子$\mu_k$与$u^k=(u_t^k, t\in T_k)$使得

$H_kd^k+\mu_k\nabla f(x^k)+\sum\limits_{t\in T_k}u_{t}^k\nabla_x g(x^k, t)=0,$

(2.2)

$\mu_k+\sum\limits_{t\in T_k} u_{t}^k=1,$

(2.3)

$0\leq\mu_k\bot\left(z_k+\gamma\varphi_k-\nabla f(x^k)^Td^k\right)\geq 0,$

(2.4)

$0\leq u_{t}^k\bot\left(z_k+\varphi_k-g(x^k, t)-\nabla_x g(x^k, t)^Td^k\right)\geq0, t\in T_k,$

(2.5)

其中$x\bot y$表示$x^Ty=0$.

假设2.2 对任意$x\in R^n$, Mangasarian-Fromovitz约束规格(简称MFCQ)成立, 即存在向量$d\in R^n$使得$\nabla_x g(x, t)^Td<0$对于所有$t\in T_0(x)$成立.

引理2.2 假设$T_k\subseteq T$使得$T_0(x^k)\subseteq T_k$.则(ⅰ) $v^k\stackrel{\triangle}=-(z_k+\frac12 (d^k)^TH_kd^k)\geq 0$, $z_k+(d^k)^TH_kd^k\leq0, \ z_k\leq0;$ (ⅱ) $z_k=0\Leftrightarrow d^k=0 \Leftrightarrow x^k$是问题(P)的KKT点.

证 (ⅰ) 由$(0, 0)^T$是问题(2.1) 的可行解, 易知$v^k\geq 0$.由KKT条件(2.2)-(2.5) 推导可知

$ \begin{aligned} (d^k)^TH_kd^k&=-\mu_k\nabla f(x^k)^Td^k-\sum\limits_{t\in T_k}u_{t}^k\nabla_x g(x^k, t)^Td^k\\&=-\mu_kz_k-\mu_k\gamma\varphi_k -\sum\limits_{t\in T_k}u_{t}^k(z_k+\varphi_k-g(x^k, t))\\&=-z_k(1-\sum\limits_{t\in T_k}u_{t}^k) -\mu_k\gamma\varphi_k-\sum\limits_{t\in T_k}u_{t}^kz_k +\sum\limits_{t\in T_k}u_{t}^k(g(x^k, t)-\varphi_k)\\&= -z_k-\mu_k\gamma\varphi_k+\sum\limits_{t\in T_k}u_{t}^k (g(x^k, t)-\varphi_k)\\&\leq -z_k, \end{aligned}$

进而$z_k\leq 0$.

(ⅱ)如果$x^k$是问题(P)的KKT点, 则存在乘子$\lambda^k=(\lambda_{t}^k, t\in T)$使得

$\nabla f(x^k)+\sum\limits_{t\in T}\lambda_{t}^k\nabla_x g(x^k, t)=0, \ 0\leq\lambda_{t}^k\perp g(x^k, t)\leq 0, \ t\in T. $

(2.6)

参考文[7]引理2.2(ⅱ)可完成此结论证明.

算法A

初始步参数$\alpha\in (0, \frac12), \beta\in (0, 1), \gamma>0, 0<\varrho\ll 1$.矩阵$H_0\in R^{n\times n}$对称正定, 指标集$T_0=T_0(x^0)\cup\{a\}\cup\{b\}$.初始点$x^0\in R^n$, 令$k:=0$.

步骤1 求解QP子问题(2.1) 得到KKT点$(d^{k}, z_{k})$, 乘子为$(u_{T_k}^k, \mu_k)$.如果$z_k=0$, 则$x^k$是问题(P)的一个KKT点, 停止.否则, 进入步骤2.

步骤2 如果$\varphi(x^k)>0$ (阶段Ⅰ), 令$\lambda_k$为序列$\{1, \beta, \beta^2, \cdots\}$第一个满足式(2.7) 或(2.8) 的$\lambda$值.

$\phi(x^k+\lambda d^k)-\phi(x^k)\leq -\alpha \lambda(d^k)^TH_kd^k,$

(2.7)

$\phi(x^k+\lambda d^k)\leq 0.$

(2.8)

如果$\varphi(x^k)=0$ (阶段Ⅱ), 令$\lambda_k$为序列$\{1, \beta, \beta^2, \cdots\}$第一个满足下面不等式组的$\lambda$值:

$f(x^k+\lambda d^k)-f(x^k)\leq -\alpha \lambda(d^k)^TH_kd^k,$

(2.9)

$\phi(x^k+\lambda d^k)\leq 0.$

(2.10)

步骤3 (ⅰ) 令$x^{k+1}=x^k+\lambda_kd^k$.

(ⅱ) 选取$T_{k+1}\supseteq T_0(x^{k+1})\cup T_k^b$, 其中$T^b_k=\{t\in T_k| u^k_t>0\}$.如果$\lambda_k<1$且$\varphi(x^k)>0$, 则$T_{k+1}:=T_{k+1}\cup T_0^+(\bar{x}^{k+1})$, 其中$\bar{x}^{k+1}=x^k+\frac{\lambda_k}{\beta}d^k$.

(ⅲ) 如果$\lambda_k\leq\varrho$, 且存在指标$\bar{t}_k\in T_0^+(\bar{x}^{k+1})\setminus T_k$, 则$H_{k+1}=H_k$.否则计算一个新的对称正定阵$H_{k+1}$.

(ⅳ) 令$k:=k+1$返回步骤1.

引理2.3 对于充分小的正数$\lambda$, 式(2.7)/(2.8), (2.9)-(2.10) 恒成立, 从而步骤2中的线搜索可以执行, 算法A是适定的.

证 由$\phi(x^k)$的定义, 函数$g$与$f$在迭代点$x^k+\lambda d^k$的泰勒展开, 问题(2.1) 的约束条件及引理2.2可完成本引理的证明.

本节讨论算法A的全局收敛性, 为此需进一步假设:

假设3.3 算法A产生的点列$\{x^k\}$有界.

假设3.4 矩阵序列$\{H_k\}$一致正定, 即存在两个正整数$a$和$b$, 使得$a\|d\|^2\leq d^TH_kd\leq b\|d\|^2, \ \forall d\in R^n, \ \forall k.$

引理3.4 序列$\{d^{k}\}$, $\{z_{k}\}$均有界, 且$\lim\limits_{k\rightarrow\infty}\lambda_kd^k=0$.

证 由引理2.2(ⅰ)的结论, 式(2.4) 及假设2.1, 2.2, 3.3及3.4可推得$\{d^{k}\}$有界, 进而易证$\{z_k\}$有界.为证$\lim\limits_{k\rightarrow\infty}t_kd^k=0$, 下面分两种情形进行论证.

情形Ⅰ 如果$\varphi(x^k)=0$.由式(2.9) 和假设3.4, 得

$ f(x^{k+1})-f(x^k)\leq-\alpha \lambda_k(d^k)^TH_kd^k\leq-\alpha \lambda_ka\|d^k\|^2\leq 0. $

由假设3.3知, $\{f(x^k)\}$单调递减且有界, 故收敛.进而由上式得$\lim\limits_{k\rightarrow\infty}\lambda_kd^k=0$.

情形Ⅱ 如果$\varphi(x^k)>0$.若线搜索(2.7) 被满足, 则

$\phi(x^k+\lambda d^k)-\phi(x^k)\leq -\alpha \lambda_k(d^k)^TH_kd^k \leq -\alpha \lambda_ka\|d^k\|^2\leq0, $

故$\{\phi(x^k)\}$单调有界故收敛, 从而$\lim\limits_{k\rightarrow\infty}\lambda_kd^k=0$.若线搜索(2.8) 被满足, 则$\phi(x^{k+1})\leq 0$, 从而$\varphi(x^{k+1})=0$.故第$k+1$次迭代线搜索进入阶段Ⅰ, 分析同上情形Ⅰ.证毕.

引理3.5 乘子序列$\{\mu_k\}$和$\{u^k\}$有界.

证 参考文[7]引理3.2可完成此引理证明.

引理3.6 (ⅰ) $d^k\stackrel{k\in K}\longrightarrow 0\Leftrightarrow z_k\stackrel{k\in K}\longrightarrow0$; (ⅱ) $(d^k, z_k)\stackrel{k\in K}\longrightarrow (0, 0)\Leftrightarrow v^k\stackrel{k\in K}\longrightarrow0$; (ⅲ) 如果$d^k\stackrel{k\in K}\longrightarrow 0$, 则$\{x^k\}_K$的任意聚点都是问题(P)的KKT点.进而给定$\{x^k\}_K$的聚点$x^*$, 则存在无限指标集$K'\subseteq K$使得$\{(x^k, u^k/\mu_k)\}_{K'}$收敛到KKT点对$(x^*, \xi^*)$, 且$\lim\limits_{k\in K'}\mu_k=\mu_*>0$.

证 (ⅰ) 由引理2.2(ⅰ)及假设3.4, 有$0\leq a\|d^k\|^2\leq (d^k)^TH_kd^k\leq -z_k$.若$z_k\stackrel{k\in K}\longrightarrow0$, 则$d^k\stackrel{k\in K}\longrightarrow0$.反之, 若$d^k\stackrel{k\in K}\longrightarrow 0$, 往证$z_k\stackrel{k\in K}\longrightarrow 0$.如果$\varphi(x^k)=0$, 则$\varphi_k=0$.由$\nabla f(x^k)^Td^k$ $\leq z_k+\gamma\varphi_k$及$z_k\leq 0$ (见引理2.2(ⅰ)), 易证当$d^k\stackrel{k\in K}\longrightarrow 0$时, $z_k\stackrel{k\in K}\longrightarrow 0$成立.如果$\varphi(x^k)>0$, 由$T_0(x^k)\subseteq T_k$可推得存在$t_0\in T_k$使得$g(x^k, t_0)=\varphi_k$, 从而$0\geq z_k\geq \nabla_x g(x^k, t_0)^Td^k$.显然, 若$d^k\stackrel{k\in K}\longrightarrow 0$, 则$z_k\stackrel{k\in K}\longrightarrow 0$.

(ⅱ) 如果$(d^k, z_k)\stackrel{k\in K}\longrightarrow (0, 0)$, 由$v^k$的定义知$v^k\stackrel{k\in K}\longrightarrow0$.反之, 由引理2.2(ⅰ)可得

$v^k\geq -\frac12(d^k)^TH_kd^k+ (d^k)^TH_kd^k\geq\frac12a\|d^k\|^2\geq 0.$

显然, 若$v^k\stackrel{k\in K}\longrightarrow 0$, 则$d^k\stackrel{k\in K}\longrightarrow0$.进而由结论(ⅰ)知$z_k\stackrel{k\in K}\longrightarrow0$, 于是$(d^k, z_k)\stackrel{k\in K}\longrightarrow (0, 0)$.

(ⅲ) 设$x^*$是迭代点列$\{x^k\}_K$任意给定的聚点.记

$L_0(x^k)=\{t\in T_k|\ g(x^k, t)+\nabla_xg(x^k, t)^Td^k= z_k+\varphi_k\}.$

(3.1)

考虑到$T_k$与$L_0(x^k)$是有限集$T$的子集, 以及引理3.4和3.5, 不妨设存在无限子集$K'\subseteq K$, 使得

$(x^k, H_k, \eta_k, \varphi_k, \mu_k, u^k)\stackrel{k\in K'}\longrightarrow (x^*, H_*, \eta_*, \varphi(x^*), \mu_*, u^*), T_k\equiv \hat{T}, \ L_0(x^k)\equiv L_0, \forall k\in K'.$

因$d^k\stackrel{k\in K'}\longrightarrow 0$, 由结论(ⅰ)知$z_k\stackrel{k\in K'}\longrightarrow 0$, 根据(3.1) 式可得$L_0\subseteq T_0(x^*)$.进而对KKT条件(2.2)-(2.5) 在$k\in K'$中取极限, 得

$\mu_*\nabla f(x^*)+\sum\limits_{t\in L_0}u_{t}^*\nabla_x g(x^*, t)=0,$

(3.2)

$\varphi_*-g(x^*, t)=0, t\in L_0,$

(3.3)

$\mu_*+\sum\limits_{t\in L_0} u_t^*=1, \; \mu_*\gamma\varphi(x^*)=0, \; \mu_*\geq0, \; u_t^*\geq0, t\in \hat{T}.$

(3.4)

由(3.4) 式知$(\mu_*, u^*)\neq 0$.由(3.2) 式和假设2.2 (在$x^*$处)可证得$\mu_*>0$.进而由(3.4) 式知$\varphi(x^*)=0$, 从而$x^*\in X$.令$u_t^*=0, t\in T_q\backslash \hat{T}, $从(3.2)-(3.4) 式可知$x^*$是问题(P)的KKT点, 乘子$\{u^k/{\mu_k}, k\in K'\}$收敛到乘子$\xi^*\stackrel{\triangle}=u^*/{\mu_*}$, 且$\lim\limits_{k\in K'}\mu_k=\mu_*>0$.证毕.

引理3.7 如果存在无穷迭代指标集$K$使得

$(x^k, H_k, d^k, z_k)\stackrel{k\in K}\longrightarrow (x^*, H_*, d^*, z_*), T_k\equiv T_*, \forall k\in K, $

(3.5)

则$(d^*, z_*)$是问题QP$(x^*, H_*, T_*)$的唯一最优解.

证 根据乘子$\{(\mu_k, u^k)\}_K$的有界性, 在$K$的一个子列中对KKT条件(2.2)-(2.5) 取极限, 结合引理2.1可证.

引理3.8 如果无穷迭代指标集$K$满足(3.5) 式, 且$d^*\neq 0$.则存在$\underline{\lambda}>0$, 使得式(2.7) 和(2.9), 以及当$\varphi(x^k)=0$时,

$g(x^k+\lambda d^k, t)\leq 0, t\in T_*$

(3.6)

对所有$\lambda\in [0, \underline{\lambda}]$和充分大的$k\in K$成立.

证 由于$\lim\limits_{k\in K}d^k=d^*\neq 0$及$d^k\neq0$, 存在$\delta_0>0$, 使得$\|d^k \|\geq \delta_0, \forall k\in K$.由引理2.2(ⅰ)和假设3.4知

$z_k\leq -(d^k)^TH_kd^k\leq - a\|d^k\|^2\leq -a\delta_0^2, \ k\in K.$

(3.7)

分析(2.7):注意到当$\varphi(x^k)>0$时, $\phi(x^k)=\varphi(x^k)=\varphi_k$.利用$\{(x^k, d^k)\}$的有界性, 泰勒展开, (2.5) 式及假设3.4可知

$\quad \phi(x^k+\lambda d^k)-\phi(x^k)+\alpha \lambda(d^k)^TH_kd^k\\ =\max\{g(x^k+\lambda d^k, t), t\in T_k\}-\phi(x^k)+\alpha \lambda(d^k)^TH_kd^k\\ =\max\{g(x^k, t)+\lambda\nabla_xg(x^k, t)^Td^k, t\in T_k\}-\phi(x^k)+\alpha \lambda(d^k)^TH_kd^k+o(\lambda)\\ \leq\max\{g(x^k, t)+\lambda(z_k+\varphi_k-g(x^k, t)), t\in T_k\}-\phi(x^k)+\alpha \lambda(d^k)^TH_kd^k+o(\lambda)\\ \leq(1-\lambda)\max\{g(x^k, t), t\in T_k\}+\lambda(z_k+\varphi_k)-\phi(x^k)-\alpha\lambda z_k+o(\lambda)\\ =(1-\lambda)\phi(x^k)+\lambda(z_k+\varphi_k)-\phi(x^k)-\alpha \lambda z_k+o(\lambda)\\ =(1-\alpha)\lambda z_k+o(\lambda)\\ \leq (1-\alpha)\lambda a\delta_0^2+o(\lambda)\leq 0, $

对$k\in K$和充分小的$\lambda>0$成立.

分析(2.9):注意到, 此时$\varphi(x^k)=0$, 即$\varphi_k=0$.由$\{(x^k, d^k)\}$的有界性, 利用泰勒展开, 引理2.2(ⅰ)及假设3.4可知, 对$k\in K$和充分小的$\lambda>0$, 有

$\quad f(x^k+\lambda d^k)-f(x^k)+\alpha \lambda(d^k)^TH_kd^k\\ =t\nabla f(x^k)^Td^k+\alpha \lambda(d^k)^TH_kd^k+o(\lambda)\\ \leq \lambda(z_k+\gamma\varphi_k)-\alpha \lambda z_k+o(\lambda)\\ \leq(1-\alpha)\lambda z_k+o(\lambda)\\ \leq-(1-\alpha)\lambda a\delta_0^2\leq 0.$

同理, 可分析(3.6) 式成立.综上可知, 存在$\underline{\lambda}>0$使得式(2.7) 和(2.9) 及(3.6) 对所有$\lambda\in [0, \underline{\lambda}]$和充分大的$k\in K$成立.证毕.

引理3.9 $\lim\inf\limits_{k} v^k=0$.

证 反证法.假设$v^*\stackrel{\triangle}=\lim\inf\limits_{k}v^k>0.$由引理3.4和3.5, 假设2.1, 3.3和3.4, 不失一般性, 假设存在无限子集$K$使得

$ (x^k, d^k, z_k, \varphi_k, H_k, v^k; d^{k+1}, z_{k+1}, v^{k+1})\stackrel{K}\longrightarrow (x^*, d^*, z_*, \varphi_*, H_*, v^*; d_+^*, z_+^*, v_+^*), \\ T_k\equiv\hat T, \ T_k^b\equiv\hat T^b, T_{k+1}\equiv\hat{T}_+, \ \forall k\in K. $

由$T_k^b$的定义知$T_k^b\subseteq T_k$, 结合KKT条件(2.2)-(2.5) 可知, QP$(x^k, H_k, T_k)$的解$(d^k, z_k)$也是QP $(x^k, H_k, T_k^b)$的KKT点.进一步由引理2.1解的唯一性和引理3.7可得, $(d^*, z_*)$是QP$(x^*, H_*, \hat T^b)$的唯一解.

由$v^k\stackrel{K}\rightarrow v^*>0$, 引理2.2(ⅰ)及$z_k\leq 0$可知, $d^*\not=0, z_*<0$.根据引理3.4(ⅱ)及$d^*\neq 0$, 有$\lambda_k\stackrel{k\in K}\longrightarrow 0$.不失一般性, 假设对所有的$k\in K$, 有$\lambda_k<\beta\min\{\varrho, \underline{\lambda}\}$, 其中$\varrho, \beta$见算法A, $\underline{\lambda}$见引理3.8. $\lambda_k<\varrho<1$说明算法A步骤2中的线搜索在点$\bar{x}^{k+1}=x^k+\frac{\lambda_k}{\beta}d^k$不能完全满足.又$d^*\not=0$, 由引理3.8可知(2.7) 和(2.9) 式在点$\bar{x}^{k+1}$对充分大的$k\in K$总成立.因此, 对充分大的$k\in K$, 线搜索(2.10) 在点$\bar{x}^{k+1}$被违背.不失一般性, 不妨设存在指标$\bar{t}_k\in T_0^+(\bar{x}_{k+1})$, 使得$g(\bar{x}^{k+1}, \bar{t}_k)>0, \ \bar t_k\equiv\bar t, \forall k\in K.$

注意到$d^*\neq 0$和$\lambda_k/\beta<\underline{\lambda}$, 由引理3.8知$\bar t\notin\hat T\supseteq \hat T^b$.又$\lambda_k<\varrho\ll1$, 由算法步骤3(ⅲ)得$H_{k+1}=H_k$.因此$(d^{k+1}, z_{k+1})$是QP$(x^{k+1}, H_{k}, T_{k+1})$的解.由算法步骤3(ⅱ)知, $\hat T_+\supseteq\hat T^b\cup\{\bar{t}\}\supset\hat T^b$.由引理3.4(ⅱ), 可知$x^{k+1}\stackrel{K}\rightarrow x^*$, 易推得$(d^*_+, z^*_+)$是QP$(x^*, $ $ H_*, \hat{T}_+)$的最优解.既然$g(\bar{x}^{k+1}, \bar{t})>0$和$g(x^{k+1}, \bar{t})\leq 0$, 由泰勒展开可得

$0<g(\bar{x}^{k+1}, \bar{t})-g(x^{k+1}, \bar{t}) =\lambda_k(\frac{1}{\beta}-1)\nabla_x g(x^k, \bar t)^Td^k+o(\lambda_k), k\in K.$

考虑到$\beta\in(0, 1)$和$\lambda_k>0$, 不等式两边同除以$\lambda_k$, 在$k\in K$中取极限可得, $\nabla_x g(x^*, \bar{t})^Td^*\geq 0$.由引理3.4(ⅱ)知$(x^{k+1}, \bar{x}^{k+1})\stackrel{k\in K}\longrightarrow (x^*, x^*)$.注意到$\lambda_k\stackrel{k\in K}\longrightarrow 0$, 对$g(\bar{x}^{k+1}, \bar{t})>0$和$g(x^{k+1}, \bar{t})\leq 0$分别取极限可得$g(x^*, \bar{t})=0$.又$z_*<0, \varphi(x^*)=0$, 故$(d^*, z_*)$对QP$(x^*, H_*, \hat{T}_+)$是不可行的.又知$(d^*, z_*)$和$(d_+^*, z_+^*)$分别是QP$(x^*, H_*, \hat T^b)$和QP$(x^*, $ $H_*, \hat{T}_+)$的最优解, $\hat T^b\subset\hat T_+$, 由引理2.1(ⅰ)及$v^k$的定义可知$v^*_+<v^*$, 这与$v^*=\lim\inf\limits_{k}v^k$及$v^{k+1}\stackrel{k\in K}\longrightarrow v_+^*$矛盾.证毕.

定理3.1 存在$\{x^k\}$的聚点$x^*$是问题${\rm SIP}_q$ (P)的KKT点.称算法A具有弱全局收敛性.

证 由引理3.9知$\lim\inf\limits_{k} v^k=0$, 从而存在$K$使得$v^k\stackrel{K}\rightarrow 0$, 进而由引理3.6(ⅱ)有$d^k\stackrel{K}\rightarrow 0$, 于是由引理3.6(ⅲ)知$\{x^k\}_K$的任意聚点都是问题(P)的KKT点.证毕.

本节利用文献[13]中的算例$\verb"oet_1"$, $\verb"oet_2"$, $\verb"oet_3"$, $\verb"het_z"$及文献[14]中的$\verb"cw_2"$, $\verb"cw_3"$及$\verb"cw_5"$来验证算法A的数值效果.数值代码由MATLAB 2009A编写执行.在测试中, 取$l=100$, 故$|T|=101$.置初始阵$H_0$为单位阵, $H_k$的修正公式见文献[16]中的BFGS公式.

算法中的各参数设置为: $\alpha=0.4, \; \beta=0.6, \; \; \gamma=2, \varrho=10^{-3}.$算法终止准则为$\|d^k\|\leq10^{-4}$或$|z_k|\leq10^{-4}$. 表 4.1中Ni表示算法的迭代次数(若初始点不可行, 则该列前面一个加数表示可行域外的迭代次数, 后面一个加数表示可行域内的迭代次数); $x^*$和$f(x^*)$为算法终止时的$T_k$中的近似最优解及其目标函数值; $\verb"objective"$表示文献[15]中相应问题的最优目标值.数值试验结果表明算法A是有效的.