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

劉美玲

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

?

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

劉美玲

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

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

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

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

(1)

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

相應的Lagrange函數(shù)為

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

(2)

式中，向量λ為Lagrange乘子；c(x)=(c1(x),c2(x),…,cm(x))。

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

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

1算法機制

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

(3)

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

(4)

在得到一個搜索方向dk及一個步長αk∈[0,1]后,下一個試探步由

xk+1∶=xk+αkdk

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

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

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

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

(5)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2收斂分析

2.1　全局收斂

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

A1所有的迭代點xk在Rn的一個非空閉有界集S中。

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

以上A1、A2是標準假設條件,A3、A4對獲得收斂結果和確保算法可執(zhí)行至關重要。

(6)

引理1假設Lk單調遞減且下有界，對所有的k,如果

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

則hk→0。

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

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

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

h(xkj)>ε

(7)

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

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

hkj+1≤β hkj

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

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

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

則必存在試探點可被濾子接收。

證明算法機制確保了第1個迭代點可被濾子接收。以下假設(h(xk),L(xk,λk))可被接收到第k個濾子中,且(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)

即引理結論為真。

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

(1) 問題(1)的一個KKT點找到。

(2) 存在一個聚點是一個KKT點。

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

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

(11)

此處用了引理3的結論，即

(2) 只有有限個h-型迭代點加到濾子中,則對所有的k≥K,xk是一個L-型迭代點，故 L(xk,λk) 嚴格單調減少。又因為

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

|ΔLki-Δlki|=

(12)

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

即

(13)

由式(12)、(13)推得

(14)

2.2　局部收斂

以下進行局部收斂分析,證明在本文的濾子構造可避免Maratos效應,即一個試探步長αk=1可被接受。加一假設條件：

(15)

在下文的證明中,定義

(16)

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

(17)

由Taylor定理和

(18)

顯然可得

(19)

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

(20)

?d∈Rn

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

(21)

(22)

(23)

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

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

(24)

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

(25)

由引理5,得到

(26)

設

(27)

以下證明對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)可推出

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

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

xk+1=xk+dk

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

3數(shù)值結果

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

(1) 終止準則設置為

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

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

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

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

表2　算例計算結果Tab.2　Numerical results

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

4結語

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

參考文獻：

[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.

歡迎投稿《上海電機學院學報》

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

地址：上海市臨港新城橄欖路1350號

上海電機學院文理樓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

文獻標志碼:A

中圖分類號:O 221.2

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

作者簡介：劉美玲(1981-)，女，講師，博士，主要研究方向為非線性規(guī)劃，E-mail: liuml2004@163.com

基金項目：國家自然科學 資助(11371281)；上海高校青年教師培養(yǎng)資助計劃資助(ZZSDJ13008)；上海電機學院二級基礎學科建設項目資助(13XKJC01)

收稿日期：2015 - 01 - 10