求解凸可行性問題的循環(huán)平均交替反射法

梅 奎，歐陽薇

（云南師范大學(xué) 數(shù)學(xué)學(xué)院，云南 昆明 650091）

凸可行性問題是給定一族非空閉凸集C1,C2,…,Cr包含在希爾伯特空間H中，尋求可行性問題在數(shù)學(xué)和物理等不同領(lǐng)域中有著大量的實際應(yīng)用。它們都可以用問題（1）

這種形式進行建模，因此問題（1）引起了許多學(xué)者的注意[1-2]。在解決問題（1）的各種算法中，Douglas-Rachford 算法是最常用的算法之一，它最初由Douglas 和Rachford 提出[3]，用于求解熱傳導(dǎo)問題中的線性方程組，后來由Lions和Mercier擴展到求解具有任意閉集和凸集的可行性問題[4]，并有其他學(xué)者進行了相關(guān)研究[5-7]。1984 年P(guān)ierra 提出了乘積空間中的Douglas-Rachford 算法，將原始的Douglas-Rachford 算法應(yīng)用于多集合中[8]。2008年Luke提出了松弛平均交替反射法（RAAR方法），其迭代定義為經(jīng)典Douglas-Rachford算子與投影算子之間的平均值[9]。2014年Borwein和Tam提出了循環(huán)DR算法，它可以應(yīng)用于多集合的凸可行性問題，而無需使用乘積空間中的DR算法，該方法彌補了DR算法不能直接處理多集凸可行問題的不足[10]。受此啟發(fā)，本文將松弛平均交替反射法進行擴展，考慮一種循環(huán)平均交替反射法，并利用它求解可行性問題（1）。

本文組織結(jié)構(gòu)如下：第1節(jié)給出一些基本概念和結(jié)論，第2節(jié)介紹循環(huán)平均交替反射法并證明該算法的收斂性，第3節(jié)利用循環(huán)平均交替反射法進行數(shù)值實驗，第4節(jié)進行總結(jié)。

1 預(yù)備知識

引理8[13]若T:H →H 是非擴張、漸進正則的且FixT≠?，則對任意x0∈H序列{Tnx0}弱收斂到FixT中一點。

2 循環(huán)平均交替反射法

算法1 本節(jié)考慮循環(huán)平均交替反射法，其迭代格式如下：

3 數(shù)值實驗

圖1 二維凸可行性迭代圖Figure 1 Iteration diagram of two-dimensional convex feasibility problem

圖2 三維凸可行性迭代圖Figure 2 Iteration diagram of three-dimensional convex feasibility problem

從圖3中可以看出，隨著約束集的增加，雖然迭代次數(shù)呈上升趨勢，但都能夠在較少的迭代次數(shù)中尋找到凸可行性問題的解。

圖3 約束集個數(shù)和平均迭代次數(shù)關(guān)系圖Figure 3 Relationship between the number of constraint sets and the average number of iterations

4 結(jié)論與展望

為求解多個集合的可行性問題，本文構(gòu)造了一種循環(huán)平均交替反射算法，在約束集是閉凸集的情形下證明了由循環(huán)平均交替反射法產(chǎn)生的迭代序列收斂于可行性問題的解，同時結(jié)合實例給出數(shù)值實驗，實驗結(jié)果表明該算法有著良好的收斂性。