单调变分不等式问题外梯度方法的推广

闻道君, 张 蓉, 何 光

(1. 重庆工商大学 数学与统计学院, 重庆 400067; 2. 经济社会应用统计重庆市重点实验室, 重庆 400067;3. 重庆邮电大学 理学院, 重庆 400065)

0 引 言

变分不等式问题是非线性分析的重要组成部分, 在优化必要条件、 不动点理论、 网络平衡问题、 互补问题和非线性方程组等领域应用广泛[1-6].

设H为一实Hilbert空间, 其内积和范数分别表示为〈·,·〉和‖·‖. 设C为H的一个非空闭凸子集,A:H→H为一非线性算子. 考虑如下变分不等式问题: 求一点x∈C, 使得

〈Ax,y-x〉≥0, ∀y∈C.

(1)

用Ω表示变分不等式问题(1)的解集, 即Ω={x∈C: 〈Ax,y-x〉≥0, ∀y∈C}.

目前, 关于变分不等式问题的研究主要集中在解的存在性和有效的数值解法两方面. 求解变分不等式问题的基本技巧是投影方法, 但其收敛性分析几乎都要求算子A满足L-Lipschitz连续且η-强单调的条件[7-8]. 为去掉η-强单调性的限制, Tseng[9]给出了一种改进的外梯度方法:

(2)

其中:PC表示从H到C的度量投影;λ∈(0,1/L). 事实上, 外梯度法(2)的每步迭代都需要在闭凸集C上计算两次投影, 并且在实际问题中Lipschitz常数L通常是未知的或者难以估计的, 但参数λ∈(0,1/L)的选取又直接影响数值方法的收敛速度, 在一定程度上限制了外梯度方法的推广应用. 因此, 为提高数值方法的有效性和稳定性, 研究者们开始尝试改进外梯度法中的投影并逐步减弱对常数L的依赖. Censor等[10]通过构造一个特殊的半空间取代方法(2)中的第二个投影, 并在Hilbert空间中给出了如下的次梯度-外梯度法:

(3)

其中λ∈(0,1/L). Gibali[11]利用Armijo-似搜索技巧, 进一步研究了求解伪单调变分不等式问题的自适应次梯度-外梯度法, 并在收敛性分析中释放了迭代参数λ对Lipschitz常数L的依赖. Shehu等[12]结合Armijo-似搜索和次梯度-外梯度法(3), 给出了一种改进的求解单调变分不等式问题的黏滞-外梯度方法:

(4)

并在适当的条件下得到了单调变分不等式问题的强收敛解, 但仍未解决外梯度方法(2)～(4)中投影导致的计算复杂度问题. 其中:αn∈(0,1);μ∈(0,1);f:H→H是压缩映象. 基于此, 本文通过引入强正有界算子改进外梯度方法(2)～(4)中的投影, 给出一种求解单调变分不等式问题的广义外梯度方法:

(5)

其中:αn∈(0,1);γ>0;D:H→H为强正算子; 系数μ∈(0,1);λ=max{λn}∈{σ,lσ,l2σ,…},σ>0,l∈(0,1). 本文利用Armijo-似搜索改进黏滞-外梯度方法(4), 通过强正有界算子取代外梯度方法(2)～(4)中的投影以降低逼近方法的复杂度, 并在不依赖Lipschitz常数L的条件下, 建立关于单调变分不等式问题解的强收敛定理, 所得结果改进并推广了文献[8-12]中的相应结论.

1 预备知识

设C为Hilbert空间H的非空闭凸子集, {xn}为H中的任一序列, 用xn→x和xn⇀x分别表示序列{xn}强和弱收敛到x.

定义1[10,12]设A:H→H为非线性算子, 如果〈Ax-Ay,x-y〉≥ 0(∀x,y∈C), 则称A在C上单调; 如果存在常数η>0, 使得〈Ax-Ay,x-y〉≥η‖x-y‖2(∀x,y∈C), 则称A在C上η-强单调.

定义2[10,12]设A:H→H为非线性算子, 如果存在常数L>0, 使得‖Ax-Ay‖≤L‖x-y‖(∀x,y∈H), 则称A为L-Lipschitz连续.

定义4[3,13]设f:H→H为非线性映象, 如果存在常数ρ∈[0,1), 使得

‖f(x)-f(y)‖≤ρ‖x-y‖, ∀x,y∈H,

则称f为ρ-压缩映象.

由文献[2]可知, 对任意x∈H, 在C中存在唯一的最近点, 记为PCx, 即

‖x-PCx‖≤‖x-y‖, ∀y∈C,

则称PC为H到C上的度量投影, 且PC是非扩张的, 且有下列性质：

1)u=PCx⟺〈x-u,u-y〉≥0, ∀x∈H,y∈C;

2) ‖x-y‖2≥‖x-PCx‖2+‖y-PCx‖2, ∀x∈H,y∈C.

引理2[14]设A:C→H为一连续单调算子, 则x*∈Ω的充分必要条件是〈Ay,y-x*〉≥0, ∀y∈C.

引理3[15]设{an}为一非负实序列, 如果存在子序列{anj}⊂{an}满足条件anj

事实上,mk是集合{1,2,…,k}中满足条件an

引理4[16]设{an},{γn}和{δn}是3个非负序列, 且γn∈(0,1). 如果满足条件

an+1≤(1-γn)an+γnδn,n≥0,

2 主要结果

定理1设A:H→H为L-Lipschitz连续算子. 对给定的μ∈(0,1),σ>0,l∈(0,1), 则式(5)定义的Armijo-似搜索

λ‖Axn-Ayn‖≤μ‖xn-yn‖

(6)

适当且满足条件min{σ,μl/L}≤λn≤σ, 其中λ=max{λn}∈{σ,lσ,l2σ,…}.

证明： 因为A为L-Lipschitz连续算子, 则

‖Aw-A(PC(w-λnAw))‖≤L‖w-PC(w-λnAw)‖,

等价于

表明只要满足λ=max{λn}≤μ/L, Armijo-似搜索(6)定义即适当.

由λ∈{σ,lσ,l2σ,…}得λn≤σ. 显然, 如果λn=σ, 则有min{σ,μl/L}≤λn≤σ成立. 如果λn<σ, 由式(6)的定义可知, 存在系数λn/l, 使得

再结合A的L-Lipschitz连续性可得λn>μl/L, 即min{σ,μl/L}≤λn≤σ成立. 证毕.

证明： 取p∈Ω, 由式(5)得

因为yn=PC(xn-λnAxn), 因此由投影的性质得〈yn-(xn-λnAxn),yn-p〉≤0, 整理得

〈yn-xn,yn-p〉≤-λn〈Axn,yn-p〉.

(8)

结合式(6)～(8), 并利用A的单调性可得

又因为μ∈(0,1), 所以式(9)蕴含了‖zn-p‖≤‖xn-p‖. 由式(5)和引理1进一步得

即序列{xn}有界. 因此, 序列{yn},{zn}和{f(xn)}也有界. 另一方面, 对q=PΩ(q-(D-γf)q), 由式(5)和式(9)得

整理得

‖xn+1-q‖2≤‖xn-q‖2, ∀n≥.

(12)

不妨假设存在子列{xnj}⊂{xn}且xnj⇀z. 又因为ynj=PC(xnj-λnjAxnj)且A是单调算子, 则

由定理1可知λn>μl/L, 再结合式(12)并对式(13)取极限得

〈Ax,x-z〉≥0, ∀x∈C.

(14)

由引理2得z∈Ω, 进一步得

(15)

利用式(5)得

(16)

结合式(15),(16)进一步得

由式(5),(9)和引理1得

整理得

(18)

2) 如果存在子列{‖xnk-q‖2}⊂{‖xn-q‖2}满足条件‖xnk-q‖2≤‖xnk+1-q‖2(∀k∈).由引理3知, 存在一个非递减序列{mk}且使得对任意(或充分大)的k∈, 都有

‖xmk-q‖2≤‖xmk+1-q‖2, ‖xk-q‖2≤‖xmk+1-q‖2.

(19)

在式(11)中取n=mk, 则

(20)

类似地, 由式(13)～(17)可得

(21)

利用式(19)并整理式(22)得

xn→q=PΩ(q-(D-γf)q).

定理3设C为Hilbert空间H的非空闭凸子集,A:C→H为单调算子且L-Lipschitz连续. 设f:H→H为ρ-压缩映象. 对任意给定的x0∈H, 定义黏滞迭代序列{xn}如下:

(23)

证明： 取γ=1,D=I, 则式(5)退化为黏滞逼近式(23), 类似定理2的证明可得结论.