何松年，趙子祎

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

投影算子的一種簡(jiǎn)單算法

何松年，趙子祎

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

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

投影；半空間；強(qiáng)收斂；Hilbert空間

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

且PC有如下特征：對(duì)x∈H，有

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

假設(shè)T：C→C為非擴(kuò)張映像，其不動(dòng)點(diǎn)集Fix（T）非空，眾所周知Fix（T）閉凸的。計(jì)算T的不動(dòng)點(diǎn)的Halpern迭代格式為

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

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

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

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

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

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

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

若成立：對(duì)任意的x，y∈H

則稱T是firmly非擴(kuò)張的。投影PC是一個(gè)典型firmly非擴(kuò)張映像例子。

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

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

引理1 對(duì)于所有的x，y∈H，滿足

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

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

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

引理3 T：H→H的一個(gè)算子，以下命題等價(jià)[7]

1）T是firmly非擴(kuò)張的；

2）‖Tx-Ty‖2≤；

3）I-T是firmly非擴(kuò)張的。

2 迭代算法及其收斂性

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

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

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

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

下面運(yùn)用引理2來(lái)分析算法1的強(qiáng)收斂性。

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

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

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

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

從式（9）的第一個(gè)不等式有

則式（10）可以寫(xiě)為

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

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

令

那么式（12）可以寫(xiě)為

[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.

（責(zé)任編輯：楊媛媛）

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

：中央高校基本科研業(yè)務(wù)費(fèi)專(zhuān)項(xiàng)（3122013SY30）

何松年（1963—），男，山西太原人，教授，博士，研究方向?yàn)榉蔷€性分析理論、算法及其應(yīng)用.