解非線性半定規(guī)劃的一種回溯線搜索型算法①

李丹丹，王松華，李遠(yuǎn)飛

1.廣州華商學(xué)院 應(yīng)用數(shù)學(xué)系， 廣州 511300；2.百色學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院， 廣西 百色 533000

考慮如下非線性半定規(guī)劃問(wèn)題(NLSDP)：

(1)

線性半定規(guī)劃[1-2]是優(yōu)化領(lǐng)域中最經(jīng)典的問(wèn)題， 然而眾多實(shí)際問(wèn)題屬于非線性半定規(guī)劃問(wèn)題， 如工程設(shè)計(jì)、 最優(yōu)控制、 經(jīng)濟(jì)、 金融等領(lǐng)域[3-4]． 因此， 非線性半定規(guī)劃的研究具有理論創(chuàng)新和實(shí)際應(yīng)用的意義． 若干有效方法可求解非線性半定規(guī)劃問(wèn)題且其效果顯著， 如增廣拉格朗日方法[5]、 序列半定規(guī)劃方法[6]、 序列線性方程組方法[7]、 乘子法[8]、 原始-對(duì)偶內(nèi)點(diǎn)法[9]， 其中序列半定規(guī)劃方法應(yīng)用較廣． 很多學(xué)者將優(yōu)良的非線性規(guī)劃算法推廣到非線性半定規(guī)劃問(wèn)題中， 如文獻(xiàn)[10]借鑒傳統(tǒng)非線性規(guī)劃的子問(wèn)題修正技術(shù)， 并結(jié)合信賴域框架， 提出了求解非線性半定規(guī)劃的一個(gè)無(wú)可行性恢復(fù)階段的濾子算法． 文獻(xiàn)[11]采用非單調(diào)線搜索技術(shù)來(lái)保證目標(biāo)函數(shù)或約束違反度函數(shù)的充分下降， 從而提出一個(gè)求解非線性半定規(guī)劃的無(wú)罰無(wú)濾序列二次半定規(guī)劃算法． 文獻(xiàn)[12]提出一個(gè)求解帶有不等式約束的非線性規(guī)劃全局收斂性算法， 該算法的接受準(zhǔn)則既不使用罰函數(shù)也不使用濾子， 且效果顯著． 本文在文獻(xiàn)[12]的基礎(chǔ)上， 將該思想推廣到非線性半定規(guī)劃中， 提出一個(gè)求解非線性半定規(guī)劃問(wèn)題的無(wú)罰函數(shù)無(wú)濾子回溯線搜索型序列半定規(guī)劃算法．

1 算法描述

二階連續(xù)可微函數(shù)f(x)的梯度和Hesse矩陣分別記為f(x)和2f(x)． 二階連續(xù)可微向量函數(shù)h(x)： =(h1(x)，h2(x)， …，hp(x))T， 則稱矩陣Dh(x)=(h1(x)，h2(x)， …，hp(x))T∈Rp×n為h(x) 的雅可比矩陣． 二階連續(xù)可微矩陣函數(shù)G(x)， 記其微分算子DG(x)為

且對(duì)任意的d∈Rn

記其伴隨算子DG(x)*為

其中Z∈Sm．

記NLSDP(1)的拉格朗日函數(shù)為

L(x，λ，Y)=f(x)+λTh(x)+〈Y，G(x)〉

其中x∈Rn，λ∈Rp，Y∈Sm．

定義1若x*∈Rn是NLSDP(1)的可行點(diǎn)， 且存在向量λ*∈Rp和矩陣Y*∈Sm滿足如下條件：

xL(x*，λ*，Y*)=f(x*)+Dh(x*)Tλ*+DG(x*)*Y*=0

h(x*)=0，G(x*)?0，Y*0， 〈G(x*)，Y*〉=0

則稱(x*，λ*，Y*)是NLSDP(1)的一個(gè)KKT點(diǎn)對(duì)， (λ*，Y*)是在x*處相對(duì)應(yīng)的拉格朗日乘子．

本文采用線搜索型序列半定規(guī)劃方法框架， 設(shè)當(dāng)前迭代點(diǎn)為xk∈Rn， 定義產(chǎn)生搜索方向的二次半定子問(wèn)題QSD(xk，Bk) 如下：

(2)

其中矩陣Bk∈Rn×n是NLSDP(1)的拉格朗日函數(shù)的Hesse陣或其近似陣． 若QSD(xk，Bk)存在最優(yōu)解， 則記其解為dk． 同時(shí)， 為了度量NLSDP(1)的約束可行性， 下面給出其約束違反度函數(shù)的定義：

θ(x)=λ1(G(x))++‖h(x)‖

其中λ1(A)表示矩陣A的最大特征值， (α)+=max{0，α}， (λ1(G(x)))+簡(jiǎn)記為λ1(G(x))+． 顯然， 若θ(x)=0， 則x為NLSDP(1) 的可行解．

(3)

pred(xk)=-f(xk)Tdk

(4)

因此， 定義目標(biāo)函數(shù)f(x)的非單調(diào)充分下降性條件：

nared(xk)≥ηαk，lpred(xk)

(5)

其中η∈(0， 1)， 這不同于單調(diào)充分下降性條件：

(6)

(7)

其中β∈(0， 1)．

最后， 下面給出算法的接受準(zhǔn)則． 如果約束違反度函數(shù)θ(x)滿足非單調(diào)充分下降性條件， 即(7)式成立， 或目標(biāo)函數(shù)f(x)具有適當(dāng)?shù)南陆盗壳壹s束違反度函數(shù)值有個(gè)合理的上界， 即

(8)

成立， 其中γ∈(0， 1)． 那么考慮以下兩種情況．

1) 若

pred(xk)≤ξ(dk)TBkdk

(9)

且

(10)

2) 若

pred(xk)>ξ(dk)TBkdk

(11)

(12)

其中γα∈(0， 1)，sθ≥1．

可行性恢復(fù)階段的具體細(xì)節(jié)見(jiàn)文獻(xiàn)[10]．

基于以上討論， 下面給出求解NLSDP(1)的算法描述：

算法1

步驟1令flag=0， 求解子問(wèn)題QSD(xk，Bk)． 若QSD(xk，Bk)存在最優(yōu)解， 則記為dk， 否則算法進(jìn)入可行性恢復(fù)階段， 轉(zhuǎn)步驟7． 若dk=0， 則算法停止．

步驟3(回溯線搜索)

步驟3.1令l=0，αk，0=1．

步驟3.3若(7)式和(8)式不成立， 則轉(zhuǎn)步驟3.5．

步驟3.4若(9)式和(10)式成立， 則令flag=1， 轉(zhuǎn)步驟4． 若(5)式和(11)式成立， 則轉(zhuǎn)步驟4．

步驟3.5令αk， l+1=ραk， l，l=l+1， 轉(zhuǎn)步驟3.2．

步驟4令αk=αk， l，xk+1=xk+αkdk．

步驟6(更新步)利用某種方法， 更新Bk為對(duì)稱正定矩陣Bk+1． 令k=k+1， 轉(zhuǎn)步驟1．

2 全局收斂性

本節(jié)將分析算法1的全局收斂性， 為此， 需作如下合理假設(shè)：

(B1) 迭代點(diǎn)列{xk}和{xk+αk，ldk}在緊凸集χ中．

(B2)f(x)，h(x)，G(x)在緊凸集χ中二階連續(xù)可微．

(B3) 矩陣Bk為對(duì)稱正定矩陣， 且存在常數(shù)a，b>0， 對(duì)任意的d∈Rn有a‖d‖2≤dTBkd≤b‖d‖2．

注1不失一般性， 由假設(shè)B可知， 對(duì)于任意x∈χ， ‖2f(x)‖≤b， ‖D2h(x)‖≤b， ‖D2G(x)‖≤b．

引理1對(duì)于任意的k， 以下不等式成立：

于是有

因此， 當(dāng)k充分大時(shí)

2) 假定θ型迭代發(fā)生無(wú)限次， 那么存在指標(biāo)k2， 使得當(dāng)k>k2時(shí)，θ型迭代發(fā)生， 由(10)式和引理2， 可知結(jié)論成立．

引理4在假設(shè)B條件下， 子問(wèn)題QSD(xk，Bk)的可行解d滿足以下不等式：

(13)

(14)

證由(3)式、 (4)式、 Taylor展開(kāi)式和假設(shè)B可得

其中ξ1介于xk和xk+αk，ld之間． 類(lèi)似地， 由Taylor展開(kāi)式可推出

引理5在假設(shè)B成立下， NLSDP(1)的可行點(diǎn)x*滿足MFCQ條件， 但不是KKT點(diǎn)． 那么存在x*的鄰域N(x*)及正常數(shù)η1， 使得當(dāng)xk∈N(x*)∩χ時(shí)， 子問(wèn)題QSD(xk，Bk)的可行集非空， 且其最優(yōu)解dk滿足

(15)

證類(lèi)似文獻(xiàn)[14]的引理4.7可證結(jié)論成立．

引理6在假設(shè)B條件下，dk是子問(wèn)題QSD(xk，Bk)的最優(yōu)解， 那么若

(16)

且

(17)

證若

則由引理4和引理5得

故nared(xk)≥ηαk，lpred(xk)成立． 結(jié)合引理4和引理5， 由(16)和(17)式有

故nared(xk)≥γθ(xk+αk，ldk)成立．

引理7在假設(shè)B條件下， 線搜索(步驟3)是有限步終止的．

綜上所述， 若

(18)

則xk+αk，ldk被算法所接受，f型迭代發(fā)生， 矛盾．

定理1若假設(shè)B成立， 則下面結(jié)論之一成立：

(C2) 算法有限步終止， 即存在某個(gè)迭代點(diǎn)xk為NLSDP(1)的KKT點(diǎn)．

(C3) 算法產(chǎn)生的迭代點(diǎn)列{xk}收斂于聚點(diǎn)x*且該聚點(diǎn)x*為NLSDP(1)的可行解， 那么x*或是NLSDP(1)的KKT點(diǎn)， 或是x*不滿足MFCQ條件．

證不失一般性， 假設(shè)結(jié)論(C1)和(C2)都不成立， 下面討論兩種情況分別證明結(jié)論(C3)成立．

即x*是NLSDP(1)的可行點(diǎn)．

3 數(shù)值試驗(yàn)

為了驗(yàn)證算法1的可行性， 本節(jié)給出了算法的初步數(shù)值實(shí)驗(yàn)， 采用MATLAB(2014a)軟件實(shí)現(xiàn)算法， 程序在配置Windows 10， 8G RAM， 3.60 GHz CPU的計(jì)算機(jī)上運(yùn)行． 子問(wèn)題QSD(xk，Bk)使用文獻(xiàn)[15] SDPT3求解． 算法采用BFGS公式對(duì)Bk更新為Bk+1， 其更新公式見(jiàn)文獻(xiàn)[16]． 下面給出算例問(wèn)題如下：

1) Rosen-Suzuki問(wèn)題： 測(cè)試算例來(lái)源于文獻(xiàn)[17]：

其數(shù)值結(jié)果見(jiàn)表1．

2) SOFP問(wèn)題． 測(cè)試算例來(lái)源于文獻(xiàn)[18]：

其中：QF=CTFTFC+I；AF=A+BFC； 矩陣變量L為實(shí)對(duì)稱的； 矩陣變量F不是方陣；A，B，C為常量矩陣． 該問(wèn)題的數(shù)值結(jié)果見(jiàn)表2．

表2 SOFP問(wèn)題數(shù)值結(jié)果

3) NCMP問(wèn)題． 測(cè)試算例來(lái)自于文獻(xiàn)[9]：

其中：A=(aij)(∈Sm)是給定的， 且其對(duì)角線元素aii=1(i=1，2，…，m)， 其余元素隨機(jī)取自[-1， 1]； 選取ε=10-3． 數(shù)值結(jié)果見(jiàn)表3．

表3 NCMP問(wèn)題數(shù)值結(jié)果

在數(shù)值試驗(yàn)中， 選取的參數(shù)如下：

η=0.001，τ=0.01，ξ=0.01，γ=0.001，γα=0.99，sθ=2，β=0.999，ρ=0.5

終止準(zhǔn)則為‖dk‖≤10-4， 設(shè)置算法1的迭代次數(shù)上限為200． 下面給出表1-3中的符號(hào)含義如下：x0為初始點(diǎn)；Ndf為目標(biāo)函數(shù)梯度計(jì)算次數(shù)； problem為COMPleib算例庫(kù)算例名稱；Iter為算法迭代次數(shù)；n為自變量維數(shù)；ri為可行性恢復(fù)階段使用次數(shù)；p為等式約束的維數(shù)；θ*為最優(yōu)點(diǎn)約束違反度函數(shù)值；m為半定約束矩陣維數(shù)；f*為最優(yōu)目標(biāo)函數(shù)值；Nf為目標(biāo)函數(shù)計(jì)算次數(shù)；t為計(jì)算機(jī)運(yùn)行時(shí)間(含可行性恢復(fù)階段用時(shí))．

表1 Rosen-Suzuki問(wèn)題數(shù)值結(jié)果

續(xù)表2

4 小結(jié)

本文提出一種新的求解非線性半定規(guī)劃的無(wú)罰無(wú)濾回溯線搜索型序列半定規(guī)劃算法， 新方法基于傳統(tǒng)的二次規(guī)劃子問(wèn)題構(gòu)建二次半定子問(wèn)題， 通過(guò)求解該子問(wèn)題產(chǎn)生搜索方向， 為了避免使用罰函數(shù)和濾子， 采用回溯線搜索技術(shù)來(lái)保證目標(biāo)函數(shù)值或約束違反度函數(shù)值充分下降． 而非單調(diào)的充分性下降條件使得試探點(diǎn)更加容易被算法接受． 同時(shí)在合理的假設(shè)條件下， 證明了該算法的適定性以及全局收斂性， 最后初步的數(shù)值試驗(yàn)結(jié)果表明了該算法的有效性．