求解分裂可行問(wèn)題的次梯度投影松弛算法

陳進(jìn)作, 王元恒

(浙江師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院,浙江 金華 321004)

0 引 言

分裂可行問(wèn)題[1]自提出以來(lái),得到越來(lái)越多學(xué)者的關(guān)注[2-8],并且在信息[2]、醫(yī)療[3]等領(lǐng)域得到了廣泛應(yīng)用.分裂可行問(wèn)題的數(shù)學(xué)模型是

尋找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ù)的算法研究多數(shù)是在CQ算法基礎(chǔ)上的完善與改進(jìn),其中有較大影響的是Yang[4]提出的建立在半空間上的松弛CQ算法,

(3)

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

(4)

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

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

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

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

定義3[10]給定函數(shù)f：H1→(-∞,+∞],當(dāng)

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

成立時(shí),稱u為f在點(diǎn)x的次梯度.稱f在點(diǎn)x的所有次梯度構(gòu)成的集合為f在點(diǎn)x的次微分,記為?f(x).

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

G：H→H;

如果f為Gateaux可微,那么關(guān)于f的次梯度投影為：

G：H→H;

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

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

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

成立時(shí),稱{xk}是Fejer單調(diào)的.

引理2[7]若{xk}在C中是Fejer單調(diào)的,則{xk}弱收斂于z∈C當(dāng)且僅當(dāng){xk}的每一個(gè)弱聚點(diǎn)都在C中.

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

2 主要結(jié)果

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

定義半空間

Gfk：H1→H1;

定義關(guān)于gk的次梯度投影為：

Ggk：H2→H2;

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

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

(5)

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

證明第1步,證明Ggk和Gfk具有cutter性質(zhì).

下面證明Ggk具有cutter性質(zhì).

〈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}關(guān)于Γ是Fejer單調(diào)的.

由式(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)

由假設(shè)μk∈(0,2),λk∈(0,2)得序列{xk}關(guān)于Γ是Fejer單調(diào)的,故序列{xk}是有界的.

第3步,證明Ax*∈Q0.

由式(8)得

(9)

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

(10)

(11)

因?yàn)楹瘮?shù)q是凸的且下半連續(xù),所以由引理1得q是弱下半連續(xù)的.由式(11)得

(12)

這說(shuō)明Ax*∈Q0.

第4步,證明x*∈C0.

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

(13)

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

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

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

3 結(jié) 語(yǔ)

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

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

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