一種求解序列二次規(guī)劃結合信賴域的多維濾子算法

孫 濤， 楊雪峰

(大連理工大學 數(shù)學科學學院，遼寧 大連 116024)

0 引言

本文考慮如下形式的非線性約束優(yōu)化問題：

(1)

其中目標函數(shù)f:Rn→R和約束函數(shù)ci:Rn→R(i=1,2,…,n)是二次連續(xù)可微的，記E={i:i=1,2,…,m}，I={i:i=m+1,…,n}。

緊接著，問題(1)的KKT條件為：

(2)

在過去的十年里，F(xiàn)letcher和Leyffer[1]等人提出了一種濾子算法來求解非線性規(guī)劃問題。他們借用了多目標優(yōu)化的思想，將非線性約束優(yōu)化問題分為雙目標優(yōu)化，其實質(zhì)為一種非單調(diào)法，即目標函數(shù)與約束違反度都減小，但可以不同時減小的策略，具有非常好的收斂性效果。緊接著Fletcher，Gould和Leyffer[2]等人又給出了SQP結合信賴域的全局收斂性證明。Su和An[3]等人提出了一種對于等式約束具有全局收斂性的非單調(diào)濾子算法，他們將試探步分為了準法步與切步，使算法的計算規(guī)模變得更小。Nie[4]等人提出了一般非線性規(guī)劃的信賴域濾子算法，他們通過信賴域半徑來控制試探步獲得原始問題的K-T點。Shen[5]等人提出了基于線搜索的三維濾子算法，使得試探步的接受程度變得更加靈活。Gu[6]等人提出了一種基于Wachter-Biegler方法的非線性等式約束的濾子算法，并得出了全局收斂性證明。Liu[7]等人提出了三維濾子的序列二次規(guī)劃方法用于求解變分不等式問題。隨后，人們相繼將濾子方法與非光滑的捆綁法[8]、模式搜索法[9]、內(nèi)點法[10]以及線搜索法等相結合，從而得到了一系列不同的濾子優(yōu)化算法。

本文針對SQP結合信賴域時可能出現(xiàn)無解的情況(即不相容性問題)給出了一種多維濾子算法。首先根據(jù)袁等人提出的思想，我們對約束條件引進參數(shù)變量，對目標函數(shù)加上罰項，實行可行化處理，從而克服了不相容性問題，也就是無需再設計可行性恢復算法。其次，我們改善了傳統(tǒng)的二維濾子對迭代步選擇性接受的嚴格性(即將所有的約束條件放在一起考慮且只有一個約束違反度)。由于實際所遇到的問題中，約束條件可以分為線性與非線性等式，線性與非線性不等式四類，因此，我們對不同的約束條件加以分析，將它們相應的約束違反度同時最小化作為條件，再加上目標函數(shù)條件，即得到一個多維濾子，即包括目標函數(shù)，線性與非線性等式約束違反度，線性與非線性不等式約束違反度等。與傳統(tǒng)的二維濾子算法相比，本算法對迭代步的選擇性條件大大的被放松。最后，為了避免該濾子算法同樣會出現(xiàn)maratos效應，我們采用了二階校正的方法，給出了修改后的多維濾子算法。同時，該算法在一定的假設條件下，具有了全局收斂性的性質(zhì)。

本文分為四個部分。即第一部分為算法分析與濾子定義。第二部分為二階校正方法。第三部分為算法步驟。第四部分為全局收斂性的證明。第五部分為結論。

1 算法分析與多維濾子定義

考慮逐步二次規(guī)劃與信賴域結合的如下子問題:

(3)

其中，gk=▽f(xk)，Bk為Hesse陣或近似對稱正定陣，Δk為信賴域半徑。

然而簡單的將逐步二次規(guī)劃與信賴域結合顯然是不可行的，即可能會出現(xiàn)無解的情況，所以我們考慮如下子問題：

(4)

其中θ為參數(shù)變量，θ∈(0,1]，δ>0為罰因子。

當θ→1時，子問題(4)具有一定的可行性(即無需再次設置可行性恢復階段算法)。

1.1 等式和不等式約束違反度

由于問題(1)可以等價的轉化為：

(5)

其中：E1={i:i=1,…,l}所對應的函數(shù)為線性等式，E2={i:i=l+1,…,m}所對應的函數(shù)為非線性等式，I1={i:i=m+1,…,p}所對應的函數(shù)為線性不等式，并且I2={i:i=p+1,…,n}所對應的函數(shù)為非線性不等式。

所以，相應函數(shù)的約束違反度分別被記為：

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))占優(yōu)于另一個迭代點(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為一些迭代點的集合，若對其中任意兩點之間不能被彼此占優(yōu)于。

定義3記當前濾子為Fk-1，若xk點不被濾子Fk-1中任意一點所占優(yōu)于，則(cE1(xk),cE2(xk),cI1(xk),cI2(xk),f(xk))被濾子Fk-1接受，加入到Fk-1，同時也要移去一些被xk占優(yōu)于的點。即，令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,其中對一個足夠大的非負整數(shù)N，我們有‖F(xiàn)k‖≤N。

1.4 多維濾子方法的思想

在濾子開始之前，將子問題(4)中設置為k=0，即在每一次迭代中都要先求解子問題(4)，以得到一個最優(yōu)的迭代步xk+dk，若該迭代步被濾子接受，則令新的迭代步為xk+1=xk+dk，并增加信賴域半徑，更新濾子(將xk加入濾子中，并移去濾子中那些被xk占優(yōu)于的點)，否則當前濾子將拒絕接受迭代步，則令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。因為這樣可以使算法在迭代的過程中盡量快速的保持可行性條件，同時使目標函數(shù)有足夠的下降量。γ5∈(γ,1)盡量使其趨向于1，其中γ=max{γ0,γ1,γ3,γ4}。

注3多維濾子接受條件(7)指的是一個試探點若被接受只要滿足任何一個條件就可以。因為多維濾子算法是通過SQP結合信賴域的方法來獲得的搜索方向，并且在SQP方法中，是用一階泰勒展開得到約束條件的近似。這樣，對于那些線性約束條件或者幾乎線性約束條件來說，是一個比較好的方法，但是對于某些高度非線性的約束條件來說，只采用一階泰勒去近似，就顯得過于直接。從數(shù)值計算的角度來說，非線性約束條件的約束違反度在不同的迭代點之間會有較大的變化，而對于線性約束條件來說，一般不會太多發(fā)生。又因為在實際問題中經(jīng)常會出現(xiàn)既有線性約束條件，也有非線性約束條件。所以，線性約束條件和非線性約束條件要區(qū)別性的對待。傳統(tǒng)的二維濾子SQP方法中，盡管將目標函數(shù)和約束違反度分別考慮，但是它們是將所有的約束條件放在一起考慮得到的一個約束違反度，沒有對不同性質(zhì)的約束條件都充分考慮。而濾子方法的本質(zhì)思想是將非線性規(guī)劃問題看作是一個多目標優(yōu)化問題，它的目標是使得約束違反度最小或使得目標函數(shù)值達到最小。所以，本文考慮將約束條件分為線性與非線性等式約束違反度，線性與非線性不等式約束違反度等，再加上目標函數(shù)，這樣就得到一個多維濾子下降條件。所以一個試探點被接受只要滿足任何一個條件就可以。這樣，與傳統(tǒng)的二維濾子相比，一個試探點被接受的條件就被大大的放松。并且，由于傳統(tǒng)的二維濾子條件也避免不了maratos效應。因此，對于構造的多維濾子在一定程度上可以避免此類問題的發(fā)生。

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):最優(yōu)性檢驗。若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在這個多維濾子算法中，為了防止太靠近濾子中的迭代點被接受，定義了一個多維濾子接受條件，從而避免了有些迭代點不能被濾子接受的情況，因此使得算法具有很好的可行性與收斂速度。但是放松后的濾子元素數(shù)量不能太多，應該對濾子數(shù)量設置一個充分大的上界以防止元素數(shù)量的溢滿。

4 全局收斂性證明

首先，我們對算法中函數(shù)及迭代步做出以下假設條件：

(1)算法所產(chǎn)生的所有迭代步xk都包含在一個非空的凸緊集X上。

(2)函數(shù)f(x),ci(x)(i∈EUI)在一個X的開集上是二次連續(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(即有可行點) 。

證明根據(jù)算法及假設條件，分為以下三個部分：

(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)。即產(chǎn)生矛盾。因此當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)是單調(diào)遞減有下界的函數(shù)。

證明類似于引理一中的(1)與(2)。

定理1若假設條件(1)～(4)成立，那么算法會產(chǎn)生如下的兩種情況：

|1|找到NLP問題的KKT點。

|2|必有一個可行的聚點，并且它是KKT點或不滿足MFCQ條件。

證明根據(jù)算法及假設條件，分為兩部分考慮：

(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迭代點，那么與原問題產(chǎn)生矛盾，所以x*為KKT點。即證。

5 結論

本文提出了一種求解序列二次規(guī)劃結合信賴域的多維濾子算法。該算法與傳統(tǒng)的二維濾子算法相比，構造了一個多維濾子的接受條件，使得它對迭代步的接受程度被大大的放松，并且可以克服解的不相容性與maratos效應。最后，從理論上證明了該算法在一定的假設條件下具有全局收斂性。因此，所提的多維濾子算法對未來求解大規(guī)模的非線性規(guī)劃問題提供了一個很好的理論方向。