一种求解序列二次规划结合信赖域的多维滤子算法

孙 涛， 杨雪峰

(大连理工大学 数学科学学院，辽宁 大连 116024)

0 引言

本文考虑如下形式的非线性约束优化问题：

(1)

其中目标函数f:Rn→R和约束函数ci:Rn→R(i=1,2,…,n)是二次连续可微的，记E={i:i=1,2,…,m}，I={i:i=m+1,…,n}。

紧接着，问题(1)的KKT条件为：

(2)

在过去的十年里，Fletcher和Leyffer[1]等人提出了一种滤子算法来求解非线性规划问题。他们借用了多目标优化的思想，将非线性约束优化问题分为双目标优化，其实质为一种非单调法，即目标函数与约束违反度都减小，但可以不同时减小的策略，具有非常好的收敛性效果。紧接着Fletcher，Gould和Leyffer[2]等人又给出了SQP结合信赖域的全局收敛性证明。Su和An[3]等人提出了一种对于等式约束具有全局收敛性的非单调滤子算法，他们将试探步分为了准法步与切步，使算法的计算规模变得更小。Nie[4]等人提出了一般非线性规划的信赖域滤子算法，他们通过信赖域半径来控制试探步获得原始问题的K-T点。Shen[5]等人提出了基于线搜索的三维滤子算法，使得试探步的接受程度变得更加灵活。Gu[6]等人提出了一种基于Wachter-Biegler方法的非线性等式约束的滤子算法，并得出了全局收敛性证明。Liu[7]等人提出了三维滤子的序列二次规划方法用于求解变分不等式问题。随后，人们相继将滤子方法与非光滑的捆绑法[8]、模式搜索法[9]、内点法[10]以及线搜索法等相结合，从而得到了一系列不同的滤子优化算法。

本文针对SQP结合信赖域时可能出现无解的情况(即不相容性问题)给出了一种多维滤子算法。首先根据袁等人提出的思想，我们对约束条件引进参数变量，对目标函数加上罚项，实行可行化处理，从而克服了不相容性问题，也就是无需再设计可行性恢复算法。其次，我们改善了传统的二维滤子对迭代步选择性接受的严格性(即将所有的约束条件放在一起考虑且只有一个约束违反度)。由于实际所遇到的问题中，约束条件可以分为线性与非线性等式，线性与非线性不等式四类，因此，我们对不同的约束条件加以分析，将它们相应的约束违反度同时最小化作为条件，再加上目标函数条件，即得到一个多维滤子，即包括目标函数，线性与非线性等式约束违反度，线性与非线性不等式约束违反度等。与传统的二维滤子算法相比，本算法对迭代步的选择性条件大大的被放松。最后，为了避免该滤子算法同样会出现maratos效应，我们采用了二阶校正的方法，给出了修改后的多维滤子算法。同时，该算法在一定的假设条件下，具有了全局收敛性的性质。

本文分为四个部分。即第一部分为算法分析与滤子定义。第二部分为二阶校正方法。第三部分为算法步骤。第四部分为全局收敛性的证明。第五部分为结论。

1 算法分析与多维滤子定义

考虑逐步二次规划与信赖域结合的如下子问题:

(3)

其中，gk=▽f(xk)，Bk为Hesse阵或近似对称正定阵，Δk为信赖域半径。

然而简单的将逐步二次规划与信赖域结合显然是不可行的，即可能会出现无解的情况，所以我们考虑如下子问题：

(4)

其中θ为参数变量，θ∈(0,1]，δ>0为罚因子。

当θ→1时，子问题(4)具有一定的可行性(即无需再次设置可行性恢复阶段算法)。

1.1 等式和不等式约束违反度

由于问题(1)可以等价的转化为：

(5)

其中：E1={i:i=1,…,l}所对应的函数为线性等式，E2={i:i=l+1,…,m}所对应的函数为非线性等式，I1={i:i=m+1,…,p}所对应的函数为线性不等式，并且I2={i:i=p+1,…,n}所对应的函数为非线性不等式。

所以，相应函数的约束违反度分别被记为：

1.2 下降量

预计下降量与实际下降量分别被定义为:

Δq=qk(0)-qk(d),Δf=f(xk)-f(xk+1)

(6)

1.3 多维滤子

定义1称一个迭代点(cE1(xk),cE2(xk),cI1(xk),cI2(xk),f(xk))占优于另一个迭代点(cE1(xi),cE2(xi),cI1(xi),cI2(xi),f(xi))当且仅当有cE1(xk)≤cE1(xi)，cE2(xk)≤cE2(xi),cI1(xk)≤cI1(xi)，cI2(xk)≤cI2(xi)，f(xk)≤f(xi)成立即可。

定义2称一个滤子F为一些迭代点的集合，若对其中任意两点之间不能被彼此占优于。

定义3记当前滤子为Fk-1，若xk点不被滤子Fk-1中任意一点所占优于，则(cE1(xk),cE2(xk),cI1(xk),cI2(xk),f(xk))被滤子Fk-1接受，加入到Fk-1，同时也要移去一些被xk占优于的点。即，令Dk={xi:cE1(xk)≤cE1(xi),cE2(xk)≤cE2(xi),cI1(xk)≤cI1(xi),cI2(xk)≤cI2(xi),f(xk)≤f(xi)},则我们有Fk=(Fk-1∪{xk})Dk,其中对一个足够大的非负整数N，我们有‖Fk‖≤N。

1.4 多维滤子方法的思想

在滤子开始之前，将子问题(4)中设置为k=0，即在每一次迭代中都要先求解子问题(4)，以得到一个最优的迭代步xk+dk，若该迭代步被滤子接受，则令新的迭代步为xk+1=xk+dk，并增加信赖域半径，更新滤子(将xk加入滤子中，并移去滤子中那些被xk占优于的点)，否则当前滤子将拒绝接受迭代步，则令xk+1=xk，并减小信赖域半径，重新求解子问题(4)。

为了防止太靠近滤子中的迭代点被接受，我们定义一个多维的滤子接受条件:

(7)

注1其中h(x)=(cE1(x)+cE2(x)+cI1(x)+cI2(x))2。如果h(x)=0，则x∈D，其中D={x∈Rn:ci(x)=0,ci(x)≤0,i∈E,i∈I}为可行域。

注2在算法的计算过程中尽量取γ1,γ2,γ3,γ4相等且大于γ0，同时都趋向于0。因为这样可以使算法在迭代的过程中尽量快速的保持可行性条件，同时使目标函数有足够的下降量。γ5∈(γ,1)尽量使其趋向于1，其中γ=max{γ0,γ1,γ3,γ4}。

注3多维滤子接受条件(7)指的是一个试探点若被接受只要满足任何一个条件就可以。因为多维滤子算法是通过SQP结合信赖域的方法来获得的搜索方向，并且在SQP方法中，是用一阶泰勒展开得到约束条件的近似。这样，对于那些线性约束条件或者几乎线性约束条件来说，是一个比较好的方法，但是对于某些高度非线性的约束条件来说，只采用一阶泰勒去近似，就显得过于直接。从数值计算的角度来说，非线性约束条件的约束违反度在不同的迭代点之间会有较大的变化，而对于线性约束条件来说，一般不会太多发生。又因为在实际问题中经常会出现既有线性约束条件，也有非线性约束条件。所以，线性约束条件和非线性约束条件要区别性的对待。传统的二维滤子SQP方法中，尽管将目标函数和约束违反度分别考虑，但是它们是将所有的约束条件放在一起考虑得到的一个约束违反度，没有对不同性质的约束条件都充分考虑。而滤子方法的本质思想是将非线性规划问题看作是一个多目标优化问题，它的目标是使得约束违反度最小或使得目标函数值达到最小。所以，本文考虑将约束条件分为线性与非线性等式约束违反度，线性与非线性不等式约束违反度等，再加上目标函数，这样就得到一个多维滤子下降条件。所以一个试探点被接受只要满足任何一个条件就可以。这样，与传统的二维滤子相比，一个试探点被接受的条件就被大大的放松。并且，由于传统的二维滤子条件也避免不了maratos效应。因此，对于构造的多维滤子在一定程度上可以避免此类问题的发生。

1.5 充分下降条件

Δq=qk(0)-qk(d),Δf=f(xk)-f(xk+1)

(8)

注4令满足<2>或<3>或<4>或<5>或<6>之一条件时的叫h迭代点。令满足<1>与(8)条件的叫f迭代点。

2 二阶校正的思想

如果xk+dk不能被滤子接受时，那么计算二阶校正步(SOC)，即求解下列子问题：

(9)

3 算法：

1):初始化点x0∈Rn,Δ0>0,0<η1<1,η2≥1,ρ1∈(0,1),ρ2≥1,B0=I,γi∈(0,1)，其中i=1,2,…,5。

3):最优性检验。若dk=0，θ=1，则停止。否则，转到步4)。

6)：令xk+1=xk，Δk+1=ρ1Δk，(ρ1∈(0,1))，转步3)。

7)：令Δk+1=ρ2Δk(ρ2≥1)，转下一步。

8)：更新滤子，转下一步。

9)：利用BFGS，使Bk→Bk+1，转下一步。

10)：令k=k+1，转步3)。

注7在这个多维滤子算法中，为了防止太靠近滤子中的迭代点被接受，定义了一个多维滤子接受条件，从而避免了有些迭代点不能被滤子接受的情况，因此使得算法具有很好的可行性与收敛速度。但是放松后的滤子元素数量不能太多，应该对滤子数量设置一个充分大的上界以防止元素数量的溢满。

4 全局收敛性证明

首先，我们对算法中函数及迭代步做出以下假设条件：

(1)算法所产生的所有迭代步xk都包含在一个非空的凸紧集X上。

(2)函数f(x),ci(x)(i∈EUI)在一个X的开集上是二次连续可微的。

(3)对任意的k，Bk为一致正定有界的。

(4)存在0≤m≤M，使m‖d‖2≤dTBkd≤M‖d‖2成立，其中d∈Rn。

(5)在子问题(4)中，尽量令θ→1，使算法保持可行性。

引理1如果有无穷点列{xk}加入到滤子(即存在(cE1(xk),cE2(xk),cI1(xk),cI2(xk),f(xk))加入到滤子中)，h(xk)>0且f(xk)有下界，则当k→∞时，我们有h(xk)→0(即有可行点) 。

证明根据算法及假设条件，分为以下三个部分：

(1)如果当k→∞时，有无穷多个{xk}满足(7)中的<2>或<3>或<4>或<5>之一时，则必有h(xk)→0(当→∞时)。

(反证法)反设对某个ε1，存在一子列{xki}⊆{xk}，使h{xki}≥ε1成立，由假设条件(1)可知，算法中迭代点列{xki}包含在一个凸紧集上，所以，由聚点定理(有界无穷点集必有聚点)，则存在一个点列{xkj-1}⊆{xki}使xkj-1→x*(当j→∞时)，并且我们也有:h(xkj-1)→h(x*)⊗，其中x*为{xkj-1}的聚点。

又因为对每一个kj-1都有使得下式之一成立，即

cE1(xkj)-cE1(xkj-1)≤γ1h(xkj-1)γ1∈(0,1)cE2(xkj)-cE2(xkj-1)≤γ2h(xkj-1)γ2∈(0,1)cI1(xkj)-cI1(xkj-1)≤-γ3h(xkj-1)γ3∈(0,1)cI2(xkj)-cI2(xkj-1)≤-γ4h(xkj-1)γ4∈(0,1)

因为h(xi)≥ε1，不失一般性，当子列{xkj-1}就为{xki}本身时，一定有kj-1使得h(xkj-1)>ε1，所以由⊗式也一定有h(x*)>ε1。即当j→∞时，上式中任何一个条件有0<-γih(x*)(i=1,2,3,4)。又因为h(x*)>ε1，所以有0<-γiε1,(i=1,2,3,4)。即产生矛盾。因此当k→∞时，我们有h(xk)→0。

(2)如果{xk}不满足(7)中的<2>且<3>且<4>且<5>时，即有

cE1(xk)-cE1(xk-1)>-γ1h(xk-1)γ1∈(0,1)cE2(xk)-cE2(xk-1)>-γ2h(xk-1)γ2∈(0,1)cI1(xk)-cI2(xk-1)>-γ3h(xk-1)γ3∈(0,1)cI2(xk)-cI2(xk-1)>-γ4h(xk-1)γ4∈(0,1)

(3)对于(7)中的<6>显然成立。即证。

推论1如果存在无穷多个点列{xk}满足<2>或<3>或<4>或<5>时，并且迭代点被加入到滤子中，则当k→∞时，必有h(xk)→0。

证明类似于引理一中的(1)。

推论2给定一组迭代点(cE1(xk),cE2(xk),cI1(xk),cI2(xk),f(xk))，若对所有k，有(7)式成立时，则当k→∞时，我们有h(xk)→0，其中cE1(xk)≥0，cE2(xk)≥0，cI1(xk)≥0，cI2(xk)≥0，且f(xk)是单调递减有下界的函数。

证明类似于引理一中的(1)与(2)。

定理1若假设条件(1)～(4)成立，那么算法会产生如下的两种情况：

|1|找到NLP问题的KKT点。

|2|必有一个可行的聚点，并且它是KKT点或不满足MFCQ条件。

证明根据算法及假设条件，分为两部分考虑：

(2)如果满足h迭代点是无穷多个点，则由引理一，必存在xk，当k→∞时，我们有h(xk)→0，并且xk有聚点x*(由聚点定理可知)，因此x*为一个可行点(因为h(x*)=0)。

h(xk+1)=(cE1(xk+1)+cE2(xk+1)+cI1(xk+1)+cI2(xk+1))2

≤cE1(xk+1)+cE2(xk+1)+cI1(xk+1)+cI2(xk+1)

f(xk)-f(xk+1)-γ0h(xk)

≥f(xk)-f(xk+1)-γ0/γ5h(xk+1)

(*)

因此，对充分大的k，我们有无穷多个f迭代点，那么与原问题产生矛盾，所以x*为KKT点。即证。

5 结论

本文提出了一种求解序列二次规划结合信赖域的多维滤子算法。该算法与传统的二维滤子算法相比，构造了一个多维滤子的接受条件，使得它对迭代步的接受程度被大大的放松，并且可以克服解的不相容性与maratos效应。最后，从理论上证明了该算法在一定的假设条件下具有全局收敛性。因此，所提的多维滤子算法对未来求解大规模的非线性规划问题提供了一个很好的理论方向。