投影算子的一種簡單算法

何松年，趙子祎

（中國民航大學理學院，天津 300300）

投影算子的一種簡單算法

何松年，趙子祎

（中國民航大學理學院，天津 300300）

提出了投影算子的一種Halpern型的松弛算法，由于這種算法把計算關于一個凸函數(shù)水平集的投影轉化為計算關于一列包含水平集的半空間的投影，因而算法容易實現(xiàn)，并且證明了算法的強收斂性。

投影；半空間；強收斂；Hilbert空間

設H是一實Hilbert空間，其內積與范數(shù)分別表示為<·，·>和‖·‖，C?H非空閉凸。從H到其非空閉凸子集C上的投影PC定義為：對于任意x∈H，必有C中唯一一點，記作PCx，滿足

且PC有如下特征：對x∈H，有

投影算子在很多算法中都會涉及到：如不動點的求解，凸優(yōu)化問題的求解，變分不等式[1]以及分裂可行性問題[2-5]的求解等。由于對一般閉凸子集C，投影算子PC沒有顯式表達式（除非C是閉球或者半空間等簡單情形），所以投影算子的計算一般難以實現(xiàn)。

假設T：C→C為非擴張映像，其不動點集Fix（T）非空，眾所周知Fix（T）閉凸的。計算T的不動點的Halpern迭代格式為

其中：u∈C取定，x0∈C任意取定，{λn}?（0，1）。關于Halpern迭代的收斂性，有如下基本結果：

定理1 設H是一實Hilbert空間，其內積與范數(shù)分別表示為<·，·>和||·||，C?H非空閉凸，T：C→C非擴張并且滿足F（T）≠?，又設

則序列（xn）強收斂到PFix(T)u。

假設c：H→R為凸函數(shù)，本文討論關于凸函數(shù)c的水平集投影的計算方法，其中水平集為

本文提出投影算子的一種Halpern型松弛算法，具體如下

其中：取u∈H，任意取定初值x0∈H，Cn?C（n=1，2，…）是一列半空間（Cn的確切構造見第2節(jié)），由于這種算法是把計算關于一個凸函數(shù)水平集的投影轉化為計算關于一列包含水平集的半空間的投影，所以此算法容易實現(xiàn)。將在第2節(jié)證明此算法產(chǎn)生的序列在一定條件下強收斂于PCu。

1 預備知識

若成立：對任意的x，y∈H

則稱T是firmly非擴張的。投影PC是一個典型firmly非擴張映像例子。

稱元素g∈H為f：H→R在點x處的次梯度，如果有

函數(shù)f：H→R如果在點x處至少有一個次梯度，則稱函數(shù)f在點x處次可微，f在點x處的次梯度集稱為f在點x處的次微分，記為?f（x）。式（3）稱為f在點x處的次微分不等式。如果對于?x∈H，f在點x處都次可微，則稱f是次可微的。

引理1 對于所有的x，y∈H，滿足

引理2 假設{sn}為非負實數(shù)列，且滿足[6]

{γn}是（0，1）上的數(shù)列，{ηn}為一非負實數(shù)列，且{δn}和{αn}都是R上的數(shù)列，滿足如下條件

3）對任意的子列{nk}?{n}，只要就有

引理3 T：H→H的一個算子，以下命題等價[7]

1）T是firmly非擴張的；

2）‖Tx-Ty‖2≤；

3）I-T是firmly非擴張的。

2 迭代算法及其收斂性

本節(jié)給出本文算法并證明其收斂性。假設c：H→ R為一凸函數(shù)，總是假設c在H上是次可微的，并且?c是有界算子（也就是在有界集上是有界的）。值得注意的是定義在有限維Hilbert空間中的每一個凸函數(shù)都是次可微的，并且其次可微算子是有界的[8]。假設算法第n步迭代xn已經(jīng)得到，基于次微分不等式，構造如下半空間

其中：ξn∈?c（xn）。由次微分不等式容易驗證Cn?C= {x∈H|c（x）≤0}。

算法1 取u∈H，任意初值x0∈H取定，（xn）以如下迭代格式產(chǎn)生

其中：Cn由式（7）給出，并且{λn}?（0，1）。

下面運用引理2來分析算法1的強收斂性。

定理2 假設λn→0（n→∞）并且由算法1產(chǎn)生的迭代序列（xn）強收斂于PCu。

證明先證明序列（xn）有界。

令PCu=z，由式（8）及引理1得

所以得證（xn）是有界的。

從式（9）的第一個不等式有

則式（10）可以寫為

另一方面由于PC為firmly非擴張以及引理1，所以有

這里M是某一實數(shù)，使得2‖u-z‖·‖xn+1-z‖≤M（注意到（xn）是有界的）。

令

那么式（12）可以寫為

[1]YANG Q.On variable-set relaxed projection algorithm for variational inequalities[J].J Math Anal APPL，2005（302）：166-79.

[2]YANG Q.The relaxed CQ algorithm for solving the split feasibility problem[J].Inverse Problems，2004，20（4）：1261-1266.

[3]XU H K.Iterative methods for the split feasibility problem in infinitedimensional Hilbert spaces[J].InverseProblems，2010，26（10）：105018-105034.

[4]ZHAO J，YANG Q.Self-adaptive projection methods for the multiplesets split feasibility problem[J].Inverse Problems，2011，27（3）：35009-35021.

[5]LóPEZ G，MARTíN-MáRQUEZ V，WANG F H，et al.Solving the split feasibility problem without prior knowledge of matrix norms[J].Inverse Problems，2012，28（8）：85004-85021.

[6]H S，Y C.Solving the variational inequality problem defined on intersection of finite level sets[J].Abstract and Applied Analysis，2013，doi.org/10.1155/2013/942315.

[7]GOEBEL K，KIRK W A.Topics on Metric Fixed Point Theory[M]. Cambridge：Cambridge University Press，1990.

[8]BAUSCHKE H H，BORWEIN J M.On projection algorithms for solving convex feasibility problem[J].SIAM Rev，1996（38）：367-426.

（責任編輯：楊媛媛）

Simple algorithm for projection operator

HE Song-nian，ZHAO Zi-yi
（College of Science，CAUC，Tianjin 300300，China）

A relaxed Halpern's projection algorithm is proposed.Since this algorithm computes the projection onto level set of a convex function by computing the projection onto a series of half-spaces containing a level set，it is easy to be implemented.Strong convergence of this algorithm is proved.

projection；half-space；strong convergence；Hilbert space

O177

：A

：1674-5590（2014）04-0052-03

2013-07-12；

：2013-09-02

：中央高?；究蒲袠I(yè)務費專項（3122013SY30）

何松年（1963—），男，山西太原人，教授，博士，研究方向為非線性分析理論、算法及其應用.