積空間中求解凸不等式系統(tǒng)的不完全投影算法

黨亞崢， 高 巖

（1.河南理工大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院，焦作 454001；2.上海理工大學(xué)管理學(xué)院，上海 200093）

1 問題的提出

設(shè)Ci?Rn，i＝1，2，…，m.Ci為歐氏空間中有限的非空閉凸集，且它們的交集非空，凸可行問題（CFP）就是求一點

如果定義Ci＝｛x∈Rn：fi（x）≤0｝ ，其中，函數(shù)fi（x）是凸的，則凸可行問題（CFP）就變成為求解不等式系統(tǒng)fi（x）≤0（i＝1，2，…，m）的可行解的問題.

作為一類重要的復(fù)雜系統(tǒng)，凸可行問題在系統(tǒng)科學(xué)和工程技術(shù)中的應(yīng)用非常廣泛，如最優(yōu)化［1－2］、逼近論［3－4］、圖像重建的預(yù)測和計算機(jī)斷層掃描［5－6］、控制理論［7－8］等.實際中很難直接找到C＝中的一點，通常采用投影算法，可參見文獻(xiàn)［9－11］.投影算法產(chǎn)生的序列是Fejer單調(diào)的，基于這樣的事實，1998年Ubaldo在文獻(xiàn)［12］中提出了解凸可行問題的平行不完全投影算法.事實上，任何一種投影算法經(jīng)過有限步迭代總能找到不完全投影點，所以，不完全投影算法包含了一般的投影算法.隨后，Echebest在文獻(xiàn)［13］中針對線性的凸可行問題提出了一種加速的不完全投影算法，但是，在這些不完全投影算法迭代步中含有權(quán)參數(shù)ωki，所以，在證明算法的收斂性時會涉及這些參數(shù)的選擇問題，勢必會使證明復(fù)雜化.本文利用文獻(xiàn)［14］的思想建立一個新的積空間，轉(zhuǎn)換平行的不完全投影算法為半序列的不完全投影算法，這樣，一方面將求多集的交點問題轉(zhuǎn)化為2個凸集的交點問題，使問題簡化；另一方面使權(quán)參數(shù)隱含在一個算子中，從而更有利于簡化算法的收斂性證明.

2 預(yù)備知識

現(xiàn)介紹文獻(xiàn)［12］中提到的解凸可行問題的平行不完全投影算法.

算法1

步驟1 假設(shè)xk?C，xk是當(dāng)前迭代點；給定參數(shù)η，0＜η≤1.

步驟2 對每個凸集Ci，i＝1，2，…，m，尋找滿足

步驟4 計算

其中

一般的投影算法產(chǎn)生的迭代序列是Fejer單調(diào)的，即如果序列｛xk｝由投影算法產(chǎn)生，則，所以，在算法1中，不完全投影點可以通過有限步的投影算法得到.

3 算法轉(zhuǎn)換

算法1含有加速因子αk和松弛參數(shù)λk，η≤λk≤2－η，0＜η≤1.因此，它是一種加速的不完全投影算法.但是，本文只考慮下松弛的情況，也就是在算法1中取αk＝1，λk∈（0，1）.現(xiàn)介紹具體過程.

3.1 下松弛的不完全投影算法

算法2

步驟1 假設(shè)xk?C，xk是當(dāng)前迭代點.

步驟2 對每個凸集Ci，i＝1，2，…，m，尋找滿足

步驟4 計算

其中，λk∈（0，1）.

3.2 新的積空間

為了簡化算法2的收斂性證明，將平行不完全投影算法轉(zhuǎn)化為半序列不完全投影算法，首先需要建立新的積空間，其定義為

其中，V＝（v1，v2，…，vm）∈（Rn）m，vi∈Rn，i＝1，2，…，m，W＝（w1，w2，…，wm）∈（Rn）m，wi∈Rn，i＝1，2，…，m.這樣就可以構(gòu)建一個新的積空間和分別表示新空間的內(nèi)積和范數(shù).為了方便起見，空間可以簡記為（Rn）m，為便于區(qū)別Rn中的點，這里用大寫字母表示（Rn）m中的點.

現(xiàn)定義新的積空間（Rn）m中的兩個子集.其一，定義集N∶≡C1×C2×…×Cm，即Rn中的凸集Ci的笛卡兒積，i＝1，2，…，m.顯然，N是空間（Rn）m中的閉集.其二，定義集D，D為Rn在常規(guī)嵌入q∶Rn→（Rn）m下的像，即對?v∈Rn，令q（v）≡（v，v，…，v）.

顯然，如果C≠?，則N∩D≠?， 而且q（C）＝N∩D.這樣，在原始空間中找C中的一點就等價于找N∩D中的一點，并且這些點是一一對應(yīng)的.因此，在子集D?（Rn）m中構(gòu)建一個序列｛Xk｝收斂到N∩D中的一點，就可以在Rn中找到一個相應(yīng)的序列｛xk｝收斂到C中相應(yīng)的一點.

命題1 設(shè)V＝（v1，v2，…，vm）∈（Rn）m，定義算子

也就是自變量xk經(jīng)過算子TCi運(yùn)算后得到滿足不等式（3）的點yki，即TCi（xk）＝y(tǒng)ki，直接定義算子

其中

則對任意Z∈D∩N，有

a.TNV＝（TC1v1，TC2v2，…，TCmvm）；

證明 顯然，TD是線性算子.

a.由新空間的范數(shù)的定義可得

所以

b.由TD的定義可得

其中

3.3 轉(zhuǎn)換平行算法為半序列算法

現(xiàn)給出算法2對應(yīng)的積空間中的半序列投影算法.

算法3

步驟1 取D中任意一點X0＝q（x0）.

步驟2 計算

步驟3 計算

其中，λk∈（0，1）.

顯然，由于Xk＝q（xk），以上下松弛不完全投影算法產(chǎn)生的序列｛Xk｝?D，對應(yīng)Rn中的序列｛xk｝.

命題2 假設(shè)Z∈D∩N，則

證明

由命題1得

因此

顯然，可以直接得出結(jié)果.

推論1 令Z∈D∩N，則

證明 由命題2很容易得到

4 收斂性證明

首先證明積空間中算法3的收斂性，然后基于算法2與算法3的等價性給出算法2的收斂性定理和相應(yīng)的簡單化證明.

定理1 令Z∈D∩N，則

證明 由式（4）得

由推論1可知

故定理1得證.

假設(shè)

顯然

再由式（5）可得

另外，由式（5）得

定理2 如果D∩N≠?，任取D中的點X0為起始點，則由算法3產(chǎn)生的序列收斂于點D∩N中的一點，記為Z.

經(jīng)過內(nèi)積運(yùn)算，得

同理.對任意p′∈Z＋，有

對p→∞和p′→∞，式（8）和式（9）分別取極限，可得

故A′＝A.所以，定理2得證.

將平行不完全投影算法轉(zhuǎn)換為半序列不完全投影算法的主要優(yōu)點是能夠通過序列的收斂性質(zhì)得到相應(yīng)的序列的收斂性質(zhì).基于此，給出定理3.

定理3 當(dāng)（Rn）m中的序列收斂于一點A∈D∩N時，則在空間Rn中其相應(yīng)的序列也收斂到一點a∈C，并且a＝q（a）.

對任意b∈Rn，取一個指標(biāo)j∈｛1，2，…，m｝，有

由式（7）可以得到不等式（11）右邊的第一項趨向于0，由于序列收斂到一點a，顯然，第二項也趨于0.所以，又由于Cj.所以

5 結(jié) 論

原空間的平行不完全投影算法轉(zhuǎn)換為一個新空間中的半序列不完全投影算法，這樣，平行不完全投影算法的收斂性就可以由半序列不完全投影算法的收斂性得到，在某種程度上簡化了平行不完全投影算法的收斂性證明.

但是，本文只是下松弛的平行不完全投影算法，是否能拓展到上松弛和加速的情況仍然是有待解決的問題.

［1］ Chinneck J W.The constraint consensus method for finding approximately feasible points in nonlinear programs［J］.Informs J Comput，2004，16（3）：255－265.

［2］ Censor Y，Lent A.Cyclic subgradient projections［J］.Math Program，1982，24（1）：233－235.

［3］ Deutsch F.Best approximation in inner product space［M］.New York：Springer－Verlag，2001.

［4］ Deutsch F.The Method of alternating orthogonal projections，approximation theory，spline functions and applications［M］.Dordrecht：Kluwer Academic Publishers，1992，105－121.

［5］ Censor Y.Parallel application of block iterative methods in medical imaging and radiation therapy［J］.Math Program，1998，12（2）：307－325.

［6］ Gould N I M.How good are projection methods for convex feasibility problems［J］.Comput Optim Appl，2008，40（1）：1－12.

［7］ Boyd S，EI Ghaoui L，F(xiàn)eron E，et al.Linear matrix inequalities in system and control theory［M］.Philadlphia：Society for Industrial and Applied Mathematics，1994.

［8］ 高巖.仿射非線性控制系統(tǒng)生存性的判別［J］.控制理論與應(yīng)用，2009，29（6）：654－656.

［9］ Baushke H H，Borwein J M.On projection algorithms for solving convex feasibility problems［J］.SIAM Rev，1996，8（3）：367－426.

［10］ Eremin I I.On systems of inequalities with convex functions in the left－h(huán)and sides［J］.Amer Math Soc Trans，1970，88（2）：67－83.

［11］ Herman G T.Image reconstruction from projections：the fundamentals of computerized tomography［M］.New York：Academic Press，1980.

［12］ Garcia U M，Gonzalez F J.Icomplete projection algorithms for solving the convex feasibility problem［J］.Numer Algorithms，1998，18（2）：177－193.

［13］ Echebest N，Guradarcci M T.An acceleration scheme for solving convex feasibility problems using incomplete projection algorithm［J］.Numerical Algorithms，2004，35（2／3／4）：331－350.

［14］ Crombez G.Viewing parallel projection methods as sequential ones in convex feasibility problems［J］.Trans Amer Math Soc，1995，347（7）：2575－2583.