求解雙層偽單調變分不等式的慣性次梯度超梯度算法

方長杰， 張瑞瑞

（重慶郵電大學 理學院，重慶400065）

1 序言

設C為Hilbert空間H中的非空閉凸集，A、F是H→H的2個連續映射，〈·，·〉和‖·‖分別是H中的內積和范數.本文將考慮如下雙層變分不等式問題（BVIP）：尋找點x*≥VI（C，A），使得

其中，VI（C，A）表示如下變分不等式問題（VIP）的解集，尋找y*≥C使得

眾所周知，VIP問題（2）等價于不動點問題：找到一個點x*≥C，使得

其中λ取任意正實數.求解VIP（2）最簡潔的方法是投影方法，該方法在可行集上只進行一步投影.但是，這種方法的收斂性需要一個較強的假設，即映射算子A為強單調且Lipschiz連續的.為了避免這種強烈的假設，Korpelevich［1］引入求解鞍點問題的超梯度方法，并將其推廣到有限維和無限維Hilbert空間中的VIP問題，其迭代步驟為

雙層變分不等式問題（1）是擬變分不等式問題以及具有均衡約束的均衡問題的特例［5-7］；同時，它們涵蓋了一些具有均衡約束的數學規劃問題［8］、雙層最小化問題［9］、變分不等式問題［3，10］和二層凸規劃模型［11］等.基于這些原因，有必要研究雙層變分不等式問題.最近，Thong等［12］提出了求解雙層偽單調變分不等式問題的超梯度方法.在該方法中，映射A是偽單調的、Lipschitz連續的，但Lipshiz常數需要事先知道.

慣性型方法起源于含摩擦重球系統（HBF）的隱式離散化方法，其主要特點是每個新的迭代點依賴于前2次迭代［13］.隨后，將該慣性技術推廣到求解極大單調算子的包含問題［14］.近年來，慣性類型算法的研究越來越受到人們的關注，如慣性向前-向后分裂算法［15］、慣性道格拉斯分裂算法［16］和變分不等式的慣性型方法［17］等.

受上述研究工作的啟發，本文通過結合慣性項和次梯度超梯度方法，提出求解雙層變分不等式問題的慣性次梯度超梯度算法，并獲得強收斂性結果.和文獻［12］相比，本文通過類Armijo線性搜索準則的應用，映射A假定是偽單調和Lipschiz連續的，但不需要事先知道Lipschiz常數.同時，通過數值實驗將算法3.1和文獻［3，12］中相應的算法進行比較，驗證本文算法的有效性.

2 預備知識

設H是一個實Hilbert空間，而C是H中的一個非空閉凸子集.用xn?x表示序列｛xn｝弱收斂到x，用xn→x表示序列｛xn｝強收斂到x.對于每個x，y≥H，以及α∈R，有

對?x≥H，在C中存在1個唯一的點z=PC x，使得‖x-z‖≤‖x-y‖，?y≥C.PC稱為H到C的投影.

則稱T是β強單調的.

（v）稱算子T是序列弱-弱連續的，如果對任意的序列xn弱收斂到x，則序列Axn弱收斂到Ax.

眾所周知，如果F：H→H是在H上β-強單調和L-lipschitz連續的，且VI（C，A）是Hilbert空間H的非空、閉凸子集，那么BVIP（1）有一個唯一的解［20］.

引理2.4［21，引理2.1］假設C是一個實Hilbert空間H上的非空有界閉凸子集，且A：C→H是偽單調連續映射，則x*是VI（C，A）的一個解當且僅當

引理2.5［12］設α∈（0，1］，ρ＞0且F：H→H是L-Lipschitz連續和β-強單調映射.定義映射Tρ：H→H如下：

3 主要結果

做如下假設：

（A1）可行集C是實Hilbert空間H的非空、閉凸子集；

（A2）映射A：H→H是Lipschitz連續和偽單調的，在C上是序列弱連續的；

（A3）VIP（2）的 解 集 是 非 空 的，即VI（C，A）≠?；

（A4）映射F：H→H是H上β-強單調和L2-Lipschitz連續的，且L2≥β.此外，定義p是BVIP（1）唯一的解；

證明分4個步驟來證明.

第一步 證明xn、wn和zn是有界的.由引理3.3，有

4 數值實驗

提供一些數值實驗來驗證算法的有效性.處理器為Intel（R）Core（TM）i3-4010U CPU@1.70 GHZ的系統環境下，使用版本為8.4.0.150421（R2014b）SP1的MATLAB進行數值實驗.在表1和表2中，“Iter”表示迭代次數，“CPU”表示以s為單位的CPU時間.ε表示當‖xn-x*‖≤ε時，迭代停止.此外，圖形注釋中的“ISEA”“SEA”和“MSEA”分別表示本文的算法3.1、文獻［12］中的算法3.1和文獻［3］中的算法3.1.在圖1中，縱坐標表示｛‖xn-x*‖｝（n=1，2，…）的值，橫坐標表示運行時間t.

N是n×n階矩陣，B是n×n階斜對稱矩陣，且矩陣N和B中的元素是在（-2，2）中隨機選取的.矩陣D是n×n階對角矩陣，且對角線元素取值范圍為［0，2］（矩陣M是正定矩陣）.方便起見，選取向量d為零向量.

接下來給出第二個映射算子A的2種選擇.

例4.1定義

和C：=｛x∈R2：0≤xn≤1，n=1，2｝.A是在C上偽單調和L2-Lipschitz連續的，其中L2=1/2.在我們的算法中，參數取值為μ=0.73，τ=0.22，γ=0.75，ρ=3.63，α=0.042；在文獻［12］的算法3.1中，參數取值為μ=0.94，α=0.53，γ=0.91；在文獻［3］的算法3.1中，參數取值為μ=0.66，τ=0.03，γ=1.54（圖1和表1）.

表1 例1中CPU和迭代次數比較Tab.1 Comparison between CPU and the iteration number in example 1

圖1 例4.1中的‖xn-x*‖和時間的關系Fig.1 The relationship of‖xn-x*‖and time in Example 4.1

例4.2設H=R2且

其中，A是單調的，L2-Lipschitz連續，參數L2=1/2.算法參數取值為μ=0.92，τ=0.39，γ=0.28，ρ=0.44，α=0.8；在文獻［12］的算法3.1，參數取值為μ=0.36，α=0.75，γ=0.49；在文獻［3］的算法3.1中，參數取值為μ=0.76，τ=0.34，γ=0.45，見圖2和表2.

表2 例2中CPU和迭代次數比較Tab.2 Comparison between CPU and the iteration number in example 2

圖2 例4.2中的‖xn-x*‖和時間的關系Fig.2 The relationship of‖xn-x*‖and time in Example 4.2