王霄婷, 龍憲軍, 彭再云
(1. 重慶工商大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,重慶 400067;2. 重慶交通大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,重慶 400074)
設(shè) H 是具有內(nèi)積 〈·,·〉和范數(shù) ‖·‖的實(shí) Hilbert 空間, C?H 是一個(gè)非空閉凸子集, F : H→H 是一個(gè)非線性算x?∈C 子.本文考慮的變分不等式問題是:尋找 ,滿足
記問題(1)的解集為 Sol(C,F).
變分不等式作為非線性分析中的重要分支,在交通、運(yùn)輸、博弈論、機(jī)器學(xué)習(xí)和網(wǎng)絡(luò)規(guī)劃等領(lǐng)域都有著廣泛的應(yīng)用[1-10].投影算法是求解變分不等式問題的一種主要方法,最早的投影算法由Goldstein[11]提出,在F是強(qiáng)單調(diào)且 Lipschitz連續(xù)的條件下,Goldstein證明了算法的收斂性.由于F的強(qiáng)單調(diào)性,算法的使用受到了限制.1976年,Korpelevich[12]提出了外梯度算法,在單調(diào)和 Lipschitz連續(xù)的假設(shè)下證明了算法的收斂性.1999年,Solodov和Svaiter[13]在有限維空間中提出了一種新的二次投影算法,在非單調(diào)和連續(xù)的假設(shè)下證明了算法的收斂性.在 Hilbert空間中,Vuong和Shehu[14]提出了Halpern型二次投影算法,在偽單調(diào)和一致連續(xù)的假設(shè)下證明了算法的收斂性.最近,Reich等[15]通過構(gòu)造一類新的嚴(yán)格分離當(dāng)前迭代和變分不等式解集的超平面,對(duì)文獻(xiàn)[14]中的算法進(jìn)行改進(jìn),提出了兩種新的算法,并在偽單調(diào)和一致連續(xù)的假設(shè)下證明了其算法的收斂性.
本文受文獻(xiàn)[13-15]的啟發(fā),提出了一種新的二次投影算法.在沒有單調(diào)性的假設(shè)下,證明了算法強(qiáng)收斂到變分不等式問題的解.
設(shè) H 是實(shí) Hilbert 空間, C?H 是非空閉凸子集.記 xn→x 為 {xn}強(qiáng)收斂于x, xn?x 為 {xn}弱收斂于x.對(duì)任意的u,v∈H,α∈(0,1),有
任給x∈H,則存在C中唯一的最近點(diǎn)PC(x)滿足
‖x-PC(x)‖≤‖x-y‖, ?y∈C,
PC叫做H到C 上的投影,易知 PC為H到C 上的非擴(kuò)張映射.
定義1 設(shè) F : H→H 是一映射.
(ⅰ) 稱F是偽單調(diào)的,如果 〈F(x),y-x〉≥0?〈F(y),y-x〉≥0,?x,y∈H.
(ⅱ) 稱F是 Lipschitz連 續(xù)的,如果 ‖F(xiàn)(x)-F(y)‖≤L‖x-y‖,?x,y∈H ,這里L(fēng)為 Lipschitz常 數(shù)且 L>0.
引理1[2]設(shè)C ?H 是非空閉凸子集,對(duì)任意的 x∈H,有
(ⅰ) 〈 x-y,PC(x)-PC(y)〉≥‖PCx-PCy‖2,?y∈H.
(ⅱ) ‖ PC(x)-y‖2≤‖x-y‖2-‖x-PC(x)‖2,?y∈C.
引理2[2]設(shè)C ?H 是非空閉凸子集.給定 x∈H,z∈C,則 z = PC(x)?〈x-z,z-y〉≥0,?y∈C.
引理3[3]設(shè) C?H 是非空閉凸子集, h(x)是H上的實(shí)值函數(shù),定義集合 K := {x∈C : h(x)≤0}.如果K非空且 h(x)在C 上是 Lipschitz連續(xù)的,則
dist(x,K)≥θ-1max{h(x),0}, ?x∈C,
其中 dist(x,K)表示x到K的距離,θ為 Lipschitz常 數(shù),且 θ>0.
引理4[4]設(shè) {an}是非負(fù)實(shí)數(shù)序列,滿足以下關(guān)系:
an+1≤(1-ηn)an+ηnsn.
若{ηn},{sn}滿足:(ⅰ) { ηn}?(0,1),; (ⅱ) l imsupn→∞sn≤0,則 limn→∞an= 0.
引理5[2]x?∈Vol(C,F),當(dāng)且僅當(dāng) x?= PC(x?-λF(x?)).
本文假設(shè)
(C1)映射 F : H→H 在C 中的有界集上是一致連續(xù)的.
(C2)變分不等式解集 Sol(C,F)非空.
(C3)對(duì)于 x?∈Sol(C,F)都有
(C4)f :C→C 是一個(gè)壓縮映射且壓縮系數(shù)為 ρ∈[0,1).
(C5)序列 {αn}?(0,1),且滿足
本文提出如下算法:
算法1選取 σ∈(0,1), γ∈(0,1), λ∈選取初始點(diǎn)x1∈C.
步驟1計(jì)算
如果r(xn) := xn-zn= 0,則算法停止,xn是變分不等式的解.否則,轉(zhuǎn)到步驟2.
步驟2計(jì)算
其中 τn:=γmn,mn是滿足下式的最小非負(fù)整數(shù)m:
步驟3計(jì)算
其中
令n = n+1,并回到步驟1.
注1 (ⅰ) 顯然由算法1產(chǎn)生的序列{xn},{yn},{zn}都屬于C.
(ⅱ) 假設(shè) (C1)~ (C4)成立,由引理5可知,若 r(xn) = 0,則 xn是變分不等式的解,算法停止.否則根據(jù)映射F在C 上的一致連續(xù)性以及引理1,可得
即〈F(xn),r(xn)〉≥λ-1‖r(xn)‖2λ∈.又因?yàn)閺亩?/p>
(ⅲ) 如果F是偽單調(diào)的,則式(2)成立,反之則不成立,具體例子可參見文獻(xiàn)[16]中的例3.1.由此說明假設(shè) (C3)比偽單調(diào)性更弱.
引理6假設(shè) (C1) ~ ( C4)成立,且函數(shù) hn(x)由式(5)定義.(ⅰ) 如果 r(xn)≠0,則 hn(xn)>0;(ⅱ) 如果x?∈Sol(C,F),則 hn(x?)≤0.
證明由 hn(x)定義知 hn(xn) =若r(xn)≠0,有 hn(xn)>0.另一方面,
結(jié)合式(2)和(4)可得
從而引理6得證.
引理7 假設(shè) (C1) ~ ( C5)成立,則由算法1產(chǎn)生的序列 {xn}有界.
證明設(shè)p∈Sol(C,F),由引理1(ⅱ)可得 ‖PCn(xn)- p‖2≤‖xn- p‖2-‖PCn(xn)-xn‖2.故 ‖PCn(xn)- p‖≤‖xn- p‖.結(jié)合 {xn+1}的定義知
這表明 {xn}有界.
引理8假設(shè) (C1) ~ ( C4)成立, {xn}為算法1產(chǎn)生的序列.如果 limn→∞τn‖xn-zn‖2= 0,則 limn→∞‖xn-zn‖= 0.
證明我們考慮以下兩種情形.
情形1若 liminfn→∞τn>0,則 0≤‖r(xn)‖2=從而
因此limsupn→∞‖r(xn)‖= 0,即 limn→∞‖r(xn)‖= limn→∞‖xn-zn‖= 0.
情形2若 liminfn→∞τn= 0.不妨設(shè) limk→∞τnk= 0, limk→∞‖xnk-znk‖= a>0.令
則
因?yàn)?{xnk}有界,所以 {znk}有界,則 {znk-xnk}有界且 limn→∞τnk= 0.由此可得 limn→∞(unk-xnk) = 0.根據(jù)線搜索規(guī)則(4)和 {unk}的定義可得
上式等價(jià)于
令δnk:= xnk-λF(xnk),則
又因?yàn)?/p>
聯(lián)立式(6)和(7)有
又由F的一致連續(xù)性可得 limk→∞‖F(xiàn)(unk)-F(xnk)‖= 0.所以當(dāng) k→∞時(shí)不等式(8)右邊會(huì)趨近于(σλ-1)a2<0,從而有
對(duì)于 ?= -(σλ-1)a2/2>0,存在 N∈N,當(dāng) n≥N時(shí)有
故‖xnk-δnk‖<‖znk-δnk‖,這與{zn}的定義矛盾.因此 limn→∞‖xn-zn‖= 0.證畢.
定理1 假設(shè)(C1)~ ( C5)成立,則由算法1產(chǎn)生的序列 {xn}強(qiáng)收斂于 p∈Sol(C,F),這里 p := PSol(C,F)°f(p).
證明先證‖PCn(xn)-xn‖2≤‖xn- p‖2-‖xn+1- p‖2+2αn〈f(xn)- p,xn+1- p〉.事實(shí)上
由引理1(ⅱ)得
由此可得
這表明hn(x)是 Lipschitz連 續(xù)的,且 Lipschitz常數(shù)為M.由引理1、3和6可得
結(jié)合{xn+1}的定義知
所以
下面分兩種情形進(jìn)行討論.
情形3若存在正整數(shù) N ,當(dāng) n≥N 時(shí)有 ‖xn+1- p‖2≤‖xn- p‖2,這表明 limn→∞‖xn- p‖2存在.由式(10)可得,所以
由引理8知
又因?yàn)?{xn}有界,所以對(duì) {xn}的任一聚點(diǎn)z都 存在子列 {xnk},有 limk→∞xnk= z .結(jié)合 PC和F的一致連續(xù)性可得
故r(z) = 0.又由引理5得 z∈Sol(C,F).另一方面
通過式(9)可得limn→∞‖PCn(xn)-xn‖= 0.因此
結(jié)合引理2及p := PSol(C,F)°f(p)有
所以有
則依據(jù)式(11)和引理4有xn→p(n→∞).
情形4假設(shè)不存在 n0∈N 使得是單調(diào)遞減序列.令 Γn=‖xn- p‖2且有映射 t : N→N 滿足對(duì)所有的 n≥n0(n0足夠大)都有
即 t(n)是1,2,···,n 中使得 Γk為遞增序列的最大值k .顯然t 是一個(gè)非遞減序列,且滿足 limn→∞t(n) =∞,以及
由Cauchy-Schwarz不等式以及式(9)可得
由式(10)可得
類似于情形3的證明可得
以及
由式(11)可得
因此limsupn→∞‖xt(n)+1- p‖2≤0
結(jié)合式(12)有 ,即
接下來,我們證明當(dāng)n≥n0時(shí)(n0足夠大),有 0≤Γn≤Γt(n)+1.不難發(fā)現(xiàn),當(dāng) n≥n0時(shí)有 t(n)≤n.考慮三種情況:當(dāng) t(n) = n 和 t(n) = n-1時(shí),顯然有 Γn≤Γt(n)+1.現(xiàn)考慮 t(n)<n-1.對(duì)任意的正整數(shù) n≥n0,由 t(n)的定義知,有Γj≥Γj+1,當(dāng) t(n)+1≤j≤n-1時(shí),得到 Γt(n)+1≥Γt(n)+2≥···≥Γn-1≥Γn,因此當(dāng)n足 夠大時(shí), 0≤Γn≤Γt(n)+1恒成立.聯(lián)立式(13)可知 limn→∞Γn= 0,即算法1迭代產(chǎn)生的序列xn強(qiáng)收斂于p.
在本節(jié)中給出了算法1在一個(gè)簡(jiǎn)單例子中的計(jì)算機(jī)檢驗(yàn)結(jié)果,并與文獻(xiàn)[14]中算法3.3及文獻(xiàn)[15]中算法4進(jìn)行比較.本文中所有代碼都是在MATLAB R2020a和Windows10系統(tǒng)下運(yùn)行的.計(jì)算機(jī)基本參數(shù)為Intel(R) Core(TM) i5-8250U CPU @ 1.60 GHz.此外,用“iter”表示算法迭代次數(shù),“CPU time”表示程序運(yùn)算的時(shí)間,單位為s.參數(shù)選取如下:
例1設(shè)映射 F : Rm→Rm滿足 F(x) = Mx+q ,這里 q∈Rm且 M = NNT+S+ D,其中為反對(duì)稱矩陣,D為 對(duì)角矩陣且對(duì)角元素非負(fù).取可行集
容易得到F是一個(gè)單調(diào)且Lipschitz連續(xù)的映射,其中Lipschitz常 數(shù)L=‖M‖.對(duì)于q = 0,相應(yīng)的變分不等式的唯一解是{0}.
在本文的實(shí)驗(yàn)中,矩陣N,S中所有元素都在區(qū)間(-2,2)上隨機(jī)產(chǎn)生,矩陣D中的對(duì)角元素在(0,1)上隨機(jī)產(chǎn)生.此外,設(shè)置所有算法中最大迭代次數(shù)為,停機(jī)條件為,其中εerr為給定的誤差界.在此情況下,我們對(duì)比了不同的維數(shù)、不同的初始點(diǎn)以及不同的誤差界εerr三種算法的數(shù)值效果,具體如表1 ~ 3所示.通過觀察表中的數(shù)據(jù)可以發(fā)現(xiàn),算法1在三個(gè)維度上的數(shù)值效果優(yōu)勢(shì)非常明顯.
表 1 εerr= 10-4時(shí)不同算法關(guān)于維數(shù)的比較Table 1 For εerr= 10-4, comparison of different algorithms about dimensions
表 2 εerr= 10-4時(shí)不同算法關(guān)于初始點(diǎn)的比較Table 2 For εerr= 10-4, comparison of different algorithms about the initial point
表 3 m = 100時(shí)不同算法關(guān)于允許誤差的比較Table 3 For m = 100, comparison of different algorithms about allowable errors
本文利用線搜索方法,提出了一種新的求解非單調(diào)變分不等式的二次投影算法,在映射是一致連續(xù)的條件下證明了算法的收斂性.本文所得結(jié)果改進(jìn)了文獻(xiàn)[14-15]中對(duì)應(yīng)的結(jié)果.數(shù)值實(shí)驗(yàn)展示了本文算法的優(yōu)勢(shì).本文主要對(duì)變分不等式問題的算法進(jìn)行了研究,如何將所得結(jié)果應(yīng)用于圖像處理以及網(wǎng)絡(luò)規(guī)劃等問題中,有待進(jìn)一步研究.
應(yīng)用數(shù)學(xué)和力學(xué)2022年8期