陳 園， 何詣然

（四川師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，四川 成都610066）

設(shè)F 是Rn→Rn的一個(gè)連續(xù)映射，C 為Rn 的一非空閉凸子集.本文考慮經(jīng)典的Hartman -Stampacchia變分不等式問題：求x*∈C使得

其中〈·，·〉是歐幾里德內(nèi)積.

變分不等式在經(jīng)濟(jì)、交通等領(lǐng)域中有著廣泛的應(yīng)用.關(guān)于用數(shù)值迭代法求解變分不等式的研究，已有著豐富的成果［1-12］.投影算法是求解單調(diào)型變分不等式的主要算法，削弱變分不等式單調(diào)性假設(shè)條件是研究變分不等式的重要內(nèi)容.文獻(xiàn)［3］中的算法3.2 及文獻(xiàn)［11］中第72 頁(yè)的算法，為敘述簡(jiǎn)便將其分別記為算法1 和2，具有以下的迭代形式：

其中λk是嚴(yán)格大于0 的步長(zhǎng)，G 是一對(duì)稱正定矩陣，Sk是第k次迭代步選取的迭代方向.近年來，關(guān)于（2）式的算法研究可參見文獻(xiàn)［13 -19］.為使算法簡(jiǎn)潔，將對(duì)稱正定矩陣G取為單位矩陣.

算法1 在每一步迭代中，通過Armijo 線性搜索

確定τk，令

其中τk＝αnkτk-1，nk是滿足（3）式成立的最小非負(fù)整數(shù)，α∈（0，1），τ -1∈（0，∞），

ΠC（x）表示x到閉凸集C上的投影，θ∈（0，2），δ∈（0，1）.該算法在F 為單調(diào)連續(xù)映射且（1）式有解的條件下是全局收斂的.

算法2 在每一迭代步中，使用（3）式的Armijo線性搜索，并令

其中

該算法在F 為單調(diào)連續(xù)映射且（1）式的解集非空的條件下是全局收斂的.

注意到算法2 的迭代步，由

易得，xk+1恰為xk在超平面

上的投影.本文令γ∈（0，1］，τk：＝αnk，α∈（0，1），通過（5）式中的超平面，證明了當(dāng)變分不等式（1）的解集非空且F 為偽單調(diào)連續(xù)映射時(shí)，所提算法3.1 是全局收斂的，其中nk是滿足（3）式成立的最小非負(fù)整數(shù).

近20 年來，已有較多的文獻(xiàn)研究了用投影型算法求解偽單調(diào)型變分不等式問題，如文獻(xiàn)［4 -9］.為后文敘述方便，對(duì)任意一個(gè)正實(shí)數(shù)μ，任意x∈Rn，記rμ（x）＝x -ΠC（x -μF（x））.文獻(xiàn)［4 -9］中共使用了2 種與（3）式不同的Armijo 線性搜索.文獻(xiàn)［4，6，8］中使用了Armijo線性搜索

而文獻(xiàn)［5，7，9］中使用的Armijo線性搜索為

其中α∈（0，1），θ與μ均為正數(shù)且取值相關(guān)，nk是滿足不等式（6）或（7）成立的最小非負(fù)整數(shù).易得，在每次迭代中Armijo線性搜索（6）與（7）式較之于（3）式，計(jì)算投影算子的次數(shù)更少，事實(shí)上使用（3）式，每一次nk取值的變動(dòng)將計(jì)算一次投影算子.本文中使用的Armijo 線搜索與（6）和（7）式雖不同，但可以將文獻(xiàn)［4 -9］及本文中的算法獲得下一迭代步xk+1的步驟統(tǒng)一為如下形式：

其中Hk為某超平面或半空間，αk為第k 步的步長(zhǎng)，dk為第k步的迭代方向.則文獻(xiàn)［4，7 -9］中的算法對(duì)任意非負(fù)整數(shù)k，αk＝0，文獻(xiàn)［4，8］的

文獻(xiàn)［7，9］中的算法4 的

文獻(xiàn)［6］中算法對(duì)任意非負(fù)整數(shù)k，Hk為全空間Rn，

且需滿足

文獻(xiàn)［5］中算法NVE-2 的

而本文算法在生成下一迭代步xk+1時(shí)，對(duì)任意非負(fù)整數(shù)k，

文獻(xiàn)［10］的算法1 使用了與（3）、（6）和（7）式形式均不同的Armijo線性搜索

且生成下一迭代步xk+1的等式形如（2）式，該算法的

其中

nk是使（9）式成立的最小非負(fù)整數(shù).易知（9）式的Armijo線性搜索較之于（6）和（7）式，在每次迭代中仍可能計(jì)算更多次的投影算子.本文引理2.1 的證明中指出了它與Armijo 線性搜索（3）式的關(guān)系，該算法在F 為偽單調(diào)連續(xù)映射且（1）式的解集非空的條件下，全局收斂.

為書寫簡(jiǎn)潔，將文獻(xiàn)［7］的算法1. 1 與文獻(xiàn)［10］的算法1，分別記為算法3 和4.雖然本文算法2.1 中的Armijo線性搜索較之于（6）和（7）式，在每次迭代中可能計(jì)算更多次的投影算子，但不失為一種新的投影型算法，且本文關(guān)于例3.1 的數(shù)值計(jì)算結(jié)果可說明，在求解某些變分不等式問題時(shí)，本文算法2.1 比算法1 ～4 收斂得更快.記問題（1）的解集為S，本文始終假定S≠?，F(xiàn)為偽單調(diào)連續(xù)映射.

3 數(shù)值實(shí)驗(yàn)

本節(jié)給出數(shù)值實(shí)驗(yàn)，在Windows 10，處理器為Intel（R）Core（TM）i5 -3317UCPU＠1.70GHz的系統(tǒng)環(huán)境下，使用版本為R2015b，優(yōu)化工具為toolbox 7.3 的MATLAB 進(jìn)行數(shù)值實(shí)驗(yàn).在計(jì)算過程中，允許誤差為ε ＝10-8，即當(dāng)‖r1（xk）‖2≤10-8程序終止.令算法2.1 中參數(shù)取為：τ0＝1，δ ＝0.2，α ＝0.5，γ ＝0.8，并將其與算法1 ～4 比較，其中算法1的參數(shù)取值為τ -1＝1，θ ＝1.5，δ ＝0.1，α ＝0.3；算法2 的參數(shù)取值為γ ＝1.5，α ＝0.5，δ ＝0.2，τ -1＝1；算法3 中參數(shù)的取值為α ＝0.5，θ ＝4，μ ＝0.2；算法4 中G取單位矩陣，α -1＝1，α ＝0.5，γ ＝1.5，θ ＝0.5.令x0代表初始點(diǎn)，nf表示計(jì)算f的次數(shù)，i表示程序迭代的次數(shù)，t代表程序運(yùn)行所需的時(shí)間，x 表示最后一個(gè)迭代點(diǎn).

例3.1 令C ＝［10，20］，F(xiàn)（x）＝x3，則F（x）在C上是單調(diào)映射，易得10 是該變分不等式問題的解，將算法2.1 與算法1 ～4 進(jìn)行比較，得到的數(shù)值結(jié)果如表1 ～4 所示.

表1 例3.1 的數(shù)值結(jié)果Tab. 1 Numerical results of example 3.1

表2 例3.1 的數(shù)值結(jié)果Tab. 2 Numerical results of example 3.1

表3 例3.1 的數(shù)值結(jié)果Tab. 3 Numerical results of example 3.1

表4 例3.1 的數(shù)值結(jié)果Tab. 4 Numerical results of example 3.1

4 結(jié)論

本文算法2.1 可用于求解偽單調(diào)型變分不等式.在例3.1 中，較之于算法1 ～4，算法2.1 有更好的收斂效果.能否進(jìn)一步削弱變分不等式的條件及探索算法2.1 的更多應(yīng)用，是將來進(jìn)一步的工作.