王 曉 亮， 吳 奇， 田 玉 銖， 龐 麗 萍

( 大連理工大學(xué) 數(shù)學(xué)科學(xué)學(xué)院, 遼寧 大連 116024 )

0 引 言

考慮下面的約束問題：

其中目標(biāo)函數(shù)f：Rn→R是局部lower-c2的，約束函數(shù)hi：Rn→R，i=1，2，…，m是凸的，但目標(biāo)函數(shù)與約束函數(shù)都不必是可微的．注意到上面的問題可以轉(zhuǎn)化為只包含一個約束的問題，具體地：若定義h(x)=max{hi(x)，i=1，2，…，m}，則原問題轉(zhuǎn)化為

顯然，函數(shù)h(x)也是定義在Rn上的凸函數(shù)．接下來，本文致力于該問題的求解．

濾子類方法(filter type methods)是求解約束問題的一類十分有效的方法[1-4]，它經(jīng)常涉及Pareto-domination準(zhǔn)則，即：xdominatesy當(dāng)且僅當(dāng)f(y)≥f(x)和h+(y)≥h+(x)，其中h+(x)=max{h(x)，0}．濾子算法中，一個候選點可以作為新的下降步的前提是這個點不能被先前的迭代點所支撐(domination)．這表明新的迭代點會獲得下降的目標(biāo)函數(shù)值或者較小的約束違反度(即較小的h+(x)值)．

文獻[4]采取了濾子策略和鄰近束算法結(jié)合的思想來求解凸規(guī)劃問題．本文將上述方法拓展來求解非凸非光滑問題．具體地，首先將凸化技術(shù)作用于目標(biāo)函數(shù)，以增強目標(biāo)函數(shù)的凸性；再利用改進函數(shù)算法將新獲得的約束問題轉(zhuǎn)化為無約束問題，同時采用鄰近束算法技術(shù)和濾子策略對無約束問題進行求解．文獻[7]中，針對一類非凸非光滑約束問題，作者提出了一種鄰近濾子束算法．雖然算法近似，但存在著一些不同．具體的，與文獻[7]相比，本文中改進函數(shù)的建立、相應(yīng)切平面模型的構(gòu)造和濾子策略的選取是不同的．

1 算法基礎(chǔ)

假設(shè)1給定初始點x0和一個正參數(shù)M0，水平集T0滿足

T0∶={x∈Rn：f(x)≤f(x0)+M0}?O

其中O是一個有界開集．

假設(shè)2假設(shè)Slater約束規(guī)范成立，即存在x∈Rn，使得h(x)<0成立．

(1)

其中Il?{0，1，…，l}是束的指標(biāo)集．下面建立一個增廣的函數(shù)ψl(y)：

(2)

(3)

由Φl(y)的定義可知問題(3)有唯一的解．束方法中常常涉及預(yù)測下降量，它的定義為

(4)

由yl+1的定義可得δl+1≥0．

下面介紹本文所采用的濾子技術(shù)，可參見文獻[4]．首先給定兩個參數(shù)γf，γh∈(0，1)．這里將利用這兩個參數(shù)來定義當(dāng)前禁止域(forbidden region)、濾子(filter)和當(dāng)前臨時點對(temporary pair)．具體地，在當(dāng)前的下降指標(biāo)k，濾子Hk由下面的點對構(gòu)成，其中xi(i

(5)

定義當(dāng)前臨時點對：

(6)

2 算法及其特性

算法1求解非凸非光滑約束問題的鄰近濾子束算法．

(7)

定義當(dāng)前的禁止域：

(8)

步驟2(模型產(chǎn)生與QP子問題)．已知當(dāng)前的穩(wěn)定中心xk，當(dāng)前的束信息Bl，參數(shù)μl和ηl．由式(2)計算當(dāng)前的逐點切平面模型Φl(y)．求解問題(3)來獲得新的試探點yl+1，由式(4)來計算δl+1．

步驟3(停止準(zhǔn)則)．若δl+1≤T，則停止．

步驟4(鄰近參數(shù)的更新)．若πl(wèi)(yl+1)>πl(wèi)(xk)+M0，稱這個增長是不可接受的，并更新鄰近參數(shù)μl=Γμμl返回步驟2，否則置μl+1=μl．

h+(xk)≤m1δl+1；
ψl(yl+1)≤ψl(xk)+h+(xk)-m2δl+1

(9)

則稱yl+1為新的穩(wěn)定中心，并轉(zhuǎn)至凸化參數(shù)更新步；否則，轉(zhuǎn)下一步．

步驟6(下降測試)．若條件

πl(wèi)(yl+1)≤πl(wèi)(xk)-ζδl+1

(10)

成立，則轉(zhuǎn)至恢復(fù)步，否則為零步(null step)．

步驟7(恢復(fù)步)．計算yl+1使得

(11)

稱yl+1為新的穩(wěn)定中心．

步驟8(凸化參數(shù)的更新)．應(yīng)用下面的準(zhǔn)則來更新凸化參數(shù)η：

(12)

3 算法分析

Lower-c2函數(shù)都是局部Lipschitz連續(xù)的．由T0是緊的，因此函數(shù)f和h在集T0上都是全局Lipschitz連續(xù)的．由πl(wèi)(·)的定義，可知πl(wèi)(·) 在集T0上也是Lipschitz連續(xù)的并記相應(yīng)的Lipschitz常數(shù)為L．

引理1(鄰近參數(shù)穩(wěn)定性)．迭代點序列{yl}由算法1產(chǎn)生，當(dāng)前下降點xk在束信息中且它對應(yīng)的迭代指標(biāo)為lk，即xk=ylk．則在算法的步驟2和步驟4之間只有有限多次循環(huán)．

□

□

引理3對于算法1，下面的關(guān)系成立：

(i)給定k，若產(chǎn)生新的下降點xk+1，則下面兩個條件至少一個成立：

h+(xk+1)<γhh+(xk)

ψl(xk+1)<ψl(xk)-γfh+(xk)

(v)任意給定i∈N，若存在參數(shù)p≥1，使得xi+p為下降點，則xi+p?Hi+1成立．

證明可參見文獻[4]中命題1的證明過程，這里略去其證明．

□

接下來證明算法是合理的．在此之前，下降測試條件(10)等價于下面兩個式子的組合，即

ψl(yl+1)-f(xk)≤h+(xk)-ζδl+1

(13)

與

h(yl+1)≤h+(xk)-ζδl+1

(14)

引理4算法1是合理的．

證明類似于文獻[4]中命題2的證明過程，由引理1～3可得出結(jié)論成立．

□

4 收斂性分析

下面給出算法1的全局收斂性分析．束方法產(chǎn)生的迭代點分為兩類：下降步和零步．依據(jù)下降點是否無限，收斂性證明分為兩部分．首先給出產(chǎn)生有限個下降點的情形．

證明相似的證明參見文獻[4]中的定理4.1 與文獻[11]中的引理2.2．

□

證明若xk不是問題的解，則由文獻[6]中的定理4.5可得下降條件(10)在有限多零步后將得到滿足，除非步驟5中的濾子測試首先得到滿足(注意到在下降條件滿足前，算法不進入恢復(fù)步)．若濾子測試首先滿足，則產(chǎn)生新的下降點．若下降條件首先得到滿足，則由引理4可知，下降條件比濾子測試早滿足的前提是xk是不可行點．這種情形下，將進入恢復(fù)步．引理4表明這種情形下也將產(chǎn)生新的下降點．因此綜上所述，若xk為當(dāng)前的下降步但不是問題的解，則算法1將產(chǎn)生新的下降點xk+1．

□

下面本文用兩個引理分兩種情形討論有無限多下降步的情況．一種是下降步的極限點為可行點，另一種是下降步的極限點為不可行點．它們的證明可參見文獻[4]中的命題4和5．

ψl(ki)(xki)-ψl(ki+1)(xki+1)≥ζξ/2

(15)

特別地，對所有i≥i0的迭代都是ψ迭代．

接下來，假設(shè)下降步點列中僅有有限步對應(yīng)著h+迭代，即存在一個指標(biāo)k0使得對所有的k≥k0的下降步都對應(yīng)著ψ迭代，因此序列{ψl(k)(xk)}k≥k0是單調(diào)遞減的．下降步是有界的，從而有下面的極限式成立：

ψl(k)(xk)-ψl(k+1)(xk+1)→0

(16)

□

5 數(shù)值實驗

本文測試算法1的數(shù)值表現(xiàn)并與文獻[12]中的算法(簡記為PPBM算法)進行比較．PPBM算法是利用懲罰函數(shù)策略結(jié)合鄰近束方法來求解非凸非光滑約束問題．所有的測試都是在設(shè)備為2.10 GHz CPU和16 GB RAM的電腦上進行的．二次規(guī)劃求解器采用的是MATLAB R2016b中的Quadprog.m．

圖1 目標(biāo)函數(shù)f1(x)圖

圖2 目標(biāo)函數(shù)f2(x)圖

0.5 0.5 0.5)為可行點(F)；點x0=(1 -1 1 -1)為邊界點(BD)；點x0=(10 -10 10 -10)為不可行點(IF)．

算法1的參數(shù)設(shè)置如下：m1=0.1，m2=0.5，ζ=0.05，γf=0.000 1，γh=0.999 9，μ0=2，η0=0，Γμ=2，Γη=0，M0=5，T=10-5．PPBM算法的參數(shù)采用文獻[12]中默認的但置T=10-5．詳細的數(shù)值結(jié)果見表1，其中問題表示約束問題的組成，如f1-h1表示目標(biāo)函數(shù)為f1(x)，約束函數(shù)為h1(x)；初始點表示選取的初始點的各種類型，即可行點、不可行點與邊界點；Nk表示下降步的次數(shù)；Ni表示迭代的次數(shù)；f*表示算法最終獲得的函數(shù)值．?dāng)?shù)值實驗表明算法1能夠得到更精確的函數(shù)值，表明了算法的有效性．

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

6 結(jié) 語

本文研究了一類特殊的非凸非光滑約束優(yōu)化問題，這類問題在很多重要領(lǐng)域都有廣泛的應(yīng)用．設(shè)計算法時，首先利用凸化技術(shù)對非凸的目標(biāo)函數(shù)進行凸化，接著利用改進函數(shù)將修正的約束優(yōu)化轉(zhuǎn)化為無約束問題，最后利用鄰近束算法來處理無約束優(yōu)化問題．本文還分析了算法的合理性和收斂性．在數(shù)值實驗部分，考慮了4個約束優(yōu)化問題和每個問題涉及3個不同的初始點(可行點、不可行點、邊界點)．通過與相應(yīng)算法的比較，可以得出針對上面的問題，本文的算法會得到更精確的函數(shù)值，從而驗證了算法的有效性．