陳進作, 王元恒

(浙江師范大學 數學科學學院,浙江 金華 321004)

0 引 言

分裂可行問題[1]自提出以來,得到越來越多學者的關注[2-8],并且在信息[2]、醫(yī)療[3]等領域得到了廣泛應用.分裂可行問題的數學模型是

尋找x∈C使得Ax∈Q.

(1)

式(1)中：C,Q分別為Hilbert空間H1與H2的非空閉凸集;A是有界線性算子.Byrne[3]提出CQ算法,

(2)

式(2)中：PC是空間H1在C上的投影算子;PQ是空間H2在Q上的投影算子;I是恒等算子.后續(xù)的算法研究多數是在CQ算法基礎上的完善與改進,其中有較大影響的是Yang[4]提出的建立在半空間上的松弛CQ算法,

(3)

式(3)中：Ck是C與一族半空間的交集;Qk是Q與一族半空間的交集.相對非空閉凸集C與Q,半空間上投影的計算更加簡單.注意到CQ算法(2)與松弛CQ算法(3)中的步長依賴于算子范數‖A‖,Lpez等[5]提出自適應步長,改進了松弛CQ算法,

(4)

注意到算法(2)～算法(4)中的投影都是正交投影,本文提出次梯度投影算法求解分裂可行問題.

1 預備知識

定義次梯度投影,需要以下概念及命題：

定義2[10]水平集C0={x∈H1|c(x)≤0},其中c：H1→(-∞,+∞]為下半連續(xù)凸函數;水平集Q0={y∈H2|q(y)≤0},其中q：H2→(-∞,+∞]為下半連續(xù)凸函數.

定義3[10]給定函數f：H1→(-∞,+∞],當

f(y)≥f(x)+〈u,y-x〉,y∈H1

成立時,稱u為f在點x的次梯度.稱f在點x的所有次梯度構成的集合為f在點x的次微分,記為?f(x).

定義4[10]設H為Hilbert空間,給定水平集C0,給定函數f：H→R,取定s(x)∈?f(x),定義關于函數f的次梯度投影為：

G：H→H;

如果f為Gateaux可微,那么關于f的次梯度投影為：

G：H→H;

引理1[6]給定函數f：H1→(-∞,+∞],則f為下半連續(xù)凸函數當且僅當f為弱下半連續(xù)凸函數.

定義5[8]給定H1中非空閉凸集C,若{xk}?C,則當

‖xk+1-z‖≤‖xk-z‖, ?z∈C

成立時,稱{xk}是Fejer單調的.

引理2[7]若{xk}在C中是Fejer單調的,則{xk}弱收斂于z∈C當且僅當{xk}的每一個弱聚點都在C中.

性質1[7]設H為Hilbert空間,Fix(T)為T的不動點集,給定非線性算子T：H→H,若〈Tx-x*,Tx-x〉≤0,x∈H,x*∈Fix(T),則稱T具有cutter性質.

2 主要結果

接下來引入次梯度投影松弛算法來解決分裂可行問題(1).假設問題(1)是有解的,解集為Γ;假設問題(1)中的C與Q分別定義為水平集C0與Q0,它們由定義2給出;對任意x∈H1,假設至少存在1個φ∈?c(x),對任意y∈H2,假設至少存在1個φ∈?q(y);假設?c(x)與?q(y)在有界集上是有界的[10].

定義半空間

Gfk：H1→H1;

定義關于gk的次梯度投影為：

Ggk：H2→H2;

記Rμkfk=I+μk(Gfk-I),Rλkgk=I+λk(Ggk-I),通過Rμkfk與Rλkgk構造次梯度投影松弛算法,

xk+1=Rμkfk°Rλkgk(xk),k≥1.

(5)

定理1設序列{xk}由算法(5)迭代生成,當μk∈(0,2),λk∈(0,2)時,序列{xk}弱收斂于分裂可行問題(1)的解.

證明第1步,證明Ggk和Gfk具有cutter性質.

下面證明Ggk具有cutter性質.

〈Ggk(xk)-τ,Ggk(xk)-xk〉≤0,

(6)

〈Ggk(xk)-τ,Ggk(xk)-xk〉=〈Ggk(xk)-τ,xk-xk〉=0;

〈Ggk(xk)-τ,Ggk(xk)-xk〉=

綜上所述,式(6)成立.記wk=Rλkgk(xk),同理可得

〈Gfk(wk)-τ,Gfk(wk)-wk〉≤0.

(7)

第2步,證明序列{xk}關于Γ是Fejer單調的.

由式(6)得

‖wk-τ‖2=

‖xk-τ‖2-λk(2-λk)‖Ggk(xk)-xk‖2.

由式(5)與式(7)得

‖xk+1-τ‖2=

‖xk-τ‖2-λk(2-λk)‖Ggk(xk)-xk‖2-μk(2-μk)‖Gfk(wk)-wk‖2≤

‖xk-τ‖2.

(8)

由假設μk∈(0,2),λk∈(0,2)得序列{xk}關于Γ是Fejer單調的,故序列{xk}是有界的.

第3步,證明Ax*∈Q0.

由式(8)得

(9)

‖▽gk(xk)‖=‖▽gk(xk)-▽gk(τ)‖≤‖A‖2‖xk-τ‖,

(10)

(11)

因為函數q是凸的且下半連續(xù),所以由引理1得q是弱下半連續(xù)的.由式(11)得

(12)

這說明Ax*∈Q0.

第4步,證明x*∈C0.

由wk=Rλkgk(xk)及式(9)得

(13)

這說明{wki}弱收斂于x*.下面證明x*∈C0.

再由式(11)～式(13)得c(x*)≤0,即x*∈C0.

最后,由引理2得序列{xk}弱收斂于x*,從而說明x*是分裂可行問題(1)的解.定理1證畢.

3 結 語

在無限維Hilbert空間中,利用次梯度投影技巧,提出求解分裂可行問題的松弛算法,并證明算法生成的序列收斂于分裂可行問題的解.

定理1的證明分為4步.第1步,采用分類討論的數學思想證明了次梯度投影算子的cutter性質; 第2步,根據cutter性質,證明了關于gk與fk的復合次梯度投影松弛算法生成的序列具有Fejer單調性,從而說明序列的有界性;第3步,證明了Ax*∈Q0;最后一步,采用分類討論的思想證明了x*∈C0,從而說明x*是分裂可行問題(1)的解.

CQ算法(2)、松弛CQ算法(3)和改進的松弛CQ算法(4)中的投影都是正交投影,本文使用的是由次梯度投影構造的算法來求解分裂可行問題.本文給出的算法迭代收斂于問題(1)解的方法及證明過程與上述算法有所不同.