一類不帶二階校正的超線性收斂濾子方法

劉美玲

(上海電機(jī)學(xué)院 數(shù)理教學(xué)部， 上海 201306)

?

一類不帶二階校正的超線性收斂濾子方法

劉美玲

(上海電機(jī)學(xué)院 數(shù)理教學(xué)部， 上海 201306)

摘要:提出了一類求解非線性約束優(yōu)化問題的線搜索濾子算法。在濾子結(jié)構(gòu)中用拉格朗日函數(shù)取代目標(biāo)函數(shù),在不用二階校正的情況下可避免Maratos效應(yīng)。在較弱的條件下,算法可得到全局收斂性和超線性收斂性。

關(guān)鍵詞:非線性約束優(yōu)化； 濾子； Maratos效應(yīng)； 全局收斂； 超線性收斂

考慮以下的非線性約束優(yōu)化問題：

(1)

式中，x∈Rn,函數(shù)f∶Rn→R和ci(x)(i∈E)∶Rn→R假設(shè)為連續(xù)可微的。

相應(yīng)的Lagrange函數(shù)為

L(x,λ)=f(x)+λTc(x)

(2)

式中，向量λ為L(zhǎng)agrange乘子；c(x)=(c1(x),c2(x),…,cm(x))。

Fletcher等在文獻(xiàn)[1]中提出的濾子方法是求解問題(1)的最有效的方法之一。它的基本思想如下： 如果在一個(gè)試探點(diǎn)處能改善目標(biāo)函數(shù)值或約束違反度函數(shù)值，則該試探點(diǎn)會(huì)被接受。

濾子方法可作為價(jià)值函數(shù)代替罰函數(shù)。因?yàn)榱P參數(shù)一般是不易估計(jì)的。文獻(xiàn)[1]中濾子方法的優(yōu)良數(shù)值結(jié)果使得最近幾年對(duì)它有了持續(xù)而深入的研究[2-10]。在這些研究中對(duì)全局收斂進(jìn)行了廣泛分析，但對(duì)超線性收斂性的研究較少,已有的主要成果有Ulbrich[3]提出的一類濾子SQP(Sequential Quadratic Programming)方法[3]和W?chter等[4]提出的一類帶二階校正步的線搜索濾子方法。文獻(xiàn)[3]中的濾子方法在一個(gè)SQP信賴域框架下執(zhí)行，但是為了獲得超線性收斂性并盡量接收SQP完全步,其中的充分減少條件是比較復(fù)雜的，故在算法實(shí)際執(zhí)行中比較耗時(shí)。而在文獻(xiàn)[4-5]中的無二次子規(guī)劃的線搜索方法中,濾子方法表現(xiàn)出了較好的穩(wěn)定性，且基于線搜索技術(shù)的濾子方法不需要滿足所有約束的線性化相容。但是,文獻(xiàn)[4-5]中的線搜索濾子方法如果不用二階校正步,則會(huì)受到Maratos效應(yīng)影響，此時(shí),濾子技術(shù)會(huì)阻止接收一個(gè)接近最優(yōu)解的試探步,妨礙了局部收斂性，使得濾子不可接收一個(gè)完全的線搜索步,不能得到超線性收斂性。本文研究了一類不用二階校正步的線搜索濾子算法，為了避免Maratos效應(yīng),用Lagrangian函數(shù)值代替濾子中的目標(biāo)函數(shù)值，也能確保獲得超線性收斂性。另外,該算法對(duì)充分減少條件的要求并不強(qiáng)，且算法可得到全局收斂性。

1算法機(jī)制

對(duì)一個(gè)給定的初始估計(jì)值x0,用一個(gè)線搜索算法產(chǎn)生一系列問題式(1)的最優(yōu)解的較好估計(jì)xk，k為迭代次數(shù)，k∈N。式(1)的Karush-Kuhn-Tucker(KKT)條件為

(3)

為了討論簡(jiǎn)單,本文只考慮等式約束。通過設(shè)置松弛變量等方法,所提算法和收斂技術(shù)容易用到含不等式約束的問題中。在每一次迭代k,搜索方向dk通過計(jì)算xk處的KKT條件(式(3))的線性化，可得到

(4)

在得到一個(gè)搜索方向dk及一個(gè)步長(zhǎng)αk∈[0,1]后,下一個(gè)試探步由

xk+1∶=xk+αkdk

得到。這里,用一個(gè)回溯線搜索程序獲得一個(gè)步長(zhǎng)值,主要是通過持續(xù)減少步長(zhǎng)αk的值,直到某種接收準(zhǔn)則被滿足。本文的接收準(zhǔn)則為濾子。

濾子方法的基本思想來自多目標(biāo)優(yōu)化中的支配概念[1]。

定義2一個(gè)濾子是指一列點(diǎn)對(duì)(hl,Ll),其中任何兩個(gè)點(diǎn)對(duì)都不能互相支配。如果一個(gè)點(diǎn)對(duì)(hk,Lk)不被濾子中的任何一個(gè)點(diǎn)對(duì)支配，則其可被接收到濾子中。

當(dāng)一個(gè)點(diǎn)對(duì)(hk,Lk)被接收到濾子中，也稱迭代點(diǎn)xk被接收到濾子中。然而，單濾子條件不能充分保證得到全局收斂,故用一個(gè)強(qiáng)濾子條件(稱為斜濾子[2])。因此，如果一個(gè)點(diǎn)xk相應(yīng)的點(diǎn)對(duì)(hk,Lk)滿足

(5)

條件，則本文稱該點(diǎn)可被濾子Fk接收。式中，定常數(shù)β,γ∈(0,1)，實(shí)際算法執(zhí)行時(shí),通常設(shè)置β接近1，而γ接近0。

本文的接收準(zhǔn)則給出了一個(gè)重要的包含性質(zhì),即如果一個(gè)點(diǎn)對(duì)(hk,Lk)被加到了濾子中,則新濾子的不可接受點(diǎn)集總是包含了舊濾子的不可接受點(diǎn)集[2]。

另外,設(shè)置函數(shù)L(xk,λk)的一個(gè)充分減少條件,與濾子條件結(jié)合作為試探步接受的充分減少條件： 記

ΔLk=L(xk,λk)-L(xk+1,λk+1)

作為函數(shù)L(xk,λk)的實(shí)際減少量,而

為L(zhǎng)(xk,λk)的線性減少量;設(shè)函數(shù)L(xk,λk)的充分減少條件

ΔLk≥σΔlk,σ∈(0,1)

是一個(gè)前置參數(shù)。

在實(shí)際執(zhí)行中,若線性系統(tǒng)(式(4))不相容,不能計(jì)算出搜索方向dk,故算法啟動(dòng)一個(gè)可行恢復(fù)項(xiàng)[4-5]。為了簡(jiǎn)單,本文假設(shè)線性系統(tǒng)總是相容的,故不考慮設(shè)置可行恢復(fù)項(xiàng)。本文給出下面算法步驟,用于求解問題式(1)。

(1) 給定初始點(diǎn)x0,常數(shù)β∈(0,1),γ∈(0,1),σ∈(0,1),τ∈(0,1),約束違反度函數(shù)h的上界hmax=max{104,1.2h(x0)}。

(2) 初始化。設(shè)α0=1,初始濾子F0={(hmax,L(x0,λ(x0)))},迭代數(shù)k=0。

(3) 對(duì)k=0,1,…,由式(4)計(jì)算搜索方向dk和 Lagrange乘子λk+1。當(dāng)xk滿足KKT條件(式(4))或dk=0時(shí),算法停止；否則，算法進(jìn)入下一步。

② 若Δlk>0和ΔLk<σΔlk成立,進(jìn)入③;否則，增廣濾子Fk+1=Fk∪{(h(xk+1),L(xk+1,λk+1))},進(jìn)入步驟(5);

我無意中參與了一場(chǎng)巷戰(zhàn)，被路過的老師扭送到校長(zhǎng)室。校長(zhǎng)看著我劣跡斑斑的違規(guī)記錄，擺擺手說：“你回家去吧，以后，也不必再來了。”

為方便陳述,若Δlk>0和ΔLk>σΔlk成立,則稱xk為L(zhǎng)-型迭代；若Δlk≤0,則迭代的主要目的是減少h,此時(shí)產(chǎn)生的迭代點(diǎn)稱為h-迭代點(diǎn)。

注1為了防止hk→∞時(shí)一系列L-型迭代點(diǎn)被接收,給約束違反度函數(shù)h設(shè)置一個(gè)上界hmax。

2收斂分析

2.1　全局收斂

以下給出算法1的全局收斂分析。部分參考了文獻(xiàn)[2，10]的證明思想。首先,給出假設(shè)條件:

A1所有的迭代點(diǎn)xk在Rn的一個(gè)非空閉有界集S中。

A2函數(shù)f、ci在S上二次連續(xù)可微。

以上A1、A2是標(biāo)準(zhǔn)假設(shè)條件,A3、A4對(duì)獲得收斂結(jié)果和確保算法可執(zhí)行至關(guān)重要。

(6)

引理1假設(shè)Lk單調(diào)遞減且下有界，對(duì)所有的k,如果

hk+1≤β hk或Lk-Lk+1≥γ hk+1

則hk→0。

證明如果hk+1≤βhk對(duì)所有充分大的k成立,則hk→0;否則在一個(gè)無窮迭代子序列上有Lk-Lk+1≥γhk+1成立。已知Lk單調(diào)減少且下有界,∑hk+1是有界的，因此，在該無窮子序列上有hk+1→0；但對(duì)于剩下的迭代點(diǎn)有hk+1≤βhk,因此在主序列上hk→0。

引理2設(shè)在無窮迭代序列{xki}處(h(xki),L(xki,λki))可被濾子接收,則

證明若引理結(jié)論不真,必存在一個(gè)無窮子序列{kj}?{ki},使得對(duì)所有的j和某個(gè)常數(shù)ε>0有

h(xkj)>ε

(7)

因此,在區(qū)域[hkj-(1-β)ε,hkj]×[Lkj-γε,Lkj]或該區(qū)域和V0∶=[0,hmax]×[Lmin,∞]的交集內(nèi)沒有其他的點(diǎn)對(duì)(h,L)會(huì)被加到濾子中，其中，Lmin≤L(xk,λk)是一個(gè)常數(shù)。易知這些區(qū)域的面積為(1-β)γε2，故集合V0∪{(h,L)|L≤cL}可被至多有限個(gè)這樣的區(qū)域有限覆蓋,其中，cL為常數(shù)并滿足cL≥Lmin。

既然點(diǎn)對(duì)(hkj,Lkj)持續(xù)被加到濾子中,當(dāng)i→∞,Lkj→∞，不失一般性,假設(shè)Lkj+1≥Lkj對(duì)所有充分大的j成立。但是，由式(5)和式(7),有

hkj+1≤β hkj

即得hkj→0,與式(7)矛盾。因此，假設(shè)Lkj+1≥Lkj錯(cuò)誤,引理結(jié)論成立。

證明由線性系統(tǒng)式(4)及式(6),可得

引理4設(shè)假設(shè)條件A1~A4成立,{xki}?{xk}是一個(gè)迭代點(diǎn)子序列，使得對(duì)獨(dú)立于ki的常數(shù)ε2>0有

則必存在試探點(diǎn)可被濾子接收。

證明算法機(jī)制確保了第1個(gè)迭代點(diǎn)可被濾子接收。以下假設(shè)(h(xk),L(xk,λk))可被接收到第k個(gè)濾子中,且(h(xl),L(xl,λl))∈Fk,l

即

然后,由Taylor定理和式(6)可得

(8)

相似地,若

有

仍由Taylor定理,由式(4)、(6)可得

(9)

因此,再由式(8)、(9)得

L(xki+1,λki+1)≤L(xki,λki)≤L(xl,λl)-γh(xki)

h(xki+1)≤h(xki)≤βh(xl)

(10)

即引理結(jié)論為真。

定理1設(shè)假設(shè)條件A1~A4成立,且問題(1)有至少一個(gè)解。算法產(chǎn)生的迭代點(diǎn)序列{xk}必會(huì)有以下兩種結(jié)果之一：

(1) 問題(1)的一個(gè)KKT點(diǎn)找到。

(2) 存在一個(gè)聚點(diǎn)是一個(gè)KKT點(diǎn)。

證明只需要考慮結(jié)果(2)。以下分兩種情況分析。

ΔLk=L(xk,λk)-L(xk+αdk,λ(xk+αdk))=

(11)

此處用了引理3的結(jié)論，即

(2) 只有有限個(gè)h-型迭代點(diǎn)加到濾子中,則對(duì)所有的k≥K,xk是一個(gè)L-型迭代點(diǎn)，故 L(xk,λk) 嚴(yán)格單調(diào)減少。又因?yàn)?/p>

L(x,λ)=f(x)+λc(x)

|ΔLki-Δlki|=

(12)

另一方面,據(jù)引理3,有

即

(13)

由式(12)、(13)推得

(14)

2.2　局部收斂

以下進(jìn)行局部收斂分析,證明在本文的濾子構(gòu)造可避免Maratos效應(yīng),即一個(gè)試探步長(zhǎng)αk=1可被接受。加一假設(shè)條件：

(15)

在下文的證明中,定義

(16)

式中，ρ>0是一個(gè)常數(shù)。

(17)

由Taylor定理和

(18)

顯然可得

(19)

其中，r是一個(gè)常數(shù),參見文獻(xiàn)[3]中的引理2。

(20)

?d∈Rn

對(duì)所有的常數(shù)s>0,顯然有

(21)

(22)

(23)

式中，常數(shù)t>0。則由式(22)、(23)可得引理結(jié)論。

引理6設(shè)假設(shè)條件A5成立,則對(duì)任何ζ∈[0,1]和M0≥1存在一個(gè)充分大的指標(biāo)數(shù)K，使得對(duì)所有的k≥K,α=1及

(24)

點(diǎn)xj+1,j=k,k+1,…，可被濾子Fj∶=Fk∪(hk,Lk)∪(hk+1,Lk+1)∪…∪(hj,Lj)接受。

(25)

由引理5,得到

(26)

設(shè)

(27)

以下證明對(duì)K≤l≤k,xk可接收到(hl,Ll)∈Fk∪(hk,Lk)，由式(24)得

再由式(26)，可得

(28)

則由式(26)、(27)推出

(29)

h(x)>β hl,L(x)+γh(x)>Ll

由此,可由式(25)、(26)得

(30)

由式(30)、(28)可推出

該結(jié)果與式(29)矛盾。因此，x可接收到濾子Fk∪(hk,Lk)，即可推斷(hj+1,Lj+1)可被接收到濾子Fl中。

定理2設(shè)假設(shè)條件A1~A5成立,則存在充分大的指標(biāo)數(shù)K>0，使得對(duì)所有的k≥K,算法可接受αk=1的步,即

xk+1=xk+dk

證明定理結(jié)論可直接由引理6和注2得到。

3數(shù)值結(jié)果

本文給出算法1的一些數(shù)值計(jì)算結(jié)果,并且與三維濾子方法[12]進(jìn)行比較。所有的數(shù)值計(jì)算問題均取自CUTE問題集。該問題集在NEOS網(wǎng)站可免費(fèi)獲取，算法程序由MATLAB7.0編寫。參數(shù)設(shè)置如下：

(1) 終止準(zhǔn)則設(shè)置為

取ε=1×10-6,與文獻(xiàn)[12]中取值相同。

(2) 取β=0.99,γ=10-4,σ=0.1。

數(shù)值試驗(yàn)參數(shù)如表1所示，表2給出了數(shù)值試驗(yàn)的結(jié)果；為了方便比較,表2中還給出了三維濾子線搜索算法的數(shù)值結(jié)果。

表1　試驗(yàn)參數(shù)說明Tab.1　Experimental parameters

表2　算例計(jì)算結(jié)果Tab.2　Numerical results

由表1可見,與三維濾子方法相比,算法1的數(shù)值結(jié)果顯示了其具有較好的穩(wěn)定性和有效性。

4結(jié)語

本文研究了一類求解非線性約束優(yōu)化問題的線搜索濾子算法，將Lagrangian函數(shù)取代目標(biāo)函數(shù)置于濾子中,可避免Maratos效應(yīng)，設(shè)置一個(gè)輔助增廣Lagrangian函數(shù)后,也可獲得超線性收斂性。本文結(jié)果顯示了線搜索濾子方法不用二階校正步也可以得到較快的局部收斂速度。

參考文獻(xiàn)：

[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 P L.On the global convergenceof a filter-SQP algorithm[J].SIAM Journal on Optimization,2002,13(1)： 44-59.

[3]Ulbrich S.On the superlinear local convergence of a filter-SQP method[J].Mathematical Programming,2004,100(1)： 217-245.

[4]W?chter A,Biegler L T.Line search filter methods for nonlinear programming： Local convergence[J].SIAM Journal on Optimization,2005,16(1)： 32-48.

[5]W?chter A，Biegler L T.Line search filter methods for nonlinear programming： Motivation and global convergence[J].SIAM Journal on Optimization,2005,16(1)： 1-31.

[6]Gould N I M,Sainvitu C,Toint P L.A filter-trust-region method for unconstrained optimization [J].SIAM Journal on Optimization,2006,16(2)： 341-357.

[7]Nie Puyan.Sequential penalty quadratic programming filter methods for nonlinear programming [J].Nonlinear Analysis： Real World Applications,2007,8(1)： 118-129.

[8]Nie Puyan,Ma Changfeng.A trust region filter method for general nonlinear programming [J].Applied Mathematics and Computation,2006,172(2)： 1000-1017.

[9]Ulbrich M,Ulbrich S,Vicente L N.A globally convergent primal-dual interior-point filter method for nonconvex nonlinear programming[J]. Mathematical Programming,2004,100(2)： 379-410.

[10]Fletcher R,Gould N I M,Leyffer S,et al.Global convergence of a trust-region SQP-filter algorithm for general nonlinear programming[J].SIAM Journal on Optimization,2002,13(3)： 635-659.

[11]Nocedal J,Wright S J.Numerical Optimization(photoengraving)[M].Beijing： Science Press,China,2006： 45.

[12]Shen Chungen,Xue wenjuan,Pu Dingguo.Global convergence of a tri-dimensional filter SQP algorithm based on the line search method[J].Applied Numerical Mathematics,2009,59(2)： 235-250.

歡迎投稿《上海電機(jī)學(xué)院學(xué)報(bào)》

網(wǎng)址：http:∥shdj.cbpt.cnki.net

地址：上海市臨港新城橄欖路1350號(hào)

上海電機(jī)學(xué)院文理樓205室

郵編： 201306

電話： (021)38223023(021)38223025

E-mail: shdjxb@163.com

Superlinear Convergence Filter Method without Second Order Correction

LIUMeiling

(Department of Mathematics and Physics, Shanghai Dianji University, Shanghai 201306, China)

Abstract:A line search filter method for nonlinear constrained optimization is presented. Using the Lagrangian function value instead of the objective function value in the filter, the Maratos effect is avoided without an additional second order correction. Under some mild conditions, global convergence and superlinear convergence can be realized.

Key words:nonlinear constrained optimization； filter； Maratos effect； global convergence； superlinear convergence

文獻(xiàn)標(biāo)志碼:A

中圖分類號(hào):O 221.2

文章編號(hào)2095 - 0020(2015)01 -0034 - 08

作者簡(jiǎn)介：劉美玲(1981-)，女，講師，博士，主要研究方向?yàn)榉蔷€性規(guī)劃，E-mail: liuml2004@163.com

基金項(xiàng)目：國家自然科學(xué) 資助(11371281)；上海高校青年教師培養(yǎng)資助計(jì)劃資助(ZZSDJ13008)；上海電機(jī)學(xué)院二級(jí)基礎(chǔ)學(xué)科建設(shè)項(xiàng)目資助(13XKJC01)

收稿日期：2015 - 01 - 10