亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        求解非單調(diào)變分不等式的一種二次投影算法*

        2022-09-20 08:16:06王霄婷龍憲軍彭再云
        關(guān)鍵詞:變分收斂性單調(diào)

        王霄婷, 龍憲軍, 彭再云

        (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)收斂到變分不等式問題的解.

        1 預(yù) 備 知 識(shí)

        設(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),且滿足

        2 算法與收斂性證明

        本文提出如下算法:

        算法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.

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

        在本節(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

        4 結(jié)論與展望

        本文利用線搜索方法,提出了一種新的求解非單調(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)一步研究.

        猜你喜歡
        變分收斂性單調(diào)
        數(shù)列的單調(diào)性
        數(shù)列的單調(diào)性
        Lp-混合陣列的Lr收斂性
        逆擬變分不等式問題的相關(guān)研究
        求解變分不等式的一種雙投影算法
        對(duì)數(shù)函數(shù)單調(diào)性的應(yīng)用知多少
        END隨機(jī)變量序列Sung型加權(quán)和的矩完全收斂性
        關(guān)于一個(gè)約束變分問題的注記
        一個(gè)擾動(dòng)變分不等式的可解性
        行為ND隨機(jī)變量陣列加權(quán)和的完全收斂性
        一区二区三区国产精品| 品色永久免费| 亚洲男人的天堂网站| 日本人妻少妇精品视频专区| 国产高清一区二区三区三州| 在线亚洲高清揄拍自拍一品区| 无码精品a∨在线观看十八禁 | 亚洲欧美另类日本久久影院| 亚洲中文字幕一区av| 亚洲人精品午夜射精日韩| 欧美巨大性爽| 欧美人与动牲交片免费| 人妻蜜桃日产一本久道综合在线| 男女性杂交内射妇女bbwxz| 国产成人精品一区二区视频| 2021最新久久久视精品爱| 成人高清在线播放视频| 国产a国产片国产| 亚洲中久无码永久在线观看软件 | 亚洲欧洲成人精品香蕉网| 欧美aa大片免费观看视频| 国产精品久久久久亚洲| 亚洲国产精品av麻豆网站| 免费无码av一区二区三区| 亚洲国际无码中文字幕| 亚洲视频一区二区三区免费| 人妻少妇哀求别拔出来| 精品人妻少妇一区二区三区不卡| 人妻av一区二区三区av免费| 亚洲综合久久精品少妇av| 亚洲av无一区二区三区久久| 国产精品第一二三区久久蜜芽| 日韩精品成人一区二区三区久久久| 久久精品色福利熟妇丰满人妻91| 55夜色66夜色国产精品视频| 欧美精品一区二区精品久久| 九一精品少妇一区二区三区| 免费a级毛片无码a∨中文字幕下载| 四虎影永久在线观看精品| 色视频日本一区二区三区 | 国产人妻鲁鲁一区二区|