解凸可行性問(wèn)題的選擇性投影方法

何松年，田瀚琳

（中國(guó)民航大學(xué)理學(xué)院，天津 300300）

1 引言與預(yù)備知識(shí)

假設(shè)H是實(shí)Hilbert空間，H的內(nèi)積和范數(shù)分別用〈·，·〉和‖·‖表示。C為定義在H上的有限個(gè)凸函數(shù)水平集的交集，即其中 m 是一個(gè)正整數(shù)，ci：H→R（i=1，…，m）是一個(gè)凸函數(shù)。文中總是假設(shè)ci（i=1，…，m）是次可微的且次微分?ci是有界算子（即在有界集上有界），考慮凸可行性問(wèn)題即尋找一個(gè)點(diǎn)

眾所周知，對(duì)于H中每一個(gè)點(diǎn)x，在C中總存在唯一一個(gè)點(diǎn)，記作PCx，滿足稱PCx為x到C上的度量投影，稱PC：x→PCx為H到C的投影算子。

為了求解凸可行問(wèn)題，在每一步迭代中往往需要計(jì)算每個(gè)投影PCi，如果這些Ci比較復(fù)雜，則計(jì)算其非常困難。為克服這一困難，1986年Fukushima[1]介紹了一種方法，即通過(guò)計(jì)算到包含原始水平集的半空間的一列投影去代替計(jì)算到一個(gè)凸函數(shù)的水平集的投影。之后，此想法被分別應(yīng)用去解決有限維或無(wú)限維Hilbert空間中的分裂可行性問(wèn)題[2-3]和Hilbert空間中的變分不等式問(wèn)題[4]。He等[5]應(yīng)用Fukushima的思想提出了一種松弛的Halpern-type算法[6]用來(lái)求解凸可行問(wèn)題。

算法1?u∈H取定，取任意一個(gè)初始值x0∈H，通過(guò)如下迭代格式構(gòu)造序列{xn}

序列{λn}?（0，1）。

對(duì)于算法1，He等證明如下結(jié)果。

定理 1假設(shè) λn→0（n→∞）和，則由算法 1 產(chǎn)生的序列{xn}強(qiáng)收斂到點(diǎn)

He等的算法可以很好地解決定義在有限個(gè)水平集的交集上的凸可行問(wèn)題。但算法1在每一步迭代中都需計(jì)算m次投影，所以算法1的計(jì)算量較大。另外，當(dāng)m較大時(shí)，水平集的構(gòu)造也會(huì)越來(lái)越復(fù)雜。

縱觀全文提出一種比算法1更簡(jiǎn)捷的新算法，稱之為選擇性投影方法，在新算法每一步迭代中只計(jì)算一次投影算子，因而計(jì)算量明顯減小。

為符號(hào)簡(jiǎn)明起見，將用到如下記號(hào)：

2）I表示恒等算子；

為證明主要結(jié)果，需用到如下結(jié)論。

定義1稱算子T：H→H為非擴(kuò)張的，如果

定義2稱算子T：H→H是firmly非擴(kuò)張的，如果

容易驗(yàn)證，算子T：H→H是firmly非擴(kuò)張的，當(dāng)且僅當(dāng)不等式成立，即

眾所周知，度量投影算子PC是典型的非擴(kuò)張算子和firmly非擴(kuò)張算子。

引理1（鈍角原理） 對(duì)于x∈H，z∈C，z=PCx的充要條件是

引理2?x，y∈H，則如下不等式[7]成立

引理3假設(shè){sn}是非負(fù)實(shí)數(shù)列，滿足

其中{γn}?（0，1），{ηn}是非負(fù)實(shí)數(shù)列且{δn}和{αn}是兩實(shí)數(shù)列，滿足：

定義3對(duì) f：H→R，若對(duì)任何{xn}?H，只要，就有

定義4ξ∈H稱為f：H→R在點(diǎn)x的一個(gè)次梯度，如果滿足次微分不等式

如果函數(shù)f：H→R在點(diǎn)x至少存在一個(gè)次梯度，則稱f在點(diǎn)x為次可微的。f在點(diǎn)x的次梯度集用?f（x）來(lái)表示，稱為f在x點(diǎn)的次微分。如果f在H中的每一點(diǎn)均次可微，則稱函數(shù)f次可微。

2 迭代算法

采用選擇性投影方法計(jì)算PCu，其中u為實(shí)Hilbert空間中任意取定的一個(gè)向量，C是H中有限個(gè)水平集的交集，即其中m是一個(gè)正整數(shù)，ci：H→R（i=1，…，m）是一個(gè)凸函數(shù)。

算法2選擇性投影算法的步驟：

Step1給定u∈H，任取一初始點(diǎn)x0∈H，且設(shè)n=0；

Step2計(jì)算并比較c1（xn），c2（xn），…，cm（xn）中的最大值。取 in∈I={1，2，…，m}，使得構(gòu)造一個(gè)半空間

Step3通過(guò)如下迭代格式計(jì)算xn+1，即

其中 λn∈（0，1）；

Step4令 n=n+1，返回 Step2。

對(duì)于算法2，證明了如下強(qiáng)收斂結(jié)果。

定理2假設(shè) λn→0（n→∞）和，則由算法 2產(chǎn)生的序列{xn}強(qiáng)收斂到點(diǎn)

證明1）證明{xn}是有界的。令則

由歸納法知

故序列{xn}有界。

2）注意到投影算子是firmly非擴(kuò)張的，得到

又由引理2，得到

另外，由式（1）和式（2）的第一個(gè)不等式得到

令

則式（2）和式（3）可被分別改寫為如下形式

3）注意條件λn→0蘊(yùn)含αn→0和條件分別成立。為了使用引理3完成定理的證明，需驗(yàn)證對(duì)于任一子列{nj}?{n}

蘊(yùn)含著

另一方面

根據(jù)引理1，可知

即對(duì)于任一子列{nj}?{n}，有