何松年，田瀚琳

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

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

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

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

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

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

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

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

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

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

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

為符號簡明起見，將用到如下記號：

2）I表示恒等算子；

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

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

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

容易驗證，算子T：H→H是firmly非擴張的，當且僅當不等式成立，即

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

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

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

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

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

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

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

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

2 迭代算法

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

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

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

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

Step3通過如下迭代格式計算xn+1，即

其中 λn∈（0，1）；

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

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

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

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

由歸納法知

故序列{xn}有界。

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

又由引理2，得到

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

令

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

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

蘊含著

另一方面

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

即對于任一子列{nj}?{n}，有