基于F－B NCP函數的可行QP－free算法

朱笑榮

(泰山學院信息科學技術學院，山東泰安 271021)

1 引言

本文考慮如下不等式約束優化問題:

其中，x∈Rn，f(x):Rn→R且gi(x)(i∈I):Rn→R為Lipschitz連續可微函數.

問題(1.1)的Lagrange函數為:

其中λ=(λ1，λ2，…，λm)T∈Rm為乘子向量.

點(xˉ，λˉ)∈Rn×Rm稱為問題(1.1)的KKT點，若

對于約束優化問題(1.1)的求解存在很多方法，例如序列二次規劃方法(SQP)，增廣Lagrange函數方法，QP－Free方法［1－2］等等.其中，QP－free算法主要是為了克服SQP方法中計算量大和子問題不相容等問題而提出的，其每步迭代通過求解若干同系數的線性方程組來得到搜索方向［1－3］.

為了克服迭代矩陣的病態性，Qi Houduo和Qi Liqun通過應用Fischer－Burmeister非線性互補函數，提出了一個新的可行的QP－free算法.本文通過引入F－B NCP函數和ε－有效集策略，對［1，4］中的算法進行改進得到一個新的QP－Free算法，算法每次迭代只需求解線性方程組以得到迭代方向，且方程組只包含工作集中的約束，其規模較原問題大大減小，降低了運算量.

2 算法及定義

定義2.2 Ψ(x，λ)=(ψ(x，λ)T，▽xL(x，λ)T)T，ψ(x，λ)=(Φ1(x，λ)，Φ2(x，λ)，…，Φm(x，λ))T，Φi(x，λ)=φ(－gi(x)，λi)，i∈I，則KKT條件(1.3)等價于

對問題(1.1)用迭代方法求解，在第k次迭代時，假設給定xk∈D，(xk，μk)∈Rn+m，記fk=f(xk)，以下類似，定義向量ξk，γk，ηk∈Rm如下:

來代替Ψ(x，λ)的雅克比矩陣.

算法A

步驟0 給定初始值x0=D，以及初始對稱正定矩陣H0∈Rn×n，以及

步驟1 計算工作集Jk:

(1)設j=0，εk，j=ε0;

其中

(1)令A1k為Ak的個線性無關行向量構成的階方陣，且為Ak的其余的n－個行向量構成的矩陣，可表示為

(2)解下列關于s的線性系統求得s1k;

其中e=(1，1，…，1)T∈RJk，~fk={i∈Jk|~fki=gi(xk+d0k)}，

得到d1k，設dk=d0k+d1k;

步驟4若

成立，則令步長tk=1，轉步驟7;

步驟5 計算可行下降方向qk:

步驟6 計算t使其為序列

k中滿足的第一個數值，令dk=qk;

步驟7 計算新的對稱正定Hessian陣Hk+1， xk+1=xk+tkdk，令k=k+1，轉步驟1.

注:在上述算法中，如果步驟4中的試探搜索成功，則完成一個成功迭代，否則，算法由步驟5～7定義.

3 算法的適定性

本部分說明算法A是可執行的，假設如下:

(A2):函數f和gi是Lipschitz連續可微的，且?y，z∈Rn+m，有‖L(y)－L(z)‖≤‖y－z‖.

(A3):Hk為正定陣，且存在正常數σ1和σ2使得σ1‖d‖2≤dTHkd≤σ2‖d‖2.

(A4):對?x∈D，向量{▽gi(x)，i∈I(x)}是線性無關的，其中I(x)={i∈I|gi(x)=0}.

引理3.1 對于每次迭代，步驟1中沒有無限循環，而且如果{xk}k∈K→x*，則存在常數ˉε＞0，使得對充分大的k∈K有εk，jk≥ˉε，K為無限指標集.

引理3.2 若dk0=0，則▽f(xK)=0，并且xk是問題(1.1)的KKT點.

證明:若dk0=0，由線性方程組(2.3)可得

因為對i∈Jk有gi(xk)＜0，且由定義知，于是由(3.1)可得▽f(xk)=0.

引理3.3 矩陣Vk非奇異.

由式(3.3)得v=－(diag(ηki))－1diag(ξki)ATku，然后代入(3.2)式，兩邊同乘以uT，得:

于是類似于引理3.3，可得V*是非奇異的，這與假設矛盾，故引理成立.

引理3.5 若xk不是問題(1.1)的KKT點，則有d0k≠0且

證明:由前面線性方程組(2.3)有

另外由式(2.7)，可得

從而結論成立，根據(3.7)式，可知步驟6中的線搜索總是可以完成的，因此由引理3.1～引理3.5知算法A是可行的.

［1］Gao Z Y，He G P，Wu F.Sequential systems of linear equations algorithm with arbitrary initial point［J］.Science in China(Series A)，1997(27):24－33.

［2］Qi H.D，Qi L.Q.A new QP－free，globally convergent，superlinearly convergentalgorit－hm for inequality constrained optimization［J］.SIAM.JOptim，2000(36):11－33.

［3］CKanzow，QiHD.A QP－free constrained Newton－typemethod for variational inequality problems［J］.Math Prog，1999(27):81－85.