求解具有非精確信息的非光滑凸半無限規(guī)劃束方法

吳 奇，田 琦，龐 麗 萍

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

0 引 言

半無限規(guī)劃是指具有有限數(shù)量的決策變量和無限數(shù)量的約束的數(shù)學(xué)規(guī)劃，其在數(shù)學(xué)、經(jīng)濟(jì)學(xué)和工程學(xué)等領(lǐng)域都有著廣泛的應(yīng)用．給定一點(diǎn)，檢查它的可行性需要檢查無數(shù)個(gè)約束，或者等價(jià)地求解一個(gè)全局優(yōu)化問題，并且伴隨著迭代不斷進(jìn)行，全局優(yōu)化問題逐漸發(fā)生變化．目前求解半無限規(guī)劃問題的數(shù)值方法主要有離散化方法、交換集方法、下降方法和牛頓型方法等[1-4]．然而，所有的這些方法都需要計(jì)算目標(biāo)函數(shù)和約束函數(shù)的梯度，因此無法應(yīng)用到函數(shù)是非光滑的情況．除此之外，F(xiàn)uduli等考慮了用非光滑方法求解光滑半無限極小極大問題，他們?cè)试S通過隱式方法得到內(nèi)部最大問題的非精確解[5]．Pang等研究了非光滑半無限規(guī)劃的數(shù)值方法[6-8]，他們利用非精確方法和離散化方法將半無限規(guī)劃問題轉(zhuǎn)化為一系列有限約束優(yōu)化問題并通過束方法進(jìn)行求解．

對(duì)于一些問題，函數(shù)值可能無法精確計(jì)算或者精確計(jì)算的代價(jià)太大，如無導(dǎo)數(shù)優(yōu)化、大規(guī)模拉格朗日或半定松弛以及隨機(jī)模擬，這種情況往往只能得到非精確信息(或者稱為受噪聲污染的信息)．對(duì)于采用非精確信息的非光滑優(yōu)化問題，已有不少研究成果．Kiwiel提出了一種束方法可以處理函數(shù)和次梯度值是非精確的問題，其中設(shè)置噪聲是漸近消失的[9]．束方法中，Hintermüller首次考慮了不消失型擾動(dòng)，文中只有次梯度值是非精確的，而函數(shù)值必須是精確的[10]．Solodov考慮函數(shù)與次梯度都是非精確的并且不會(huì)漸近消失的[11]．van Ackooij等提出了一種方法求解基于非精確信息的非光滑帶約束問題[12]．de Oliveira等給出了凸情況下非精確束方法的統(tǒng)一理論，概括了已經(jīng)存在的多種處理噪聲的束方法[13]．Hare等提出了一種束方法求解基于非精確信息的非光滑非凸無約束優(yōu)化問題[14]．

本文考慮如下半無限規(guī)劃問題：

s.t.g(x，ω)≤0；?ω∈Ω

考慮下水平問題：

當(dāng)采用非精確方法求解下水平問題的非精確解時(shí)，原始問題(1)可以轉(zhuǎn)化為一個(gè)基于非精確信息的非光滑有限約束問題．值得注意的是，當(dāng)約束函數(shù)g關(guān)于ω是非凸的情況，下水平問題的求解是困難的，并且每進(jìn)行一次迭代就需要一次非精確全局優(yōu)化．

本文主要研究具有非精確信息的非光滑凸半無限問題的數(shù)值解法．對(duì)于下水平問題，本文將采用離散化方法將下水平問題進(jìn)行近似．具體地，通過選擇集合Ω的有限子集對(duì)其進(jìn)行替換，將原始非光滑半無限規(guī)劃問題轉(zhuǎn)化為一系列非光滑有限約束規(guī)劃問題．在迭代過程中，約束函數(shù)是不斷發(fā)生變化的．

1 算 法

令k為當(dāng)前迭代指標(biāo)，xk表示當(dāng)前迭代點(diǎn)(或稱為穩(wěn)定中心)．此外，迭代過程中還將產(chǎn)生一系列試探點(diǎn){yj}j∈Jk，Jk?{0，1，…，k}．并且有xk∈{yj}j∈Jk．因此存在一個(gè)指標(biāo)ck=j，j∈Jk使得xk=yj．定義Ωk={ωq|q=1，2，…，Qk}?Ω，為Ω的一個(gè)細(xì)分．

定義Ω與Ωk之間的Hausdorff距離如下：

其中

(1)

ρk、σk滿足如下條件：

(2)

因此可以定義近似割平面模型如下：

(3)

其中

(4)

接下來求解二次規(guī)劃問題：

下面介紹問題(2)解的特征：

(5)

其中IX表示集合X的指示函數(shù)，?IX(yk+1)等于X在點(diǎn)yk+1處的法錐．令

(6)

(7)

為了刻畫求解問題(1)的進(jìn)度，本文采用了如下的預(yù)測下降量：

(8)

其中αk∈[0，2]．根據(jù)式(6)和(8)可以得到

(9)

則認(rèn)為由不精確信息引入的噪聲太大．為了數(shù)值上的通用性，本文考慮更一般的噪聲測量準(zhǔn)則：

(10)

其中βk∈(-1，1-αk-B]，B>0．當(dāng)上述關(guān)系成立時(shí)，噪聲被認(rèn)為太大，此時(shí)需要執(zhí)行噪聲衰減：保持穩(wěn)定中心和近似割平面模型不變，減小迫近參數(shù)μk．

對(duì)于模型(3)，除了要檢查噪聲是否可以接受，還需要對(duì)Ωk進(jìn)行選取．Ωk的選取對(duì)算法的計(jì)算效率影響較大．Ωk中包含元素過多會(huì)導(dǎo)致計(jì)算約束函數(shù)時(shí)付出的時(shí)間代價(jià)大．反過來，當(dāng)Ωk中包含元素過少，盡管計(jì)算約束函數(shù)的時(shí)間代價(jià)小，但是會(huì)導(dǎo)致模型與原問題偏差較大，也就是說計(jì)算的解的可行性犧牲很大．當(dāng)細(xì)分發(fā)生變化時(shí)，約束函數(shù)會(huì)發(fā)生變化，因此要較少地更新細(xì)分．本文引入如下準(zhǔn)則來確定是否執(zhí)行噪聲衰減步或者細(xì)化步(更新細(xì)分)．

(11)

(12)

(13)

注意，條件(11)等價(jià)于不等式(10)，用于判斷當(dāng)前迭代噪聲是否可以接受．通過選擇參數(shù)αk、βk可以更靈活地控制噪聲衰減．條件(12)和(13)用于控制細(xì)分的更新并以此降低計(jì)算約束函數(shù)的時(shí)間代價(jià)．

如果Ωk需要細(xì)化，選擇新的Ωk+1滿足如下條件：

Ωk+1?Ωk，Dk+1

(14)

當(dāng)噪聲被宣布為可接受的并且當(dāng)前細(xì)分不需要被細(xì)化時(shí)，需要判斷最新產(chǎn)生的試探點(diǎn)是否足夠好，即是否可以成為下一個(gè)穩(wěn)定中心．下面給出下降條件：

(15)

當(dāng)上述關(guān)系成立時(shí)，該迭代被宣布為下降步，穩(wěn)定中心轉(zhuǎn)移到新的試探點(diǎn)：xk+1=yk+1．否則，該迭代被聲明為空步，穩(wěn)定中心不發(fā)生變化：xk+1=xk，新的試探點(diǎn)信息被加入近似割平面模型中用來豐富模型．注意到，當(dāng)gk，ck>0時(shí)，若式(15)成立，則有g(shù)k，k+1-gk，ck≤-mδk．當(dāng)gk，ck≤0時(shí)，若式(15)成立，則有fk+1-fck≤-mδk．由此可以看出，下降條件(15)背后的基本原理是通過以下兩種方式之一來衡量實(shí)現(xiàn)問題(1)最小化的進(jìn)展：

①穩(wěn)定中心可行的情況，重點(diǎn)放在降低目標(biāo)值而又不降低穩(wěn)定中心的可行性；

②穩(wěn)定中心不可行的情況，重點(diǎn)放在降低穩(wěn)定中心的不可行性．

下面給出求解問題(1)的具體算法．

算法1

步驟2(1)如果條件(11)和(12)成立，選擇μk+1∈(0，μk)并轉(zhuǎn)步驟3．

(2)條件(11)不成立．如果δk≤γ2，停止迭代．否則，轉(zhuǎn)步驟5．

步驟6置xk+1=xk，ρk+1=ρk，σk+1=σk，Jk+1=Jk，ck+1=ck．置k=k+1并轉(zhuǎn)步驟1．

當(dāng)?shù)鷎+1是空步時(shí)，即xk+1=xk，根據(jù)步驟5(2)可以得到

2 收斂性結(jié)果

假設(shè)2[8]假設(shè)Slater約束規(guī)范成立，即存在x∈X，使得g(x，ω)<0，?ω∈Ω成立．

命題1[12]在假設(shè)1下，存在常數(shù)M，M′>0，使得

現(xiàn)在分析算法1無限循環(huán)時(shí)出現(xiàn)的不同情況：

(1)無限多次細(xì)化迭代(步驟3中Ωk+1更新發(fā)生無限多次)．

(2)有限數(shù)量細(xì)化迭代．在這種情況下，又可以具體分成下列兩種情況：

①無限多次下降迭代(步驟5(1)執(zhí)行了無限多次)．

②有限數(shù)量迭代后穩(wěn)定中心保持不變．在這種情況下，又可以具體分成下列兩種情況：

a.無限多次噪聲衰減(步驟2(2)執(zhí)行了無限多次)．

b.有限數(shù)量噪聲衰減后，最終僅執(zhí)行空步．

上述情況是互斥的，即只有其中一種情況會(huì)發(fā)生．首先考慮有限數(shù)量細(xì)化迭代發(fā)生的情況．

證明由文獻(xiàn)[12]中的引理3.1易證明Ξk+vk→0，δk→0，當(dāng)K1k→∞．證明第2個(gè)結(jié)論采用反證法．假設(shè)由算法1步驟3可得對(duì)任意的k>因?yàn)槭亲詈笠徊郊?xì)化步，對(duì)任意的k∈K1，都有這與δk→0，k∈K1相矛盾，因此有

證明由文獻(xiàn)[12]中的引理3.2易證明Ξk+vk→0，Ek<0，當(dāng)K2k→∞．證明第2個(gè)結(jié)論采用反證法．假設(shè)由算法1步驟3可得對(duì)任意的k>因?yàn)槭亲詈笠徊郊?xì)化步，對(duì)任意的k∈K2，都有這與Ξk+vk→0，k∈K2相矛盾，因此有

證明由文獻(xiàn)[12]中的引理3．3易證明Ξk+vk→0，δk→0，當(dāng)K3k→∞．第2個(gè)結(jié)論可以用與證明引理1相同的方法得到．

根據(jù)文獻(xiàn)[8]中的引理8，可以得到如下引理．

定理1令假設(shè)1和2成立，假設(shè)算法1產(chǎn)生無限多循環(huán)，如果存在無窮指標(biāo)集K使得

此外，如果K?K4，則有

〈Ξk+vk，xk-y〉

3 數(shù)值算例

表1 數(shù)值結(jié)果Tab.1 Numerical results

圖1 不同噪聲結(jié)果比較Fig.1 Comparison of results of different noise

例1考慮如下算例[15]：

s.t.(1+ω2)2-x1-x2ω-x3ω2-x4ω3≤0；

?ω∈[0，1]

其中

11x3-3x4-80

21x3-3x4-100

例2考慮如下算例[8]：

s.t.x1+x2ex3ω-e2x1ω+sin(4ω)≤0；

?ω∈[0，1]

例3考慮如下算例[16]：

s.t.|φT(ω)x-1|≤0.057 5；?ω∈[0，0.05]

|φT(ω)x|≤0.01；?ω∈[0.1，0.5]

其中

φ(ω)=(2cos(2×17πω)… 2cos(2πω)1)T

4 結(jié) 語

本文提出一種離散化束方法，來求解具有非精確信息的非光滑凸半無限規(guī)劃問題．在目標(biāo)函數(shù)只能獲取非精確信息的情況下，通過選擇帶參數(shù)型的改進(jìn)函數(shù)，證明了在適當(dāng)條件下迭代點(diǎn)的任何聚點(diǎn)對(duì)于原始問題都是可行的．通過與算法2、3進(jìn)行比較，可以得到算法1在求解半無限規(guī)劃問題時(shí)更加有效且穩(wěn)定．此外數(shù)值實(shí)驗(yàn)也表明，算法1在求解具有不同類型噪聲的凸半無限規(guī)劃問題時(shí)具有有效性．