李向榮，黎鵬，盧俊宇，袁功林*

(1.廣西大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院， 廣西 南寧 530004; 2.廣西大學(xué) 商學(xué)院， 廣西 南寧 530004)

0 引言

考慮如下的最優(yōu)化問題：

min{f(x)∣x∈Rn},

(1)

其中f:Rn→R并且f∈C2。求解該該模型的方法有牛頓法、擬牛頓法、信賴域方法和共軛梯度法等，其中共軛梯度法因結(jié)構(gòu)簡單，存儲量小被廣泛使用。常見的求解問題式(1)的共軛梯度算法迭代公式為

xk+1=xk+αkdk,

(2)

其中,xk是當(dāng)前迭代點，dk是搜索方向，αk為沿著搜索方向的步長，k=0,1,2,…。搜索方向dk定義如下：

(3)

其中，βk∈R，不同的βk決定不同的共軛梯度算法[1-9]。著名的PRP算法公式[10-11]中βk有如下形式：

(4)

其中，gk=g(xk)=f(xk)，gk+1=g(xk+1)=f(xk+1)分別是xk和xk+1處的梯度。PRP算法能有效處理大規(guī)模優(yōu)化問題，并且數(shù)值表現(xiàn)優(yōu)越，但其收斂性不理想。如在下列弱Wolfe-Powell(WWP)線搜索下，它不能滿足非凸函數(shù)的全局收斂性。

(5)

和

(6)

(7)

和

(8)

① 搜索方向滿足充分下降性;

② 在YWL線搜索下新算法對一般函數(shù)具有全局收斂性;

③ 對大規(guī)模優(yōu)化問題來說新算法比PRP算法優(yōu)秀。

本文所用記號如下：gk為目標(biāo)函數(shù)，f(x)在點xk處的梯度，‖·‖為向量的歐氏范數(shù)。

1 目標(biāo)與算法

PRP算法對一般方程來說不滿足全局收斂性的一個重要原因在于它不具有充分下降性，TOUATI-AHMED等[13], AL-BAALI[14], GILBERT等[15], HU等[16]表明了對共軛梯度法來說充分下降性是保證全局收斂性的關(guān)鍵。而王博朋等[17]提出了如下的一種三項共軛梯度法公式的搜索方向：

(9)

上述算法能求解如下的非線性方程組：

q(x)=0,x∈Rn，

(10)

其中，q:Rn→Rn連續(xù)可微且單調(diào)。筆者發(fā)現(xiàn)其中的qk是一個n維向量，是該非線性方程組的解，使得q(x)=0?？紤]如式(1)無約束優(yōu)化問題中的g(x)→0，這兩者之間是否有聯(lián)系，下面就來證明一下。

算法(1)步驟如下：

Step1:給定初始點x0∈Rn,ε∈(0，1)，δ∈(0，1/2)，δ1∈(0，δ)，σ∈(δ，1)，令k=1。

Step3:用YWL線搜索選出αk。

Step4:令迭代公式為xk+1=xk+αkdk。

Step6:通過:

(11)

Step7:令k:=k+1并且轉(zhuǎn)到step 2。

2 下降性和收斂性的證明

為了證明算法(1)的全局收斂性，現(xiàn)提出必要的假設(shè)條件:

假設(shè)1：① 水平集Ω={x∈Rn|f(x)≤f(x0)}是有界的。

② 函數(shù)f有下界，可微，還滿足Lipschitz連續(xù)，即

(12)

成立，并且L>0是一個常數(shù)?，F(xiàn)在需證明關(guān)于式(11)的搜索方向dk的充分下降性。

引理1搜索方向dk由式(11)定義，則下面的結(jié)論成立：

(13)

其中,0<η≤1是一個常數(shù)。

(14)

得證。

(15)

引理2由式(11)定義的dk有下面的結(jié)論:

(16)

其中,c是一個常數(shù)。

證明

(17)

由上知引理2得證。接下來的定理是關(guān)于算法的全局收斂性。

(18)

證明通過式(8)、(13)，可以有

(19)

通過式(12)，有

(20)

所以可以得到

(21)

通過假設(shè)1，式(7)、(12)、(18)得到

(22)

總結(jié)上述不等式從k=0到∞，可以得到

(23)

(24)

(25)

3 數(shù)值試驗

數(shù)值實驗由兩部分組成, 一是圖像修復(fù)處理實驗, 二是驗證隨機兩人零和博弈模型。實驗具體設(shè)置如下：

實驗參數(shù)：δ=0.2,δ1=0.5,σ=0.85,μ=0.5,γ=0.8。

數(shù)值實驗中所有的代碼都在Matlab R2014b上編寫,運行環(huán)境為8 G 內(nèi)存, 2.30 GHz CPU Windows 10操作系統(tǒng)。

3.1 圖像處理

在圖像處理實驗中, LL算法和PRP算法將對被脈沖噪聲破壞的圖像恢復(fù)原始圖像。圖像修復(fù)工作在優(yōu)化領(lǐng)域具有重要的現(xiàn)實意義, 能體現(xiàn)出共軛梯度法在實際應(yīng)用中起到重要的作用。

實驗選擇Lena (512×512)、Baboon (512×512) 和Man (512×512)作為測試圖像。圖 1、圖 2給出了詳細(xì)的性能結(jié)果?？梢钥闯鯨L 算法、 PRP 算法都對測試圖像的影像復(fù)原有效。表1中列出了CPU時間的消耗,以比較目的在于LL 算法和PRP算法在圖像處理方面的優(yōu)劣。

(a) 測試圖像Lena

(a) 測試圖像Lena

表1 LL算法，PRP算法基于30 %噪聲修復(fù)圖像使用CPU時間

表2 LL算法，PRP算法基于50 %噪聲修復(fù)圖像使用CPU時間

從表1、表2、圖 1和圖 2可以得出結(jié)論: ①當(dāng)測試圖像含有50 %噪聲時,比含有30 %噪聲的圖像恢復(fù)所需的CPU 時間較多; ②當(dāng)噪聲率增加時,恢復(fù)圖像所需要的時間也隨之增加。③LL算法比 PRP 算法所需CPU時間更少，更適用于影像復(fù)原問題。

3.2 隨機兩人零和博弈模型實驗

零和博弈又被稱為游戲理論或零和游戲,是指一項游戲中, 游戲者有輸有贏, 一方所贏正是另一方所輸, 而游戲的總成績永遠(yuǎn)為零。零和博弈之所以廣受關(guān)注, 主要是因為人們發(fā)現(xiàn)社會的方方面面都能發(fā)現(xiàn)與零和博弈類似的局面, 從個人到國家, 從政治到經(jīng)濟,似乎無不驗證了世界正是一個巨大的零和博弈場。零和博弈是博弈過程的最基本模型, 理想的零和博弈對于金融市場有重要意義, 在金融市場實際趨勢運行中, 理想零和博弈的全過程接近于一個半圓。理想零和博弈, 從金融趨勢的演變角度來看, 最終將構(gòu)成核心因子?；煦缃?jīng)濟學(xué)研究者一直希望在證券市場尋找到主宰世界命運的“混沌因子”, 事實上, 所有金融市場的“混沌因子”就是這么一個理想零和博弈的半圓。在這一部分中,筆者研究了一類兩人零和隨機博弈模型, 其中通過連續(xù)時間馬爾可夫過程給出了具有兩個隨機動力系統(tǒng)[z(t),v(t)]的參與人1和參與人2。 在每個時間t, 對所有參與人的收益函數(shù)[18]定義為ψ[t,z(t),v(t),i],i=1, 2。參與人i通過如下一個滿足耦合偏微分方程鞍點的均衡策略, 最大化的期望收益函數(shù)定義為

γi[zψz(i)+vψv(i)]+μi[ψ(j)-ψ(i)]},

(26)

其中,j≠i,i,j=1,2,κ(i) 代表運行成本,ζi,ρi,ηi,γi,δi代表參數(shù),ζi,μi是控制變量, 后綴代表ψ對空間變量(z,v) 和時間變量t的導(dǎo)數(shù)。與許多偏微分方程類似, 耦合偏微分方程 (26)具有終端條件：

ψ(T,z(t),v(t),i)=π(T,z,v),

(27)

以及下列邊界條件:

(28)

狀態(tài)1：

(29)

狀態(tài)2：

(30)

問題(29)、(30)分別具有i=1和i=2 的邊界條件 (28) 和終端條件 (27)。這兩個問題都需要控制變量ζi,μi(i=1,2)。問題(29)和(30)稱為二階偏微分方程, 其中含有一階偏微分項ψt,ψv,ψz,ψtvv,ψzz,ψzv。下面列出有限差分公式[19], 這些公式將在程序中用到：

(31)

(32)

(33)

(34)

(35)

(36)

(37)

其中,λ為指示函數(shù),定義如下:

(38)

(39)

和

(40)

本文的目標(biāo)是通過LL算法獲得式(39)、(40)的最優(yōu)(或近似)解ζ1和ζ2。在本次實驗中, 成本函數(shù)κ=0,μ1∈(0.04,0.14),μ2∈(0.15,0.24),ρ1=ρ2=0.3,δ1=0.1,δ2=0.3,η1=0.25,η2=0.45,γ1=0.03,γ2=0.01,M=100, 終端時間T= 1,τ=0.02?？臻g參數(shù)(z,v)被放置到一個正方形[0,zmax]×[0,vmax]中, 初始對(z0,v0)=(1,1), (zmax,vmax)=(20,20)、 (30,30) 、(100,100)分別進行求解,詳細(xì)結(jié)果如圖 3至圖5。

圖3 20個離散點時的表現(xiàn)(t=0.8)

圖4 30個離散點時的表現(xiàn)(t=0.8)

圖5 100個離散點時的表現(xiàn)(t=0.8)

從圖3至圖5可以看出, 控制變量ζ1∈[-1,1],ζ2∈[-1,1]是成立的, 同模型規(guī)定的變量范圍相符, 因而可以得出建議的算法對時間變量t=0.8而言, 至少能成功求解出離散點個數(shù)為20, 30和100的情形,驗證了算法的有效性。關(guān)于其他時間點t以及更多離散點情況,有待進一步驗證。

4 總結(jié)與展望

對于求解無約束優(yōu)化問題，筆者根據(jù)文獻[21]的啟發(fā)，在求解無約束問題時應(yīng)用了文獻中的方向，驗證該算法在能求解非線性方程組問題時, 能否求解無約束優(yōu)化問題，并在一定條件下，證明了算法的充分下降性和全局收斂性等算法性質(zhì)。同時在數(shù)值實驗結(jié)果中通過對比，確定本文所提算法比PRP算法有效。

筆者相信，隨著社會的高速發(fā)展，無約束最優(yōu)化的問題會被人們更加重視，會有越來越多的學(xué)者投入到無約束問題的研究中，無約束問題的研究將會在21世紀(jì)取得長足的進步。