張家昕

(安徽科技學(xué)院 信息與網(wǎng)絡(luò)工程學(xué)院，安徽 鳳陽 233100）

考慮下面的不等式約束優(yōu)化問題:

其中f:Rn→R，C(x)=(C1(x)，C2(x)，…，Cm(x))T:Rn→Rm均是二次連續(xù)可微函數(shù).序列二次規(guī)劃(SQP)是求解該問題的一種常見方法，但是這些方法都普遍存在以下問題:一是要求價(jià)值函數(shù)在每一個(gè)試探點(diǎn)都要單調(diào)下降，但是這個(gè)條件在每一步較難實(shí)現(xiàn);二是罰參數(shù)的處理，選擇適當(dāng)?shù)牧P參數(shù)是比較困難的，罰參數(shù)過大或過小都會(huì)引起不好的效果[1－3].濾子方法是一種無罰參數(shù)的方法.該方法的主要思想是用一組濾子代替?zhèn)鹘y(tǒng)的價(jià)值函數(shù)來判斷是否接受一個(gè)迭代點(diǎn)，這樣避免了罰因子的選取[4－6].濾子方法與其他方法相比關(guān)鍵是:一個(gè)迭代點(diǎn)被接受，當(dāng)且僅當(dāng)目標(biāo)函數(shù)值或約束違反度函數(shù)值有充分下降.簡單地說，如果目標(biāo)函數(shù)值或約束違反度函數(shù)值能在試探點(diǎn)非單調(diào)地下降，那么就接受該點(diǎn)為下一個(gè)迭代點(diǎn).濾子方法借用了多目標(biāo)優(yōu)化的思想，將約束優(yōu)化問題化為雙目標(biāo)優(yōu)化問題，即使得目標(biāo)函數(shù)和約束違反度都要減小，但是可以不同時(shí)減小，其本質(zhì)是一種非單調(diào)的方法，有利于得到全局最優(yōu)點(diǎn)[7－8]。

本文提出一個(gè)修正的濾子SQP算法，通過修正QP子問題的約束條件減小其不可行性，采用濾子方法避免罰函數(shù)法在選擇罰因子上的困難，同時(shí)松弛濾子的接受條件，有利于得到全局最優(yōu)點(diǎn)[9－10]。

1 新算法

設(shè)當(dāng)前迭代點(diǎn)為，一般的SQP方法通過求解它的子問題

得到方向dk，同時(shí)得到相應(yīng)的拉格朗日乘子λk，其Bk是海瑟陣可由BFGS方法更新.為避免QP子問題不可行，通過求解問題

得到解dk.顯然，當(dāng)d=0時(shí)，問題(4)轉(zhuǎn)化為問題(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 給定初始點(diǎn) x0∈Rn，參數(shù) β∈(0，1)，γ∈(0，1)，δ ＞0.初始化濾子(u，－∞)，u≥η，η ＞0，置 k:=0。

步驟1 對(duì)于當(dāng)前迭代點(diǎn)xk和矩陣Bk，用信賴域方法求解問題(3)，則可得.如果=0，則停。

步驟2 求解問題(4)得到dk，如果dk=0，則得KKT點(diǎn)，停止;

步驟3 如果xk+dk不被Fk∪(f(xk)，h(xk))接受，令ρ:=，轉(zhuǎn)步驟1;

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

② 如果A≥σP且P＜δ(hk)2，則令 ρ=，轉(zhuǎn)步驟1。

③ 如果 A≥σdk且 P≥δ(hk)2，，則將(f(xk)，ρ(xk))放入濾子，轉(zhuǎn)步驟5。

步驟5 更新 Bk+1，令 xk+1=xk+dk，K:=k+1，ρ =2ρ，轉(zhuǎn)步驟1。

2 收斂性分析

假設(shè)以下命題成立:

A1算法中所有的點(diǎn)(xk，λk)都在緊集X×K中，且X×K∈Rn+m。

A2 f(x)Ci(x)，i=1，2，…，m都是在緊集X中二次連續(xù)可微函數(shù)。

A3 存在 M2＞M1＞0，使得對(duì)于任意的 Bk，滿足 M1‖d‖2≤dTBkd≤M2‖d‖2。

A4 對(duì)于?x∈Rn，向量組{▽Ci(x)，i∈I(x)}線性無關(guān)。

引理1 設(shè)數(shù)列{f(xk)}和{h(xk)}滿足:h(xk)≥0，{f(xk)}單調(diào)遞減有下界，如果對(duì)于所有的k，常數(shù)0＜γ＜β＜1滿足

則h(xk)→0。

證 假設(shè)引理不真，則存在ε＞0和一列無窮指標(biāo)集K，?k∈K使h(xk)≥ε＞0成立且h(xk+1)≥βh(xk)，β∈(0，1).此時(shí)

由于{f(xk)}單調(diào)遞減，所以當(dāng)k→+∞時(shí)，.這與有下界是矛盾的，故假設(shè)不成立，引理得證。

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

證 假設(shè)引理不真，則存在ε＞0和一列無窮指標(biāo)集K，?k∈K使h(xk)≥ε＞0成立.當(dāng)h(xk+1)≤βh(xk)成立時(shí)，能夠得到?k∈K，x→ +∞，h(xk)→0.這與 h(xk)≥ε＞0相矛盾.當(dāng) f(xk)－f(xk+1)≥γh(xk+1)成立時(shí)，{f(xk)}k∈K單調(diào)遞減，類似引理1可推出矛盾.引理得證。

定理1 內(nèi)層迭代步驟1－步驟2－步驟4－步驟1有限終止。

證 利用反證法.假設(shè)該結(jié)論不真，則由算法知ρ將嚴(yán)格遞減而無限趨近于0，從而dk也將無限趨近于0，所以 P －A=o(‖dk‖2)

即當(dāng)k充分大時(shí)，存在σ∈(0，1)使得A≥σP一定成立.又由h(xk)→0知hk→0，即當(dāng)k充分大時(shí)一定有P≥δ(hk)2成立.另一方面由算法知A＜σP且P＜δ(hk)2，這顯然是矛盾的.故結(jié)論成立。

定理2 如果假設(shè)A1－A4成立，序列{xk}由算法產(chǎn)生，序列{dk}是子問題(4)的解，則有=0成立。

證 用反證法.假設(shè)結(jié)論不真，則存在ε＞0及正整數(shù)k0，當(dāng)k≥k0時(shí)，由‖dk‖≥ε，由h(xk)→0，當(dāng)k≥k0時(shí)有，

又由KKT條件有

這明顯與f(xk)有下界是相矛盾的，故假設(shè)錯(cuò)誤，結(jié)論成立。

下面來證明算法的全局收斂性。

定理3 如果假設(shè)A1－A4成立，序列{xk}由算法產(chǎn)生，則每一個(gè)聚點(diǎn)都是不等式優(yōu)化問題(1)的KKT點(diǎn)。證 由假設(shè)A1知必有聚點(diǎn)，且易證明任何聚點(diǎn)都是可行點(diǎn).下面用反證法證明可行聚點(diǎn)必是KKT點(diǎn)。

假設(shè)每一聚點(diǎn)都不是KKT點(diǎn)，設(shè)被濾子接受的點(diǎn)列產(chǎn)生的聚點(diǎn)為x*，記為一無限指標(biāo)集，F(xiàn)k為被濾子接受的迭代步指標(biāo).由文獻(xiàn)[2]引理1知x*為可行聚點(diǎn).由定理2知，存在x*的某個(gè)鄰域 N*，當(dāng)在 k ＞k0時(shí)，xk∈N*，當(dāng) k充分大時(shí)，總能滿足‖dk‖→0，k∈.所以 x*為KKT點(diǎn)，這與假設(shè)有矛盾.故結(jié)論成立。

[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]張家昕，段復(fù)建.非線性互補(bǔ)問題的一個(gè)濾子SQP算法[J].應(yīng)用數(shù)學(xué)學(xué)報(bào)，2012，35(1):49－58.

[5]劉澤顯.一種修正的線收索 Filter－SQP 算法[J].系統(tǒng)科學(xué)與數(shù)學(xué)，2014，34(1):53－63.

[6]劉美玲.帶等式約束二次規(guī)劃問題的濾子SQP算法[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2015，45(14):272－279.

[7]鄭亞強(qiáng).基于自適應(yīng)步長布谷鳥搜索算法優(yōu)化的小波加權(quán)多模盲均衡算法[J].安徽科技學(xué)院學(xué)報(bào)，2014，28(2):49－53.

[8]李六杏.基于隱含條件挖掘的枚舉算法優(yōu)化[J].安徽科技學(xué)院學(xué)報(bào)，2013，27(6):66－69.

[9]葛華，李香云.凸包工作集的TSP算法[J].安徽科技學(xué)院學(xué)報(bào)，2014，28(2):43－48.

[10]蘇珂.帶NCP函數(shù)的信賴域?yàn)V子方法[J].系統(tǒng)科學(xué)與數(shù)學(xué)，2008，28(12):1525－1534.