对于问题(1)的近似解x^k∈X，σ_k＞0，正定矩阵B_k=B(x^k)，集合L_k⊆I，为了便于讨论给出以下记号：

本文算法引用了文献[7]提出的共轭投影梯度技术，并采用文献[7]中定义的以下各量：

定义1^[7]  如果函数μ(x)：${\mathbb{R}}$ⁿ$ \longrightarrow $${\mathbb{R}}$^m满足以下条件：

1) μ(x)连续.

2) 当x^*是问题(1)的K-T点时，μ(x^*)为相应的K-T乘子.则称μ(x)为乘子函数.

滤子技术能很好地平衡目标函数和约束条件，对于每次迭代，试探点被接受当且仅当约束违反度函数值或目标函数值相对于当前的滤子集中的点有充分的下降.

本文定义约束违反度函数为

其中

易知h(x)=0的充要条件是保证迭代点x是可行点，所以试探点应该使得约束违反度函数值降低或目标函数值减小.为了保证这两项至少有一项满足，参照文献[1]引入滤子的相关定义.

定义2  称点x¹支配点x²当且仅当

定义3  滤子为具有形式为(h_i，f_i)的点集Z，使得任意点不能被其他点支配，即h(xⁱ)≤h(x^j)或f(xⁱ)≤f(x^j)对所有的i≠j成立.

在实际计算中，为了获得全局收敛性，需要添加一些条件，如文献[1]中定义了一个“包络”来阻止点任意接近滤子.从而有以下滤子准则：

定义4  一个点被滤子接受当且仅当对任意的(h_j，f_j)∈Z有

其中：h_j=h(x^j)；f_j=f(x^j)；0＜γ＜β＜1且γ→0，β→1.

在算法的进程中需要将(h_j，f_j)对添加到滤子中，如果一个点x^k被滤子集Z接受，则令x^k+1=x^k+t_kd^k且滤子按如下的规则更新

其中

事实上，这里“点x被滤子集Z接受”严格上说是将(h_j，f_j)对添加到滤子集中.如果点x^k被滤子集接受或者已在滤子集中，那么满足

的点x也是被滤子接受的.

算法1

步0 (初始化)  给定x⁰∈${\mathbb{R}}$ⁿ，μ(x⁰)∈${\mathbb{R}}$^m，B₀是对称正定矩阵，选择σ₀，ξ，ε，v∈(0，1)，τ∈(2，3)，δ＞2且α₁，α₂，η∈(0，1)，t₀=1，初始化滤子集Z₀，并令k=0.

步1 (有效集L_k)

(a) 令i=0，σ_k，i=σ₀；

(b) 若det(A_k^TA_k)＞σ_k，i，令L_k=L_k，i，i_k=i，转步2，否则转步1(c)，其中：

(c) 令i=i+1，σ_k，i=0.5σ_k，i-1，返回步1(b).

步2 (搜索方向)  通过式(2)-(5)获得d₀^k.若d₀^k=0，则获得一个K-T点，停止.否则，通过式(6)计算d^k.

若

则转步3.否则，转步4.

步3 (滤子准则)  若x^k+t_kd^k不被滤子接受，则令x^k+1=x^k，t_k+1=0.5t_k，k=k+1，转步4.若x^k+t_kd^k被滤子接受，则令x^k+1=x^k+d^k，f_k+1=f(x^k+d^k)，h_k+1=h(x^k+d^k)，并去除那些被x^k+1支配的点，更新滤子集Z_k+1，转步5.

步4 (线搜索)  通过式(7)获得q^k，取$ \left\{ {1, \frac{1}{2}, \frac{1}{4}, \cdots } \right\} $的最大值为λ_k，使其满足

令d^k=q^k，t_k=λ_k.

步5 (迭代更新)  令x^k+1=x^k+t_kd^k，更新正定对称矩阵B_k+1，k=k+1.返回步1.

算法A需要以下理论的支持.

假设A

(A1) 迭代序列{x^k}⊆X非空且位于${\mathbb{R}}$ⁿ中的有界闭凸子集内；

(A2) 对任意的x∈${\mathbb{R}}$ⁿ，向量组{▽c_j(x)，j∈I(x)}是线性无关的；

(A3) ∀k，B_k∈${\mathbb{R}}$ⁿ是一个n阶对称正定矩阵且{B_k}一致有界；

(A4) 目标函数f(x)和约束违反度函数h(x)都是二次连续可微的.

(A5) 存在两个常数0＜a≤b，使得a‖d‖²≤d^TB_kd≤b‖d‖²，∀k，∀d∈${\mathbb{R}}$ⁿ.

由于集合L_k⊆I的有限性，不妨设存在无穷子列K，使得

其中L为一个固定指标集.记A_*，Q_*，P_*，π^*，V^*，d₀^*，d^*，q^*分别为式(3)-(7)中各式在x^*处以B_*代替B(x^*)的相应各量，则A_k→A_*，Q_k→Q_*，P_k→P_*，d₀^k→d₀^*，q^k→q^*，k∈K，k→∞.

引理1  对任意的迭代指标k，算法1步1(b)和步1(c)之间的循环有限步终止.

证  利用反证法.

假设算法在步1(b)和步1(c)之间无限循环，则由算法结构知，

由L_k，i的定义有

又集合I是个有限集，从而对充分大的i有

并定义为L_k^*.令i→∞，则

这与假设(A2)矛盾.

引理2  若假设A满足且迭代点x^k∈X，则有下列结论成立

1) x^k是问题(1)的K-T点当且仅当d₀^k=0.

2) 若x^k不是问题(1)的K-T点，则d^k仍是问题(1)在点x^k处的一个可行下降方向，即有

证  参考文献[7]中定理1的证明.

引理3^[7]  对于算法1产生的序列{x^k}，设x^*是它的任意一个聚点.若x^k+1=x^k+t_kd^k均由步4和步5产生，且x^*不是问题(1)的K-T点，则有

引理4  算法是可执行的.

证  只需证明在假设A成立的前提下，当k充分大时，算法不再执行步4.由算法知，只需证明由步4产生的迭代点也一定能被滤子接受.假设算法不能有限步终止，则有t_k→0，k→∞，且新的迭代点x^k+1=x^k+t_kq^k不能被滤子接受.下面分两种情况讨论.

1) 若h_k=0.由h(x)的定义可得，

由引理1知，

结合t_k→0，k→∞，则存在一个常数β，使得

再由式(14)和引理2知

故

由式(16)-(17)可知新的迭代点x^k+1=x^k+t_kq^k能被滤子和x^k接受.矛盾.

2) 若h_k≠0.类似于情况(1)，可得h_k+1≤βh_k.由于x^k被滤子接受，所以有

由假设迭代点x^k+1=x^k+t_kq^k不能被滤子接受，则有

和

对于点x^k，若h_k≤βh_i成立，则由引理1知，

结合t_k→0，k→∞，则存在一个常数β，使得

这与式(18)矛盾.

对于点x^k，若f_k≤f_j-βh_j成立，则由引理1知，

结合t_k→0，k→∞，则存在一个常数β，使得

这与式(19)矛盾.

综上分析，当k充分大时，算法不再执行步4，即算法是有效的.

引理5^[9]  考虑{x^k}是进入滤子集的无穷序列，与其对应的h(x^k)＞0且{f(x^k)}有下界，则

引理6^[9]  1)如果有无限多个点被添加到滤子集中，则

2) 如果有有限多个点被添加到滤子集中，则存在一个k₁，使得当k＞k₁时，有

引理7  按式(6)计算的主方向d^k满足‖d^k‖~‖d₀^k‖，‖d₁^k‖=O(‖d₀^k‖²).

证  由算法1步4中λ_k的取法易知，当k充分大时，有λ_k≡1，此时x^k+1=x^k+d^k.当j∈I_*时有

而

所以，

从而当k充分大时有，

定理1  在假设A成立的前提下，算法1或有限次迭代终止于问题(1)的一个K-T点x^k，或产生一个无穷迭代序列{x^k}，使得它的任意一个聚点x^*是问题(1)的K-T点.

证  若算法1终止于点x^k，则d₀^k=0.故由引理2可知迭代点x^k是问题(1)的K-T点.即证明了定理1的前半部分.下面假设x^*为无穷迭代序列{x^k}的任意一个聚点，不妨设当k→∞时有x^k→x^*，k∈K，其中K为无穷指标集.下面分情况讨论.

1) 若存在一个无穷序列K₁⊆K，使得迭代点x^k+1=x^k+t_kd^k均由算法1步2和步3产生.结合引理5、引理6知$ \mathop {\lim }\limits_{k \to \infty } $h(x^k)=0.若$ \mathop {\lim }\limits_{k \in {K_1}, k \to \infty } $d^k‖=0，则易知x^*是一个K-T点.由$ \mathop {\lim }\limits_{k \to \infty } h\left( {{\mathit{\boldsymbol{x}}^k}} \right) = 0 $和假设A中的(A5)可设存在一个k₀，使得当k＞k₀，k∈K₁，有$ h\left( {{\mathit{\boldsymbol{x}}^k}} \right) \le \frac{{a{\varepsilon ^2}}}{{2M}} \le \frac{{a{{\left\| {{\mathit{\boldsymbol{d}}^k}} \right\|}^2}}}{{2M}} \le \frac{{{{\left( {{\mathit{\boldsymbol{d}}^k}} \right)}^{\rm{T}}}{\mathit{\boldsymbol{B}}_k}{\mathit{\boldsymbol{d}}^k}}}{{2M}} $，结合K-T条件，对所有的k＞k₀，k∈K₁有

其中ω_k为拉格朗日乘子.从而，

因此

再结合引理7可得

而

因此，根据引理2的证明，可证x^*是问题(1)的一个K-T点.

2) 若存在一个无穷序列K₁⊆K，使得若迭代点x^k+1=x^k+t_kd^k均由算法1步4和步5产生，反设x^*不是问题(1)的一个K-T点，则由引理3知

再由式(14)知

这是一个矛盾.因此x^*是问题(1)的一个K-T点.

在这一部分从数值计算的角度进一步说明本文给出的算法的有效性，算法的编程使用MATLAB软件.算法中涉及的参数取值如下：

B_k的更新选自BFGS公式修正^[10]：

其中：

而乘子函数μ(x)=-(N(x)^TN(x)+D(x))^-1N(x)^T▽f(x)，其中N(x)=(g_j(x)，j∈I)，D(x)=diag(c_j²(x)，j∈I).终止准则为‖d₀^k‖＜10^-6.

从文献[11]中选取了7个测试问题，对本文的算法进行测试，测试结果见表 1.

表 1问题编号即测试问题在文献[11]中的编号，n表示问题中变量的维数，m表示问题中约束的维数，X⁰表示问题的初始点，NF₁，NF₂分别表示本文算法和文献[11]的目标函数和约束函数的计算次数，NG₁，NG₂分别表示本文算法和文献[11]的梯度的计算次数，NIT₁，NIT₂分别表示本文算法和文献[11]的算法的迭代次数.

从上述分析可看出，本文给出的修正共轭投影梯度滤子算法是有效可行的.将共轭投影技术引入到滤子算法使得该算法不需要求解二次规划子问题，而且能有效避免常规滤子算法中的恢复算法，简化了计算.