张家昕

(安徽科技学院 信息与网络工程学院，安徽 凤阳 233100）

考虑下面的不等式约束优化问题:

其中f:Rn→R，C(x)=(C1(x)，C2(x)，…，Cm(x))T:Rn→Rm均是二次连续可微函数.序列二次规划(SQP)是求解该问题的一种常见方法，但是这些方法都普遍存在以下问题:一是要求价值函数在每一个试探点都要单调下降，但是这个条件在每一步较难实现;二是罚参数的处理，选择适当的罚参数是比较困难的，罚参数过大或过小都会引起不好的效果[1－3].滤子方法是一种无罚参数的方法.该方法的主要思想是用一组滤子代替传统的价值函数来判断是否接受一个迭代点，这样避免了罚因子的选取[4－6].滤子方法与其他方法相比关键是:一个迭代点被接受，当且仅当目标函数值或约束违反度函数值有充分下降.简单地说，如果目标函数值或约束违反度函数值能在试探点非单调地下降，那么就接受该点为下一个迭代点.滤子方法借用了多目标优化的思想，将约束优化问题化为双目标优化问题，即使得目标函数和约束违反度都要减小，但是可以不同时减小，其本质是一种非单调的方法，有利于得到全局最优点[7－8]。

本文提出一个修正的滤子SQP算法，通过修正QP子问题的约束条件减小其不可行性，采用滤子方法避免罚函数法在选择罚因子上的困难，同时松弛滤子的接受条件，有利于得到全局最优点[9－10]。

1 新算法

设当前迭代点为，一般的SQP方法通过求解它的子问题

得到方向dk，同时得到相应的拉格朗日乘子λk，其Bk是海瑟阵可由BFGS方法更新.为避免QP子问题不可行，通过求解问题

得到解dk.显然，当d=0时，问题(4)转化为问题(2)，所以问题(4)总有可行解d=0。

h(x)≤βh(xl)，β∈(0，1)或 f(xl)－f(x)≥γh(x)，γ∈(0，1)。

修改为

h(x)≤βh(xl)，β∈(0，1)或 f(xl)－f(x)≥γhk，γ∈(0，1)

修正SQP滤子算法:

步骤0 给定初始点 x0∈Rn，参数 β∈(0，1)，γ∈(0，1)，δ ＞0.初始化滤子(u，－∞)，u≥η，η ＞0，置 k:=0。

步骤1 对于当前迭代点xk和矩阵Bk，用信赖域方法求解问题(3)，则可得.如果=0，则停。

步骤2 求解问题(4)得到dk，如果dk=0，则得KKT点，停止;

步骤3 如果xk+dk不被Fk∪(f(xk)，h(xk))接受，令ρ:=，转步骤1;

步骤4 如果xk+dk被Fk∪(f(xk)，h(xk))接受

② 如果A≥σP且P＜δ(hk)2，则令 ρ=，转步骤1。

③ 如果 A≥σdk且 P≥δ(hk)2，，则将(f(xk)，ρ(xk))放入滤子，转步骤5。

步骤5 更新 Bk+1，令 xk+1=xk+dk，K:=k+1，ρ =2ρ，转步骤1。

2 收敛性分析

假设以下命题成立:

A1算法中所有的点(xk，λk)都在紧集X×K中，且X×K∈Rn+m。

A2 f(x)Ci(x)，i=1，2，…，m都是在紧集X中二次连续可微函数。

A3 存在 M2＞M1＞0，使得对于任意的 Bk，满足 M1‖d‖2≤dTBkd≤M2‖d‖2。

A4 对于∀x∈Rn，向量组{▽Ci(x)，i∈I(x)}线性无关。

引理1 设数列{f(xk)}和{h(xk)}满足:h(xk)≥0，{f(xk)}单调递减有下界，如果对于所有的k，常数0＜γ＜β＜1满足

则h(xk)→0。

证 假设引理不真，则存在ε＞0和一列无穷指标集K，∀k∈K使h(xk)≥ε＞0成立且h(xk+1)≥βh(xk)，β∈(0，1).此时

由于{f(xk)}单调递减，所以当k→+∞时，.这与有下界是矛盾的，故假设不成立，引理得证。

引理2 如果已知序列{f(xk)}和{h(xk)}满足:h(xk)＞0，{f(xk)}有下界，则h(xk)→0。

证 假设引理不真，则存在ε＞0和一列无穷指标集K，∀k∈K使h(xk)≥ε＞0成立.当h(xk+1)≤βh(xk)成立时，能够得到∀k∈K，x→ +∞，h(xk)→0.这与 h(xk)≥ε＞0相矛盾.当 f(xk)－f(xk+1)≥γh(xk+1)成立时，{f(xk)}k∈K单调递减，类似引理1可推出矛盾.引理得证。

定理1 内层迭代步骤1－步骤2－步骤4－步骤1有限终止。

证 利用反证法.假设该结论不真，则由算法知ρ将严格递减而无限趋近于0，从而dk也将无限趋近于0，所以 P －A=o(‖dk‖2)

即当k充分大时，存在σ∈(0，1)使得A≥σP一定成立.又由h(xk)→0知hk→0，即当k充分大时一定有P≥δ(hk)2成立.另一方面由算法知A＜σP且P＜δ(hk)2，这显然是矛盾的.故结论成立。

定理2 如果假设A1－A4成立，序列{xk}由算法产生，序列{dk}是子问题(4)的解，则有=0成立。

证 用反证法.假设结论不真，则存在ε＞0及正整数k0，当k≥k0时，由‖dk‖≥ε，由h(xk)→0，当k≥k0时有，

又由KKT条件有

这明显与f(xk)有下界是相矛盾的，故假设错误，结论成立。

下面来证明算法的全局收敛性。

定理3 如果假设A1－A4成立，序列{xk}由算法产生，则每一个聚点都是不等式优化问题(1)的KKT点。证 由假设A1知必有聚点，且易证明任何聚点都是可行点.下面用反证法证明可行聚点必是KKT点。

假设每一聚点都不是KKT点，设被滤子接受的点列产生的聚点为x*，记为一无限指标集，Fk为被滤子接受的迭代步指标.由文献[2]引理1知x*为可行聚点.由定理2知，存在x*的某个邻域 N*，当在 k ＞k0时，xk∈N*，当 k充分大时，总能满足‖dk‖→0，k∈.所以 x*为KKT点，这与假设有矛盾.故结论成立。

[1]Fletcher R，Leyffer S.Nonlinear programming without a penalty function[J].Mathematical Programming，2002，91(2):239－269.

[2]Fletcher R，Leyffer S，Toint Ph L.On the global convergence of a filter－SQP algorithm[J].Siam Journal on Control and Optimization，2002，13(10):44 －59.

[3]Ulbrich S.On the superliner local convergence of a filter－SQP method[J].Mathematical Programming，2004，100(1):217 －245.

[4]张家昕，段复建.非线性互补问题的一个滤子SQP算法[J].应用数学学报，2012，35(1):49－58.

[5]刘泽显.一种修正的线收索 Filter－SQP 算法[J].系统科学与数学，2014，34(1):53－63.

[6]刘美玲.带等式约束二次规划问题的滤子SQP算法[J].数学的实践与认识，2015，45(14):272－279.

[7]郑亚强.基于自适应步长布谷鸟搜索算法优化的小波加权多模盲均衡算法[J].安徽科技学院学报，2014，28(2):49－53.

[8]李六杏.基于隐含条件挖掘的枚举算法优化[J].安徽科技学院学报，2013，27(6):66－69.

[9]葛华，李香云.凸包工作集的TSP算法[J].安徽科技学院学报，2014，28(2):43－48.

[10]苏珂.带NCP函数的信赖域滤子方法[J].系统科学与数学，2008，28(12):1525－1534.