吳 奇，田 琦，龐 麗 萍

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

0 引 言

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

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

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

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

考慮下水平問題：

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

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

1 算 法

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

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

其中

(1)

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

(2)

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

(3)

其中

(4)

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

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

(5)

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

(6)

(7)

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

(8)

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

(9)

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

(10)

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

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

(11)

(12)

(13)

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

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

Ωk+1?Ωk，Dk+1

(14)

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

(15)

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

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

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

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

算法1

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

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

步驟6置xk+1=xk，ρk+1=ρk，σk+1=σk，Jk+1=Jk，ck+1=ck．置k=k+1并轉步驟1．

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

2 收斂性結果

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

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

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

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

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

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

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

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

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

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

證明由文獻[12]中的引理3.1易證明Ξk+vk→0，δk→0，當K1k→∞．證明第2個結論采用反證法．假設由算法1步驟3可得對任意的k>因為是最后一步細化步，對任意的k∈K1，都有這與δk→0，k∈K1相矛盾，因此有

證明由文獻[12]中的引理3.2易證明Ξk+vk→0，Ek<0，當K2k→∞．證明第2個結論采用反證法．假設由算法1步驟3可得對任意的k>因為是最后一步細化步，對任意的k∈K2，都有這與Ξk+vk→0，k∈K2相矛盾，因此有

證明由文獻[12]中的引理3．3易證明Ξk+vk→0，δk→0，當K3k→∞．第2個結論可以用與證明引理1相同的方法得到．

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

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

此外，如果K?K4，則有

〈Ξk+vk，xk-y〉

3 數(shù)值算例

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

圖1 不同噪聲結果比較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 結 語

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