该文考虑求解如下非线性一般约束极大极小优化问题

(1.1) $ \begin{equation} \min \{F(x)|\ f_j(x)\leq 0, \; j\in J_1;\ f_j(x) = 0, \; j\in J_2\}, \end{equation} $

其中$ F(x) = \max\{f_j(x), \; j\in I\} $, $ I = \{1, 2, \cdots, l\} $, $ J_1 = \{1, 2, \cdots, m'\}, $$ J_2 = \{m'+1, m'+2, $$ \cdots, m'+m\}, $函数$ f_j(x)(j\in I\cup J_1\cup J_2):\mathbb{R}^n\rightarrow \mathbb{R} $均为光滑实值函数.许多决策、金融、工程管理、经济问题都可描述为极大极小问题.然而,其目标函数的非光滑性使之不能利用光滑优化的算法直接求解,故其理论与数值方法的研究较光滑优化困难.但是,通过引入人工变量将原问题等价转化为带有不等式约束光滑优化问题,从而可以用许多经典的光滑优化方法如序列二次规划法^[1-3]、信赖域法^[4-5]、牛顿法^[6]和内点法^[7]等方法来求解.

另一方面,半罚函数方法是将带有等式约束优化问题等价地转化为只带有不等式约束问题进行求解,且此方法具有许多好的性质和应用^[8-10].因此,将问题(1.1)等价地转化为如下半罚问题

(1.2) $ \begin{equation} \min \bigg\{F(x;c)\triangleq F(x)-c\sum\limits_{j\in J_2}f_j(x)|\ f_j(x)\leq 0, \; j\in J_1;\ f_j(x)\leq0, \; j\in J_2 \bigg\}, \end{equation} $

其中半罚参数$ c $充分大,用于强迫不等式约束优化问题(1.2)的解落入原问题(1.1)的可行域,从而通过研究问题(1.2)获得问题(1.1)的解,在一定约束规格下,且当$ c $足够大,问题(1.2)和问题(1.1)的稳定点是等价的.

以Rosen梯度投影法^[11-12]为基础的(广义)梯度投影型算法是一类典型的方法.该类算法具有良好的收敛性,且对中小型问题数值表现良好,引起了诸多的关注^{[10, 13-16]}.文献[14]对不等式约束问题的广义梯度投影算法进行了较为详尽的研究.文献[15]和[16]分别提出了求解无约束和不等式约束极大极小问题的广义梯度投影算法,且论证了算法的收敛性质.

该文借鉴半罚函数思想,提出了一个求解带有不等式和等式约束极大极小优化问题的广义梯度投影算法.算法构造了一个新型的最优识别控制函数,在每一次迭代中,搜索方向由一个广义梯度投影显示公式产生.在适当的假设条件下,算法具有全局收敛性和强收敛性.最后,初步数值试验验证了算法的有效性.

为便于讨论,记问题(1.1)和(1.2)的可行集分别为$ X $和$ \tilde{X} $,并引入如下记号:

$ X = \{x\in \mathbb{R}^n:\ f_j(x)\leq 0, \; j\in J_1, \ \ f_j(x) = 0, \; j\in J_2\}, \ \tilde{X} = \{x\in \mathbb{R}^n:\ f_j(x)\leq 0, \; j\in J\}, $

$ J = J_1\cup J_2, \ I(x): = \{j\in I: f_j(x) = F(x)\}, \; J(x): = \{j\in J: f_j(x) = 0\}. $

类似于其他投影型算法,如文献[10, 13-16],本文亦需线性无关假设.

假设A1  函数$ f_j(x)(j \in {I\cup J}) $均一阶连续可微,且对于任意$ x\in \tilde{X } $,存在$ j_x \in I(x) $使得向量组$ \{\nabla f_j(x)-\nabla f_{j_x}(x), \ j\in I(x)\backslash\{j_x\}; \; \nabla f_j(x), j\in J(x)\} $线性无关.

假设A1等价于下面条件:

假设A1-1  任意$ t\in I(x), $向量组$ \{\nabla f_j(x)-\nabla f_t(x), \; j\in I(x)\backslash\{t\}; \; \nabla f_j(x), j\in J(x)\} $线性无关.

为叙述方便,对于给定的迭代点$ x^k\in \tilde{X} $及适当的常数$ \varepsilon, \; \delta > 0 $,本文使用以下记号:

(2.1) $ \begin{equation} I_k: = I(x^k, \varepsilon) = \{j\in I: -\varepsilon\leq f_j^k-F^k\leq 0\}, \ J_k: = J(x^k, \delta) = \{j\in J_1: -\delta\leq f_j^k\leq 0\}, \end{equation} $

(2.2) $ \begin{equation} F^k: = F(x^k), \; f_j^k: = f_j(x^k), \; g_j^k: = \nabla f_j(x^k), \; j \in I\cup J, l_k\in I(x^k), \; I_k^0: = I_k\backslash\{l_k\}, \end{equation} $

其中$ l_k \in I(x^k) $理论上可以任取,但为便于计算,可取$ l_k: = l_{x^k} = \min\{j: j\in I(x^k)\}. $

对于问题(1.1),其稳定点最优性条件为

(2.3) $ \begin{equation} \left\{\begin{array} {l} \sum\limits_{j\in I_k}\lambda_j^k g_j^k+\sum\limits_{j\in J_k\cup{J_2}}\lambda_j^k g_j^k = 0;\; \sum\limits_{j\in I_k}\lambda_j^k = 1, \lambda_j^k\geq0, \; \lambda_j^k(f_j^k-F^k) = 0, \ j \in I_k;\\ \lambda_j^k\geq0, \; \lambda_j^kf_j^k = 0, \ f_j^k\leq0, \ j \in J_k;\ f_j^k = 0, \ j\in J_2, \end{array}\right. \end{equation} $

当$ j\in (I\backslash{I_k})\cup(J\backslash{J_k}) $时, $ \lambda_j^k = 0 $.由(2.3)式易得

(2.4) $ \begin{equation} \left\{ \begin{array} {ll} \sum\limits_{j\in I_k^0}\lambda_j^k(g_j^k-g_{l_k}^k)+\sum\limits_{j\in J_k}\lambda_j^kg_j^k+\sum\limits_{j\in J_2} (\lambda_j^k+c_k)g_j^k = -(g_{l_k}^k-c_k\sum\limits_{j\in J_2} g_j^k);\\ \lambda_{l_k}^k = 1-\sum\limits_{j\in I_k^0}\lambda_j^k\geq 0;\\ \lambda_j^k\geq0, \; \lambda_j^k(f_j^k-F^k) = 0, \ \; j \in I_k^0;\\ \lambda_j^k\geq0, \; \lambda_j^kf_j^k = 0, \ f_j^k\leq0, \ j \in J_k;\ (\lambda_j^k+c_k)f_j^k = 0, \ f_j^k = 0, \ j\in J_2. \end{array}\right. \end{equation} $

为检验当前迭代点$ x^k $是否满足最优性条件(2.3),定义广义梯度投影矩阵

(2.5) $ \begin{eqnarray} P_k: = E_n-N_k Q_k, \end{eqnarray} $

其中$ E_n $是$ n $阶单位阵,对于$ p > 0 $,矩阵

(2.6) $ \begin{equation} N_k: = (g_j^k-g_{l_k}^k, \; j \in I_k^0;\; g_{j}^k, \; j \in J_k\cup J_2), \; Q_k: = (N_k^T N_k+D_k)^{-1}N_k^T, \end{equation} $

(2.7) $ \begin{equation} L_k: = I_k^0\cup{J_k}\cup{J_2}, \ D_k: = {\rm diag}(D_{j}^{k}, \; j\in {L_k}), \; D_j^k: = \left\{\begin{array}{ll}(F^k-f_j^k)^p, & j\in I_k^0;\\ (-f_j^k)^p, & j\in J_k;\\ 0, &j\in J_2. \end{array}\right. \end{equation} $

当$ (x^k, \; \lambda_{L_k}^k) $为问题(1.1)的稳定点对时,由(2.4)易得如下关系式:

$ \; N_k^T N_k\lambda_{L_k}^k = -N_k^T(g_{l_k}^k-c_k\sum\limits_{j\in J_2} g_j^k), \; D_k\lambda_{L_k}^k = 0. $

进一步可得

(2.8) $ \begin{equation} \left\{\begin{array}{ll} (N_k^T N_k+D_k)\lambda_{L_k}^k = -N_k^T(g_{l_k}^k-c_k\sum\limits_{j\in J_2} g_j^k), \\ \lambda^k_{L_k} = -Q_k(g_{l_k}^k-c_k\sum\limits_{j\in J_2} g_j^k), \ \tilde{\lambda}^k_{L_k} = -Q_kg_{l_k}^k.\end{array}\right. \end{equation} $

由(2.4)和(2.8)式,易知

(2.9) $ \begin{equation} \lambda^k_{j} = \tilde{\lambda}^k_{j}, \ j\in I_k^0\cup J_k;\ \lambda^k_{j} = \tilde{\lambda}^k_{j}+c_k, \ j\in J_2. \end{equation} $

基于以上分析,引入如下最优识别控制函数:

(2.10) $ \begin{equation} \rho_k: = \frac{\|P_kg_{l_k}^k\|^2+\omega_{k}+\bar\omega_k^2}{1+\|\mu^k_{L_k}\|_1}, \end{equation} $

其中

(2.11) $ \begin{equation} \mu^k_{L_k}: = -Q_k(g_{l_k}^k-c_k\sum\limits_{j\in J_2} g_j^k), \ \tilde{\mu}^{k}_{L_k}: = -Q_{k}g_{l_k}^k, \ \ \mu_{l_k}^k: = 1-\sum\limits_{j\in I_k^0}\tilde{\mu}_j^k, \end{equation} $

(2.12) $ \begin{equation} \omega_{k}: = \sum\limits_{j \in I_k^0\cup J_k}\max\{-\tilde{\mu}_{j}^{k}, \tilde{\mu}_{j}^{k}D_{j}^{k}\}+\sum\limits_{j \in J_2}{\mu}_{j}^{k}(-f_{j}^{k})^p, \ \ \; \bar\omega_k: = \max\{-\mu_{l_k}^k, 0\}. \end{equation} $

为说明以上各量的适定性及性质,给出以下引理.

引理2.1  设假设A1成立,有

(ⅰ)矩阵$ (N_k^T N_k+D_k) $正定;若$ x^k\rightarrow x^\ast, \; N_k\rightarrow N_\ast, \; D_k\rightarrow D_\ast, $则其极限矩阵$ (N_\ast^T N_\ast+D_\ast) $也正定;

(ⅱ) $ N_k^T P_k = D_kQ_k, \ \ N_k^T Q_k^T = E_{|L_k|}-D_k(N_k^T N_k+D_k)^{-1}; $

(ⅲ) $ (g_{l_k}^k)^{T}P_{k}g_{l_k}^k = \|P_{k}g_{l_k}^k\|^2+\sum\limits_{j\in L_k}(\tilde{\mu}_j^k)^{2}D_j^k; $

(ⅳ)如$ c_k > |\tilde{\mu}_j^k|, \ j\in J_2 $,则$ x^k $是问题$ (1.2) $稳定点$ \Longleftrightarrow $$ x^k $是问题$ (1.1) $的稳定点$ \Longleftrightarrow \rho_k = 0 $.

引理2.1(ⅰ)–(ⅲ)的证明可参照文献[14]中的引理1.1.9和文献[16]中的引理1,引理2.1(ⅳ)的证明可参照文献[9]中的引理2.2.

由以上引理知,若当前迭代点$ x^k $不是问题(1.1)的稳定点,有$ \rho_k > 0 $.进而,构造如下搜索方向

(2.13) $ \begin{equation} d^k = \rho_k^\xi\{-P_kg_{l_k}^k+Q_k^T v^k_{L_k}\}, \end{equation} $

其中参数$ \xi\geq0 $,向量$ v^k_{L_k} = (v_j^k-\rho_k, \ j\in L_k), v_j^k $构造如下:

(2.14) $ \begin{equation} v_{j}^{k} = \left\{\begin{array}{ll}-1+\bar\omega_k, & \; \tilde{\mu}_{j}^{k}<0, \; j \in I_k^0;\\ D_{j}^{k}+\bar\omega_k, & \; \tilde{\mu}_{j}^{k}\geq 0, \; j \in I_k^0, \end{array}\right. v_{j}^{k} = \left\{\begin{array}{ll}-1, & \; \tilde{\mu}_{j}^{k}<0, \; j \in J_k;\\ D_{j}^{k}, & \; \tilde{\mu}_{j}^{k}\geq 0, \; j \in J_k, \end{array}\right. v_{j}^{k} = (-f_j^k)^p, \ j\in J_2. \end{equation} $

基于引理2.1,接下来分析搜索方向$ d^k $的可行下降性.

引理2.2  设假设A1成立,方向$ d^k $满足

(ⅰ) $ {(g_{l_k}^k-c_k\sum\limits_{j\in J_2} g_j^k)}^{T}d^k\leq-\rho_k^{\xi}\bar{\omega}_k-\rho_k^{1+\xi} $;

(ⅱ) $ (g_{j}^k-c_k\sum\limits_{j\in J_2} g_j^k)^{T}d^k\leq-\rho_k^{1+\xi}, \; \forall\; j\in I(x^k)\backslash\{l_k\} $;

(ⅲ) $ (g_{j}^k)^{T}d^k\leq-\rho_k^{1+\xi}, \; \forall\; j\in {J(x^k)} $.

证   (ⅰ)首先,由(2.11)–(2.14)式, (2.9)式及引理2.1(ⅲ),有

$ \begin{eqnarray*} &&{(g_{l_k}^k-c_k\sum\limits_{j\in J_2} g_j^k)}^{T}d^k\\ & = &\rho_k^\xi\{-(g_{l_k}^k)^TP_kg_{l_k}^k+(Q_kg_{l_k}^k)^Tv_{L_k}^k+c_k\sum\limits_{j\in J_2}( g_j^k)^TP_kg_{l_k}^k-c_k\sum\limits_{j\in J_2} (g_j^k)^TQ_k^Tv_{L_k}^k\}\\ & = &\rho_k^\xi \{-\|P_{k}g_{l_k}^k\|^2-\sum\limits_{j\in L_k}(\tilde{\mu}_j^k)^{2}D_j^k -(\tilde{\mu}_{L_k}^k)^Tv_{L_k}^k-c_k\sum\limits_{j\in J_2} (g_j^k)^TQ_k^Tv_{L_k}^k\}\\ & = &\rho_k^\xi\{-\|P_{k}g_{l_k}^k\|^2-\sum\limits_{j\in L_k}(\tilde{\mu}_j^k)^{2}D_j^k -\sum\limits_{\tilde{\mu}_j^k<0, j\in I_k^0}\tilde{\mu}_j^k(\bar\omega_k-1)-\sum\limits_{\tilde{\mu}_j^k\geq 0, j\in I_k^0}\tilde{\mu}_j^k(\bar{\omega}_k+D_j^k)\\ &&-\sum\limits_{\tilde{\mu}_j^k<0, j\in J_k}(-\tilde{\mu}_j^k)-\sum\limits_{\tilde{\mu}_j^k\geq0, j\in J_k}\tilde{\mu}_j^kD_j^k-\sum\limits_{j\in J_2}(\tilde{\mu}_j^k+c_k)(-f_j^k)^p\\ &&+\rho_k(\sum\limits_{j\in I_k^0\cup J_k}\tilde{\mu}_j^k+\sum\limits_{j\in J_2}(\tilde{\mu}_j^k+c_k))\}\\ &\leq&\rho_k^\xi\{-\|P_{k}g_{l_k}^k\|^2 -{\omega}_k-\bar{\omega}_k\sum\limits_{j\in I_k^0}\tilde{\mu}_j^k+\rho_k\sum\limits_{j\in L_k}|\mu_j^k|\}. \end{eqnarray*} $

另外,由$ \mu_{l_k}^{k} $的定义可得$ \bar\omega_k\sum\limits_{j\in I_k^0}\tilde{\mu}_j^k = \bar\omega_k+\bar\omega_k(-\mu_{l_k}^{k}). $若$ \mu_{l_k}^k\geq0 $,则$ \bar\omega_k = 0 $, $ \bar\omega_k(-\mu_{l_k}^{k}) = 0 = \bar\omega_k^2 $;若$ \mu_{l_k}^k < 0 $,则$ \bar\omega_k = -\mu_{l_k}^{k} $, $ \bar\omega_k(-\mu_{l_k}^{k}) = \bar\omega_k^2 $.因此, $ \bar\omega_k\sum\limits_{j\in I_k^0}\tilde{\mu}_j^k = \bar\omega_k+\bar\omega_k^2 $恒成立,于是,结合(2.10)式,有

(2.15) $ \begin{eqnarray} {(g_{l_k}^k-c_k\sum\limits_{j\in J_2} g_j^k)}^{T}d^k &\leq&\rho_k^\xi\{-\|P_{k}g_{l_k}^k\|^2-\omega_k-\bar{\omega}_k-\bar{\omega}_k^2+\rho_k\|\mu_{L_k}^k\|_1\} \\ & = &-\rho_k^{\xi}\bar{\omega}_k-\rho_k^{1+\xi}. \end{eqnarray} $

(ⅱ)由(2.13)式及引理2.1(ⅱ)有

(2.16) $ \begin{eqnarray} N_k^Td^k& = &\rho_k^\xi \{-N_k^TP_kg_{l_k}^k+N_k^TQ_k^Tv_{L_k}^k\} \\ & = &\rho_k^\xi\{-D_k Q_kg_{l_k}^k+v_{L_k}^k-D_k(N_k^TN_k+D_k)^{-1}v_{L_k}^k\}. \end{eqnarray} $

当$ j\in(I(x^k)\backslash\{l_k\})\subseteq I_k^0 $时,有$ D_j^k = 0. $由(2.16)式有$ (g_j^k-g_{l_k}^k)^Td^k = \rho_k^\xi v_j^k -\rho_k^{1+\xi}. $再结合(2.14)式及结论(ⅰ),可得

$ \begin{eqnarray*} (g_j^k-c_k\sum\limits_{j\in J_2} g_j^k)^Td^k& = &(g_{l_k}^k-c_k\sum\limits_{j\in J_2} g_j^k)^Td^k+\rho_k^\xi v_j^k-\rho_k^{1+\xi}\\ &\leq&-\rho_k^{1+\xi}-\rho_k^{\xi}\bar{\omega}_k+\rho_k^{\xi}\bar{\omega}_k-\rho_k^{1+\xi}\leq-\rho_k^{1+\xi}. \end{eqnarray*} $

(ⅲ)当$ j\in J(x^k)\subseteq J_k\cup J_2 $时,有$ D_j^k = 0. $由(2.16)和(2.14)式有$ (g_{j}^k)^Td^k = \rho_k^\xi v_j^k - \rho_k^{1+\xi}\leq-\rho_k^{1+\xi}. $

基于以上分析,下面给出算法的具体步骤.

算法A

步骤0 (初始化)  选初始点$ x^0\in \tilde{X} $,参数:$ \alpha, \beta\in (0, 1), \; \varepsilon, \delta, p, c_0, \gamma, \gamma_0 > 0, \; \xi\geq0 $.置$ k: = 0 $.

步骤1 (修正罚参数$ c_k $)

(2.17) $ \begin{equation} c_{k} = \left\{\begin{array}{ll}\max\{s_k, \ c_{k-1}+\gamma\}, & \hbox{如}\ s_k>c_{k-1};\\ c_{k-1}, & \hbox{如}\ s_k\leq c_{k-1}, \end{array}\right.\; s_k = \max\{|\tilde{\mu}_j^k|, \ j\in J_2\}+\gamma_0. \end{equation} $

步骤2 (最优识别)  对于迭代点$ x^k $,计算投影矩阵$ P_k $和识别函数$ \rho_k $,若$ \rho_k = 0 $,则$ x^k $为问题(1.1)的稳定点,停止;否则,按(2.13)–(2.14)式计算搜索方向$ d^k $,并转入步骤3.

步骤3 (线搜索)  计算$ \{1, \beta, \beta^2, \cdots\} $中满足以下不等式(2.18)和(2.19)的最大值$ t_k $.

(2.18) $ \begin{equation} F(x^k+td^k;c_k)\leq F(x^k;c_k)-\alpha t \rho_k^{1+\xi}, \end{equation} $

(2.19) $ \begin{equation} f_j(x^k+td^k)\leq0, \; \forall\; {j\in J}. \end{equation} $

步骤4 (更新)  令$ x^{k+1} = x^k+t_kd^k $,置$ k: = k+1 $,返回步骤1.

注2.1  由引理2.2知,易证(2.18)–(2.19)式对于充分小的正数$ t $恒成立,从而步骤3的线搜索是可以执行的,故上述算法A是适定的.

本节分析算法A的全局收敛性和强收敛性.下面假设算法A产生无穷点列$ \{x^k\} $,往证其任一聚点$ x^\ast $都是问题(1.1)的稳定点,注意到指标集$ I_k, \; J_k $及$ l_k $的有限选取性,不妨假设存在无穷子列$ {\cal K} $(必要时再取$ {\cal K} $的一个子列),使得

(3.1) $ \begin{equation} x^k\stackrel{{\cal K}}{\rightarrow} x^\ast, \ I_k\equiv I_\ast, \; J_k\equiv J_\ast, \; l_k\equiv l_\ast, \; I_k^0\equiv I_{\ast}^0: = \{I_\ast\}\backslash{l_\ast}, \; L_k\equiv L_\ast: = {I_\ast^0\cup{J_\ast}\cup{J_2}}, \; \forall\ k\in {\cal K}. \end{equation} $

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

引理3.1  设假设A1和A2成立,则存在正整数$ k_0 $,使得对于任意的$ k\geq k_0 $,有$ c_k \equiv \bar c $成立.

证明可参考文献[9]中的引理3.1.根据引理3.1,下文假设$ c_k = \bar c $恒成立,定义

(3.2) $ \begin{equation} D_j^{\ast } = \left\{\begin{array}{lll}(F(x^\ast)-f_j(x^\ast))^p, &\;\mbox{ $j\in I_\ast^0$};\\ (-f_j(x^\ast))^p , &\;\mbox{ $ j\in J_\ast$}; \\0 , &\;\mbox{ $ j\in J_2$}, \end{array} \right.~~ D_\ast = {\rm diag}(D_{j}^{\ast}, \; j\in L_\ast), \end{equation} $

(3.3) $ \begin{equation} N_\ast = (\nabla f_j(x^\ast)-\nabla f_{l_\ast}(x^\ast), \ j\in I_{\ast}^0;\; \nabla f_j(x^\ast), \ j\in J_\ast\cup J_2), \ Q_\ast = (N_\ast^T N_\ast+D_\ast)^{-1}N_\ast^T, \end{equation} $

(3.4) $ \begin{equation} P_\ast = E_{n}-N_\ast Q_\ast, \ \tilde{\mu}_{L_\ast}^\ast = (\tilde{\mu}_j^\ast, \; j\in L_\ast) = -Q_\ast \nabla {f_{l_\ast}(x^\ast)}, \ \mu_{l_\ast}^\ast = 1-\sum\limits_{j\in I^0_\ast}\tilde{\mu}_j^\ast, \end{equation} $

(3.5) $ \begin{equation} \bar{\omega}_\ast = \max\{-\mu_{l_\ast}^\ast, \; 0\}, \ \mu^*_{L_*} = -Q_*(\nabla f_{l_\ast}(x^\ast)-\bar{c}\sum\limits_{j\in J_2} \nabla f_j(x^\ast)), \end{equation} $

(3.6) $ \begin{equation} \omega_\ast = \sum\limits_{j\in I_\ast^0\cup J_*}\max\{-\tilde{\mu}_j^\ast, \; \tilde{\mu}_j^\ast D_j^{\ast}\}+\sum\limits_{j\in J_2} \mu_j^*(-f_j(x^\ast))^p, \ \ \rho_{\ast} = \frac{\|P_{\ast}\nabla f_{l_\ast}(x^\ast)\|^2+\omega_\ast+\bar{\omega}_\ast^2}{1+\|\mu^*_{L_*}\|_1}. \end{equation} $

于是, $ (F(x^k; c_k), \; D_k, \; \rho_k)\rightarrow(F(x^\ast; \bar{c}), \; D_\ast, \; \rho_\ast) $.另外,由引理2.1可知,矩阵$ (N_\ast^T N_\ast+D_\ast) $正定,故序列$ \{v^k\}_{{\cal K}} $和$ \{d^k\}_{{\cal K}} $有界.

引理3.2  设假设A1和A2成立,如果$ x^\ast $不是问题$ (1.1) $的稳定点,则$ \rho_\ast > 0 $,进而当$ k\in {\cal K} $充分大时, $ \rho_k\geq0.5\rho_\ast $,且$ \bar{t} = \mathrm{inf}\{t_k, \ k\in {\cal K}\} > 0. $

证  首先,当$ x^\ast $不是问题(1.1)的稳定点时,类似于引理2.1 (iv)的分析,易证$ \rho_\ast > 0 $,因$ \bar c > |\tilde{\mu}_j^*|, \ \forall\ j\in J_2 $.进而$ \rho_k\geq0.5\rho_\ast $.为证$ \bar{t} > 0 $,只需证明对于$ {\cal K} $中充分大的$ k $以及充分小的正数$ t $(与$ k $无关),不等式(2.18)和(2.19)成立.

A1.分析不等式(2.18),由$ f_j(x) $的可微性及$ \{{d^k}\}_{{\cal K}} $的有界性,利用Taylor展开式有,记

$ \begin{eqnarray*} F^k(t):& = &F(x^k+td^k;\bar c)-F(x^k;\bar c)+\alpha t\rho_k^{1+\xi}\\ & = &\max\{f_j^k+t(g_j^k)^Td^k-{\bar c}\sum\limits_{j\in J_2}( f_j^k+t(g_j^k)^Td^k)+o(t)-F(x^k;\bar c)+\alpha t \rho_k^{1+\xi}, \ j\in I\}\\ & = & \max\{f_j^k-F^k+t(g_j^k-{\bar c}\sum\limits_{j\in J_2}g_j^k)^Td^k+\alpha t \rho_k^{1+\xi}+o(t), \ j\in I\}. \end{eqnarray*} $

为便于分析,进而记

$ b_{j}^k(t): = f_j^k-F^k+t(g_j^k-{\bar c}\sum\limits_{j\in J_2}g_j^k)^Td^k+\alpha t \rho_k^{1+\xi}+o(t). $

对于$ j\in I $,此时分$ j\notin I(x^*) $及$ j\in I(x^\ast) $两种情况讨论.

A11.当$ j\notin I(x^\ast) $,即$ f_j(x^\ast) < F(x^\ast) $时,有

$ b_{j}^k(t) = f_j^k-F^k+O(t)\leq0.5(f_j(x^\ast)-F(x^\ast))+O(t)\leq0. $

A12.当$ j\in I(x^\ast) $,即$ f_j(x^\ast) = F(x^\ast) $时.由(2.1)式易知, $ k\in {\cal K} $充分大时,恒有$ I(x^\ast)\subseteq I_k, $故$ j\in I_k. $若$ j = l_\ast $,由引理2.2 (ⅰ)有

(3.7) $ \begin{equation} (g_{l_\ast}^k-{\bar c}\sum\limits_{j\in J_2} g_j^k)^{T}d^k\leq-\rho_k^{\xi}\bar{\omega}_k-\rho_k^{1+\xi}\leq-\rho_k^{1+\xi}. \end{equation} $

若$ j\neq l_\ast $, $ D_j^k = (F^k-f_j^k)^p\stackrel{{\cal K}}{\rightarrow}(F(x^\ast)-f_j(x^\ast))^p = 0 $,由引理2.1 (i)知$ (N_k^T N_k+D_k)^{-1}\rightarrow(N_\ast^T N_\ast+D_\ast)^{-1} $,进而由(2.16)式有$ (g_j^k-g_{l_k}^k)^Td^k = \rho_k^\xi v_j^k-\rho_k^{1+\xi}+O(D_j^k). $又由(2.14)式的第一个式子,有$ v_j^k\leq\bar{\omega}_k+O(D_j^k) $,结合(2.15)式,有

(3.8) $ \begin{eqnarray} (g_j^k-{\bar c}\sum\limits_{j\in J_2}g_j^k)^Td^k&\leq& \rho_k^\xi \bar{\omega}_k+(g_{l_k}^k-{\bar c}\sum\limits_{j\in J_2}g_j^k)^Td^k-\rho_k^{1+\xi}+O(D_j^k) \\ &\leq& -2\rho_k^{1+\xi}+O(D_j^k)\leq-\rho_k^{1+\xi}+O(D_j^k). \end{eqnarray} $

因此,对于$ j\in I(x^\ast), $由Taylor展式及(3.7)和(3.8)式有

(3.9) $ \begin{eqnarray} b_{j}^k(t)& = & f_j^k-F^k+t(g_j^k-{\bar c}\sum\limits_{j\in J_2}g_j^k)^Td^k+o(t)+\alpha t \rho_k^{1+\xi} \\ &\leq &-(1-\alpha)t\rho_k^{1+\xi}+o(t) \\ &\leq&-0.5t (1-\alpha)\rho_\ast^{1+\xi}+o(t)\leq 0. \end{eqnarray} $

由A11及A12的分析可知,对于$ {\cal K} $中充分大的$ k $及充分小的正数$ t $ (与$ k $无关),有$ F^k(t)\leq0 $,即不等式(2.18)恒成立.

A2.对于$ j\in J $,类似分$ j\notin J(x^*) $和$ j\in J(x^*) $两种情况讨论.

A21.当$ j\notin J(x^\ast) $,即$ f_j(x^*) < 0 $时,由$ \{{d^k}\}_{{\cal K}} $的有界性及Taylor展式,有

(3.10) $ \begin{equation} f_j(x^k+td^k) = f_j^k+O(t)\leq0.5f_j(x^*)+O(t)\leq0. \end{equation} $

A22.当$ {j\in J(x^\ast)} $,即$ f_j(x^*) = 0 $时,由(2.1)式易知, $ k\in {\cal K} $充分大时,恒有$ J(x^\ast)\subseteq J_k\cup J_2, $故$ j\in J_k\cup J_2 $,进而$ D_j^k = (-f_j^k)^p\stackrel{{\cal K}}{\rightarrow}0 $.因此,由(2.16)式有$ (g_j^k)^Td^k = \rho_k^\xi v_j^k-\rho_k^{1+\xi}+O(D_j^k) $.进而,结合Taylor展式和(2.14)式,可得

$ f_j(x^k+td^k) = f_j^k+t(g_j^k)^Td^k+o(t) \leq f_j^k-t\rho_k^{1+\xi}+tO(D_j^k)+o(t) \leq -0.5t\rho_*^{1+\xi}+o(t)\leq0. $

因此,对于$ {\cal K} $中充分大的$ k $及充分小的正数$ t $ (与$ k $无关),不等式(2.19)恒成立.

综上所述,当$ k\in {\cal K} $充分大时, $ \bar{t} = \mathrm{inf}\{t_k, \ k\in {\cal K}\} > 0 $恒成立.

引理3.3  设假设A1和A2成立,算法A或有限步终止于问题$ (1.1) $的稳定点,或产生无穷点列$ \{x^k\} $,使得$ \{x^k\} $的任一聚点$ x^\ast $都是问题$ (1.1) $的稳定点,即算法A是全局收敛的.

证  因$ c_k\geq s_k > |\tilde{\mu}_j^k| $, $ \forall\ j\in J_2 $,若算法A有限步迭代终止,由算法A步骤2及引理2.1 (ⅳ)知$ x^k $是问题(1.1)的稳定点.下面不妨设算法A产生无穷点列$ \{x^k\} $, $ x^\ast $为其任意一给定的聚点.由$ (2.18) $式易知, $ \{F(x^k; \bar c)\} $是单调下降的.又$ \lim\limits_{k\in {\cal K}}F(x^k; \bar c) = F(x^*; \bar c) $,因此$ \lim\limits_{k\rightarrow\infty}F(x^k; \bar c) = F(x^*; \bar c) $.若$ x^\ast $不是问题$ (1.1) $的稳定点,则由引理3.2及(2.18)式有

$ 0 = \lim\limits_{k\in {\cal K}}(F(x^{k+1};\bar c)-F(x^k;\bar c))\leq\lim\limits_{k\in {\cal K}}(-\alpha t_k\rho_k^{1+\xi}) = -0.5\alpha \bar{t}\rho_\ast^{1+\xi}, $

此与$ \bar{t} > 0 $和$ \rho_\ast > 0 $矛盾.

如下定理进一步分析算法A的强收敛性,其证明可参照文献[15,定理2]类似完成.

引理3.4  设假设A1和A2成立,参数$ \xi > 0 $,则(ⅰ) $ \lim\limits_{k\rightarrow\infty}\|x^{k+1}-x^k\| = 0 $; (ⅱ)若$ \{x^k\} $有孤立聚点$ x^\ast $,则$ \lim\limits_{k\rightarrow\infty}x^k = x^\ast $,即算法是强收敛的.

本部分利用MATLAB R2015a进行编程,计算机配置为Windows 7, Intel(R) Core(TM) CPU 3.30GHz.参数设置为$ \alpha = 0.5, \; \beta = 0.5, \; \varepsilon = 10, \; \delta = 10, \; p = 2, \; c_0 = 2, \; \gamma = 1, \; \gamma_0 = 0.5, \; \xi = 0.01 $,终止准则为$ \rho_k\leq 10^{-5} $.选取文献[2]中的6个算例,并将其数值结果与文献[2]中算法(记为算法JZQM)、文献[1]中算法(记为算法YG)的结果相比较.从数值结果可以看出,三个算法近似最优目标函数值和所需的迭代次数相差甚微,故该文所提出的算法是有效的.

表 1中各个符号含义为:问题序号为文献[2]中的序号; "$ n $":自变量$ x $的维数; "$ l $":目标函数中$ f_j(x) $的个数; "$ {m'} $":不等式约束函数的个数; "$ {m} $":等式约束函数的个数; "$ x^0 $":初始点; "Ni":算法迭代次数; "$ F(x^*) $":算法终止时获得的近似最优目标函数值.