不等式約束優(yōu)化的一個濾子SQP算法

張家昕

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

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

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

本文提出一個修正的濾子SQP算法，通過修正QP子問題的約束條件減小其不可行性，采用濾子方法避免罰函數(shù)法在選擇罰因子上的困難，同時松弛濾子的接受條件，有利于得到全局最優(yōu)點[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，參數(shù) β∈(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中二次連續(xù)可微函數(shù)。

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

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

引理1 設數(shù)列{f(xk)}和{h(xk)}滿足:h(xk)≥0，{f(xk)}單調遞減有下界，如果對于所有的k，常數(shù)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}由算法產(chǎn)生，序列{dk}是子問題(4)的解，則有=0成立。

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

又由KKT條件有

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

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

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

假設每一聚點都不是KKT點，設被濾子接受的點列產(chǎn)生的聚點為x*，記為一無限指標集，F(xiàn)k為被濾子接受的迭代步指標.由文獻[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].應用數(shù)學學報，2012，35(1):49－58.

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

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

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

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

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

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