新的無罰函數(shù)無濾子的序列二次規(guī)劃方法

王　波, 濮定國

(1.同濟(jì)大學(xué) 數(shù)學(xué)系，上海 200092； 2.南京財經(jīng)大學(xué) 應(yīng)用數(shù)學(xué)學(xué)院，江蘇 南京 210023)

?

新的無罰函數(shù)無濾子的序列二次規(guī)劃方法

王波1,2, 濮定國1

(1.同濟(jì)大學(xué) 數(shù)學(xué)系，上海 200092； 2.南京財經(jīng)大學(xué) 應(yīng)用數(shù)學(xué)學(xué)院，江蘇 南京 210023)

摘要：對一般的具有等式約束和不等式約束的非線性規(guī)劃問題，提出了一個無罰函數(shù)無濾子的信賴域序列二次規(guī)劃算法.整個算法分為兩個階段，第一階段計算可行步，以達(dá)到減少約束違反度的目的，第二階段為優(yōu)化階段，以減少目標(biāo)函數(shù)的二次模型為目的.此算法中可行步和優(yōu)化步是相對獨(dú)立的，任何減少約束違反度的算法都可以應(yīng)用，具有更大的靈活性.在合理的假設(shè)條件下，證明了算法的全局收斂性和局部收斂性.通過數(shù)值實(shí)驗(yàn)證實(shí)了算法的有效性.

關(guān)鍵詞：序列二次規(guī)劃; 濾子; 罰函數(shù); 非線性規(guī)劃

(1)

其中x∈Rn,E={i|i=1,2,…,me},I={i|i=me+1,…,m},且f:Rn→R和c:Rn→Rm是光滑函數(shù).式(1)的拉格朗日函數(shù)為

(2)

其中λ∈Rme和μ∈Rm-me是乘子.式(1)的Karush-Kuhn-Tucker條件(KKT條件)為

cE(x)=0

cI(x)≤0

(3)

滿足KKT條件的點(diǎn)稱為KKT點(diǎn).

一個非線性規(guī)劃問題必須處理或者可能面對兩種不同的迭代, 分別是優(yōu)化和可行性.優(yōu)化是通過目標(biāo)函數(shù)f(x)度量的，即使目標(biāo)函數(shù)下降；可行性一般是通過約束違反度度量的, 例如,h定義為

(4)

其中‖·‖是一個任意范數(shù)，且[c(x)]+∶=max{c(x),0}.

算法中目標(biāo)函數(shù)和約束違反度這兩個準(zhǔn)則必須都得到優(yōu)化，算法就是在每一步迭代中讓這兩個準(zhǔn)則的優(yōu)化得到平衡.一些非線性規(guī)劃的算法采用價值函數(shù)作為工具，使目標(biāo)函數(shù)和約束違反度兩個準(zhǔn)則的優(yōu)化達(dá)到平衡，并且保證全局收斂性[1-2].

相對于價值函數(shù)方法, Fletcher等[3]介紹了一種濾子序列二次規(guī)劃方法， 這是一種新的非線性規(guī)劃全局方法的策略，數(shù)值結(jié)果顯示，這種序列二次規(guī)劃算法是非常有效的.Fletcher等[4]證明了濾子序列二次規(guī)劃算法的全局收斂性.之后,很多全局收斂的濾子算法被提出.

近來，Gould等[5]介紹了一種新的解非線性等式約束優(yōu)化的方法，在這種方法里，不用罰函數(shù)，濾子等.Yamashita等[6]也提出了一種對于具有非線性等式和非負(fù)約束的優(yōu)化問題的無罰函數(shù)無濾子序列二次規(guī)劃算法.Liu等[7]對非線性等式約束優(yōu)化問題，提出了一種不用罰函數(shù)和濾子的序列二次規(guī)劃算法.在此方法中，每一步的迭代的步長通過使目標(biāo)函數(shù)值或者約束違反度充分下降得到.

本文提出了一種新的不用罰函數(shù)和濾子的序列二次規(guī)劃算法.此序列二次規(guī)劃方法中計算全步長分為兩個階段.首先, 計算可行步，目標(biāo)是減少不可行測度h, 使步長滿足線性化的約束條件.其次，優(yōu)化階段是為了在線性化的可行集里計算一個試探點(diǎn)，以減少目標(biāo)函數(shù)的二次模型為目的.這種無罰函數(shù)無濾子的序列二次規(guī)劃算法有幾個優(yōu)點(diǎn)：① 此算法對一般的具有等式約束和不等式約束的非線性規(guī)劃問題適用；② 可行步和優(yōu)化步是相對獨(dú)立的，任何減少約束違反度h的算法都可以應(yīng)用；③不需要估計罰參數(shù)，避免了罰參數(shù)選取過大或過小的問題.④ 試探步受到之前迭代例如濾子的影響較小.

1算法描述

設(shè)xk為當(dāng)前迭代點(diǎn)，信賴域半徑為Δ>0，通過求解如下二次規(guī)劃:

(5)

計算步長，其中

(6)

Bk是正定對稱陣, 且

(7)

可行步nk必須滿足式(5)的約束限制并且nk的目標(biāo)是減少不可行測度h，令

其中向量PL(xk)是xk在L(xk)上的投影.然而本文不采用這種特殊的選擇，可以采用Martinez[8]的方法得到, 但是為了確保此階段的有效性，給出如下合理的假設(shè)(參見文獻(xiàn)[9]).

假設(shè)1存在常數(shù)δh>0和cn>0使得對于所有滿足h(xk)≤δh的k≥0，有

稱式(5)是相容的，當(dāng)L(xk)≠?且‖nk‖≤ξΔ,其中ξ∈(0,1)是一個常數(shù).

若式(5)是相容的, 當(dāng)執(zhí)行一個優(yōu)化步tk時，期望模型產(chǎn)生一個滿意的下降.設(shè)優(yōu)化步tk是如下二次規(guī)劃的估計解：

(8)

若式(5)是不相容的, 算法執(zhí)行重啟算法,重啟算法的目的是為了獲得xk+1，使h(xk+1)

(9)

(10)

具體算法如下

初始化:k=0,x0,0<Δmin<Δmax,Δ∈[Δmin,Δmax],γ,σ,β,λ1∈(0,1),λ2>1.

第1步:若滿足式(1)的KKT條件，即式(3)滿足，則終止算法.

第3步: 若L(xk)=?, 利用重啟策略得到xk+1.

第4步: 計算可行步nk使xk+nk∈L(xk),若‖nk‖>ξΔ,利用重啟策略得到xk+1.

第6步: 若不等式

(11)

和

(12)

成立或者不等式

(13)

否則，Δ=max{λ1Δ,Δmin}并跳轉(zhuǎn)第5步.

第7步: 利用阻尼的Broyden-Fletcher-Goldfarb-Shanno公式(BFGS公式)升級Bk+1.

第8步: 令k←k+1，并返回第1步.

注: 若試探步dk滿足f(xk)-f(xk+dk)>σΔq且Δq>0,稱此時的迭代為f-型迭代，若試探步dk滿足Δq<0,稱此時的迭代為h-型迭代.

2全局收斂性

在證明算法的全局收斂性之前，先給一些基本的假設(shè).

H1 序列xk包含在凸閉緊集X?Rn中.

H2 所有的函數(shù)f(x),cE(x),cI(x)是二次連續(xù)可微的.

H3 Hesse陣的估計陣{Bk}是上有界的且存在常數(shù)M>0使得對于所有的k,有

(14)

引理2設(shè)假設(shè)H1和H2成立，則存在常數(shù)ch>0，使對所有的xk∈X和Δ>0，由算法得到的dk滿足

(15)

證明該結(jié)論可以直接由文獻(xiàn)[12]的引理3.2得到.

引理3設(shè)f(xk)是單調(diào)遞減的并且下有界的，且h(xk)≥0.若對所有的k,

(16)

成立，則h(xk)→0.

證明該結(jié)論可以直接由文獻(xiàn)[4]的引理1得到.

引理4設(shè)無限迭代序列{xk}為h-型迭代并滿足{h(xk)}>0，f(xk)是下有界的，則{h(xk)}→0.

證明該結(jié)論可以直接由文獻(xiàn)[10]的引理3得到.

引理5若d是式(5)的可行點(diǎn), 則有

(17)

和

(18)

證明該結(jié)論可以直接由文獻(xiàn)[4]的引理4得到.

引理6設(shè)x*∈X是式(1)的可行點(diǎn)，并且在此點(diǎn)處MFCQ(Mangasarian-Fromovitz 約束規(guī)范)條件滿足, 但不是KKT點(diǎn)，則存在x*的一個鄰域N*，正數(shù)ε,μ和κ，對所有的xk∈N*∩X和Δ，其中Δ滿足

(19)

式(1)有一個可行解d，在此點(diǎn)處的預(yù)測減少滿足

(20)

并且

(21)

成立，及

(22)

證明此結(jié)論直接由文獻(xiàn)[4]的引理5得到.

引理8內(nèi)循環(huán)是有限終止的，即內(nèi)循環(huán)經(jīng)過有限步迭代終止.

證明該結(jié)論可以直接由文獻(xiàn)[10]的引理7得到.

定理1假設(shè)H1～H4成立, 由算法生成的序列會滿足以下兩種情形之一：

(A) 式(1)的KKT點(diǎn)被得到.

(B) 存在序列的一個可行聚點(diǎn)，此聚點(diǎn)或者是KKT點(diǎn)，或者不滿足MFCQ條件.

證明下面證明存在一個聚點(diǎn)或者是KKT點(diǎn)或者不滿足MFCQ條件.考慮兩種情況.

第一種情況, 考慮主序列中包含無限個使Hk升級的迭代點(diǎn)，記這樣的迭代點(diǎn)所形成的子序列為S.由引理4, 在S中，有

(23)

因此

(24)

因?yàn)樗械牡c(diǎn)xk都位于X中, 而X是緊的, 因此迭代序列至少有一個聚點(diǎn).因此，可以找到序列S的一個子序列S′，設(shè)x∞為子序列的一個可行聚點(diǎn)，并且S′中Hk被升級.

下面采用反證法，假設(shè)在x∞處滿足MFCQ 條件，但不是KKT點(diǎn).由引理 6，存在x∞的一個鄰域N∞，及ε,μ和κ>0，使得，若μh(xk)≤Δ≤κ滿足，則d為式(5)的可行解，并滿足式(21)和式(22).

(25)

則f-迭代的所有條件都滿足.下面說明將會產(chǎn)生f-迭代.

(26)

當(dāng)k充分大時，式(25)的下界是式(25)上界的二階無窮小.在內(nèi)循環(huán)中，信賴域半徑Δ的連續(xù)減少使得信賴域半徑最終落到式(25)的區(qū)間內(nèi), 或者落到該區(qū)間的右側(cè).當(dāng)信賴域半徑Δ落入式(25)的區(qū)間內(nèi)時，則必產(chǎn)生f-迭代.

當(dāng)信賴域半徑Δ的連續(xù)減少使得信賴域半徑最終落到式(25)的區(qū)間右側(cè)時，因?yàn)閐是式(5)的全局最小值, 當(dāng)Δ減少時，Δq單調(diào)遞減，Δq>0可能會由成立變?yōu)椴怀闪?，但是反之不會成?因此, 內(nèi)循環(huán)通常在一個h-迭代之前可能會有f-迭代，且對任意的Δ≥μh(xk)，不會產(chǎn)生h-迭代.

因此，在此子序列中產(chǎn)生一個f-迭代， 這與此序列中點(diǎn)都是h-迭代組成的矛盾.所以x∞或者是KKT點(diǎn)或者不滿足MFCQ條件.因此情況(B)成立.

第二種情況, 考慮主序列中僅有有限步的h-迭代.存在正數(shù)K，使得對所有的k>K，都是f-迭代.由引理3得h(xk)→0. 因此序列的任何聚點(diǎn)x∞都是可行點(diǎn).

類似于第一種情形,假設(shè)在點(diǎn)x∞處MFCQ條件滿足但不是KKT點(diǎn).由引理6和引理7, 存在x∞點(diǎn)的一個鄰域N∞及ε,μ,κ>0，使得，若

(27)

式(5)是相容的 并且相應(yīng)的試探步d滿足f-迭代的條件和式(20)，(21).

因?yàn)閷τ谒械膋>K的迭代都是f-迭代, 即Hk從第K步迭代以后就不再改變.因此，k>K,Hk中第二大元素Hk2是常數(shù)，這時式(27)的右邊為常數(shù), 與k無關(guān), 而式(27)的左邊收斂到0.因此，當(dāng)k充分大時

在這種情形下, 當(dāng)Δ在內(nèi)循環(huán)減少時, 它最終必須落到式(27)的區(qū)間內(nèi)或者落到式(27)的區(qū)間右側(cè).因?yàn)樵诿恳徊絻?nèi)迭代中Δ每次減少λ倍，并且對于任意的Δ在式(27)的區(qū)間內(nèi)，則產(chǎn)生f-迭代.因此，選擇Δ滿足

(28)

這時f-迭代產(chǎn)生.因此，由式(20)，(21)和(28)得

對于所有充分大的k成立, 這與{f(xk)}是有下界的矛盾.因此，x∞是一個KKT點(diǎn)，在這種情形下，情況(B)成立.

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

本節(jié)將算法給出的數(shù)值結(jié)果列于表1中，所有的測試問題來自文獻(xiàn)[13]中的問題. 問題的編號與文獻(xiàn)[13]中的相同.通過比較本文算法和SNOPT(5.3版)的數(shù)值結(jié)果來證明算法的有效性.SNOPT求解器是目前最流行的求解大規(guī)模非線性規(guī)劃的軟件之一，它本身也是一類采用價值函數(shù)的擬Newton型序列二次規(guī)劃方法.表1中NF為目標(biāo)函數(shù)和約束函數(shù)的計算次數(shù);NG為梯度的計算次數(shù);n表示問題中變量的維數(shù);m表示問題中約束的維數(shù);me表示問題中等式約束的維數(shù).運(yùn)算過程中, B0=I,正定矩陣Bk由阻尼的BFGS方法更新.

表1　數(shù)值結(jié)果

其中參數(shù)選擇如下:γ=10-4,β=1-10-4,σ=0.1,λ1=0.5,λ2=2,ε=10-6,Δ=10,Δmin=10-4,Δmax=100,kH=104，l=3.

數(shù)值結(jié)果表明, 本文算法的數(shù)值結(jié)果比SNOPT求解的數(shù)值結(jié)果好.無罰函數(shù)無濾子的序列二次規(guī)劃方法的步伐接受機(jī)制是有效的.

參考文獻(xiàn):

[1]Gomes F A M, Maciel M C, Martinez J M. Nonlinear programming algorithms using trust regions and augmented Lagrangians with nonmonotone penalty parameters[J]. Math Program, 1999, 84(1):161.

[2]Han S P. A globally convergent method for nonlinear programming[J]. Journal of Optimization Theory and Applications, 1977, 22(3):297.

[3]Fletcher R, Leyffer S. Nonlinear programming without a penalty function[J]. Mathematical Programming, 2002, 91(2):239.

[4]Fletcher R, Leyffer S, Toint P L. On the global convergence of a filter-SQP algorithm[J]. SIAM Journal on Optimization, 2002, 13(1): 44.

[5]Gould N I M, Toint Ph L. Nonlinear programming without a penalty function and a filter[J]. J Comput Math, 2010, 122(1):155.

[6]Yamashita H, Yabe H. A globally convergent trust-region SQP method without a penalty function for nonlinearly constrained optimization[R]. Tokyo: Mathematical Systems Inc, 2003.

[7]Liu X, Yuan Y. A sequential quadratic programming method without a penalty function and a filter for equality constrained nonlinear programming[J]. SIAM J on Optimization, 2011, 21(2):545.

[8]Martinez J M. Inexact-restoration method with Lagrangian tangent decrease and a new merit function for nonlinear programming[J]. J Optim Theory Appl, 2001, 111(1):39.

[9]Martinez J M. Two-phase model algorithm with global convergence for nonlinear programming[J]. Journal of Optimization Theory and Applications, 1998, 96(2): 397.

[10]Huang M X, Pu D G. A trust region SQP method without a penalty or a filter for nonlinear programming[J]. Journal of computational and applied mathematics, 2015, 281(1):107.

[11]Zhu X J, Pu D G. A new double trust regions SQP method without a penalty function or a filter[J]. Computational Applied Mathematics, 2012, 31(2): 407.

[12]Ribeiro A A, Karas W K, Gonzaga C C. Global convergence of filter methods for nonlinear programming[J]. SIAM Journal on Optimization, 2008, 19(2): 1231.

[13]Hock W, Schittkowski K. Test examples for nonlinear programming codes[M]. Berlin, Heidelberg, New York: Springer-Verlag, 1981.

考慮如下非線性規(guī)劃問題:

A New Sequential Quadratic Programming Method Without a Penalty Function or a Filter

WANG Bo1,2, PU Dingguo1

(1. Department of Mathematics, Tongji University, Shanghai 200092, China; 2. School of Mathematics, Nanjing University of Finance and Economics, Nanjing 210023, China)

Abstract：A sequential quadratic programming method without using a penalty function or a filter was proposed. The algorithm computes the overall step in two phases. The first phase is to compute a feasibility step. The feasibility phase aims at reducing the infeasibility measure. The second phase, an optimality phase computes a trial point reducing a quadratic model of the objective function. The feasibility and optimality phases are independent in this algorithm; therefore, any method for reducing constraint violation can be used in the feasibility phase. Under mild conditions, the method can be proved to be globally convergent. Numerical results demonstrate the efficiency of this algorithm.

Key words：sequential quadratic programming; filter; penalty function; nonlinear programming

收稿日期：2015-06-09

基金項目：國家自然科學(xué)基金(11371281,11201221);江蘇省自然科學(xué)基金(BK2012468);江蘇省高校自然科學(xué)基金(14KJD110003)

中圖分類號：O221.2

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

第一作者： 王波(1979—)，男，副教授，博士生，主要研究方向?yàn)閿?shù)學(xué)規(guī)劃.E-mail: 1110468@#edu.cn