帶1-范數約束的分裂可行問題的投影算法

暢含笑,屈 彪

(曲阜師范大學管理學院,山東日照 276826)

帶1-范數約束的分裂可行問題的投影算法

暢含笑,屈 彪

(曲阜師范大學管理學院,山東日照 276826)

本文主要研究帶1-范數約束的分裂可行問題的求解算法.用一種交替投影算法,求得了問題的解,提出松弛交替投影算法,改進了直接往閉凸集上投影這一不足,并證明了該算法的收斂性.

分裂可行問題;1-范數約束;交替投影;松弛

1 引言

由于社會的發展和生產實踐的需求,最優化問題在金融、醫學、藥學以及手工農業等領域受到越來越多的重視,分裂可行問題就是其中之一.1994年,Censor和Elfving依據醫學中有關放射治療的實踐經驗和理論提出了分裂可行問題[1],問題形式如下

其中C,Q分別為RN和RM中的非空閉凸集,A為一個M×N的實矩陣.

隨后,分裂可行問題的拓展形式被學者們相繼提出.本文主要研究的是帶1-范數約束的分裂可行問題的解,問題形式如下

其中‖.‖1代表1-范數,s＞0為一個給定的常數.

目前,大多數關于求解分裂可行問題及其拓展問題的算法,要么牽涉到往閉凸集上的投影,而這一投影在實際操作中難以實現;要么在求解合適的步長過程中需要估算相關矩陣的最大特征值、Lipschitz系數或進行線搜索,而這些操作往往需要大量的計算.關于求解分裂可行問題的1-范數解問題已有學者在研究[14,15].在文獻[14]中,作者將分裂可行問題的1-范數解問題轉化為變分不等式問題進行求解,但在其給出的算法中需要估算矩陣的最大特征值.

在文獻[2]中,對于多集分裂可行問題

其中Ci(i=1,2,···,t)和Qj(j=1,2,···,r)分別為RN和RM中的非空閉凸集.

作者提出了一種序列投影算法

顯然,序列投影算法有可以直接計算的步長,從而避免了在求解步長時進行大量的計算.受到文獻[2]的啟發,將問題(1.2)轉化為如下形式

其中D={x|‖x‖1≤s}.

序列投影算法雖有可以直接計算的步長,但卻牽涉到往閉凸集上的投影.首先,本文在序列投影的基礎上,提出交替投影算法求解了問題(1.4).其次,考慮到在實際操作中往閉凸集上的投影是難以實現的,文章后半部分構造包含C,D,Q的半空間,利用到半空間上的投影來代替到閉凸集上的投影,從而使投影得到了順利實現.

2 預備知識

定義1[3,4]設??RN為非空閉凸集,對任意的x∈RN,定義

并稱其為x到?上的投影.顯然,若x∈?,則x=P?(x).

注1由投影的定義,可以得出問題(1.2)等價于如下帶約束的最小化問題

定義2[3]給定正常凸函數f:RN→(?∞,+∞],對任意一點x∈domf,若向量ξ∈RN滿足

則稱ξ為凸函數f在點x處的次梯度.將滿足式(2.1)的向量ξ的全體構成的集合記為?f(x),并稱之為f在x處的次微分.

注2domf表示f的有效域,即domf={x∈RN|f(x)＜+∞}.若f在x處可微,則滿足(2.1)式的ξ存在且唯一,并且易知該向量即梯度▽f(x).

由次梯度的定義,簡單計算可得f(x)=‖x‖1在x∈RN的次梯度t,其分量為

引理2.1[9]設?為RN中的非空閉凸集,則對于投影算子P?(.),下述結論成立.

(a)〈P?(x)?x,z?P?(x)〉≥0,?x∈RN,z∈?;

(b)‖P?(x)?P?(y)‖ ≤ ‖x?y‖,?x,y∈RN;

(c)‖P?(x)?z‖2≤ ‖x?z‖2?‖P?(x)?x‖2,?x∈RN,z∈?;

(d)‖P?(x)?P?(y)‖2≤ ‖x?y‖2?‖P?(x)?x+y?P?(y)‖2,?x,y∈RN.

引理2.2[3]假設f:RN→R為凸函數,則f在RN上處處次可微且次微分在RN的任意有界子集上一致有界.

引理2.3[4]設a∈RN,b∈R,則u∈RN到半空間{x∈RN|aTx≥b}上的投影為

引理2.4[16]設f:RN→(?∞,+∞]為閉正常凸函數.給定滿足xk→x的點列{xk}?RN,若ξk∈ ?f(xk)且ξk→ ξ,則有ξ∈ ?f(x).

3 算法及收斂性分析

此部分給出問題(1.4)的求解算法.

3.1 交替投影算法

本文采用可以直接計算的步長,避免了在求合適步長時,進行大量的計算.在該算法中,假設到閉凸集上的投影是可以直接計算的,且問題(1.4)的解集非空.

算法3.1

步驟1任取x0∈RN,選取

步驟2令

步驟3計算

引理3.1設x?為問題(1.4)的任意解,{xk}為算法3.1產生的點列,則數列{‖xk?x?‖}收斂.

定理3.1設{xk}為算法3.1產生的點列,則{xk}收斂到問題(1.4)的一個解.

注3算法3.1可以看成[2]中序列投影算法的特例,引理3.1、定理3.1的證明過程可分別參看文獻[2]中引理2.2、定理2.1.

3.2 松弛交替投影算法

由于算法3.1牽涉到往閉凸集上的投影,所以針對這一不足對算法3.1進行改進.這里,尋找包含集合C,D,Q的半空間,利用到半空間上的投影來代替到閉凸集上的投影,從而使投影簡單可行.

在該部分,將集合D={x∈RN|‖x‖1≤s}記為D={x∈RN|f(x)≤0},其中f(x)=‖x‖1?s.

假設C,Q滿足如下條件:

(H1)C={x∈RN|c(x)≤0},其中c:RN→R是凸函數(不需要可微的)且C是非空的.Q={y∈RM|q(y)≤0},其中q:RM→R是凸函數(不需要可微的)且Q是非空的.

(H2)對于任意的x∈RN,至少有一個次梯度?∈?c(x)是可以計算的,其中?c(x)={?∈RN|c(z)≥c(x)+〈?,z?x〉,?z∈RN}.

對于任意的y∈RM,至少有一個次梯度η∈?q(y)是可以計算的,其中?q(y)={η∈RM|q(u)≥q(y)+〈η,u?y〉,?u∈RM}.并且構造包含C,D,Q的半空間Ck,Dk,Qk如下

注4由次梯度的定義,容易得出?k∈N,有C?Ck,D?Dk,Q?Qk.

算法3.2

步驟1任取x0∈RN,選取

步驟2令

步驟3計算

其中Ck,Dk,Qk如上文所述.

注5在實際計算中,

令

則

注6由(3.1)式及Ck的定義,顯然Ck=C(xk).在式(3.1)中,可以取滿足如下條件的由引理2.4知

引理3.2若點列收斂到收斂到則其中中滿足

證由引理2.3得

證畢.

引理3.3設x?為問題(1.4)的任意解,為算法3.2產生的點列,則數列收斂.

證因為x?為問題(1.4)的任意解,所以x?∈C∩D,Ax?∈Q,由引理2.1(a)得

又因為x?∈C?Ck,x?∈D?Dk,所以

注7由(3.4)式的最后一步可以得出,當時,取得最小值,也即xk最接近x?.

定理3.2設為算法3.2產生的點列,若問題(1.4)的解集非空,則收斂到問題(1.4)的一個解.

證設x?為問題(1.4)的任意解,由引理3.2知數列收斂,同時序列有界.更進一步,由(3.5)式得又因為有界,所以即

也就是

由引理2.1(b),(c)可得

從而

由(3.9)式得

由引理3.2,對(3.10)式取極限得

證畢.

4 數值實驗

為了驗證本文所給算法3.2的可行性,給出如下幾個例子.下面的例1–6取s=1.2,s=3兩種情況來驗證.首先給出的例1–4,集合C與Q都是由可微凸函數的水平集來定義的;其次給出的例5–6,集合C與Q為不可微凸函數的水平集來定義的.最后給出的例7選取高維的水平集和隨機的矩陣.在實際計算中選取參數ωk=1.

例1–6的數值結果如下表1.1–6.2.在表1.1–7.1中,x0代表初始點,Iter代表迭代步數,cpu代表計算時間(單位為秒),x?代表近似解(以下這些結果都是運用MATLAB計算得到的).

表1.1:例1(s=1.2)的數值結果

表1.2:例1(s=3)的數值結果

表2.1:例2(s=1.2)的數值結果

表2.2:例2(s=3)的數值結果

表3.1:例3(s=1.2)的數值結果

表3.2:例3(s=3)的數值結果

表4.1:例4(s=1.2)的數值結果

表4.2:例4(s=3)的數值結果

表5.1:例5(s=1.2)的數值結果

表5.2:例5(s=3)的數值結果

表6.1:例6(s=1.2)的數值結果

表6.2:例6(s=3)的數值結果

例7的數值結果如下表,由于選取的水平集為高維的、矩陣是隨機的,所以給出的計算結果中不顯示近似解.

表7.1:例7(s=0.12)的數值結果

從例1–7的數值實驗結果可以看出,所有的計算時間都在0.1秒左右完成,甚至大多數的計算時間都在0.1秒以內.由此可見松弛交替投影算法具有較強的可行性和實用性.

5 本文小結

本文主要對帶1-范數約束的分裂可行問題進行了求解.首先,在算法上取了可以直接計算的步長,避免了在求合適的步長時進行大量的計算.其次,又尋找包含閉凸集的半空間,用往半空間上的投影來代替往閉凸集上的投影,從而提出松弛交替投影算法,使得投影容易計算.并給出幾個實例來驗證松弛交替投影算法的可行性.數值實驗表明本文的算法具有較強的可行性和實用性.

[1]Censor Y,Elfving T.A multiprojection algorithm using Bregman projection in a product space[J].Numer.Alg.,1994,8(2):221–239.

[2]Liu B,Qu B.A successive projection scheme for solving the multiple-sets split feasibility problem[J].Numer.Funct.Anal.Optim.,2014,35(11):1459–1466.

[3]Rockafellar R T.Convex analysis[M].Vol.28,Princeton:Princeton Math.Ser.,1970.

[4]王宜舉,修乃華.非線性最優化理論與方法[M].北京:北京科學出版社,2012.

[5]Qu B,Xiu N.A note on the CQ algorithm for the split feasibility problem[J].Inverse Prob.,2005,21:1655–1665.

[6]Censor Y,Elfving T,Kopf N,et al.The multiple-sets split feasibility problem and its applications for inverse problems[J].Inverse Prob.,2005,21:2071–2084.

[7]Yang Q.The relaxed CQ algorithm solving the split feasibility problem[J].Inverse Prob.,2004,20(4):1261–1266.

[8]Zhang H,Wang Y.A new CQ method for solving split feasibility problem[J].Front.Math.China,2005,5(1):37–46

[9]Facchinei F,Pang J S.Finite-dimensional variational inequalities and complementarity problems[M].Vols.I and II,Berlin:Springer Verlag,2003.

[10]Qu Biao,Liu Bing-hua and Zhengna.On the computation of the step-size for the CQ-like algorithms for the split feasibility problem[J].Appl.Math.Comp.,2015,262:218–223.

[11]Carmi A,Censor Y and Gurfil P,Convex feasibility modeling and projection methods for sparse signal recovery[J].J.Comp.Appl.Math.,2012,236(17):4318–4335.

[12]Amir Beck,Yonina C Eldar.Sparsity constrained nonlinear optimization conditions and algorithms[J].SIAM Optim.,2012,23(3):1480–1509.

[13]Fukushima M.An outer approximation algorithm for solving general convex programs[J].Opera.Res.,1983,31:101–113.

[14]He H,Ling C,Xu H.An implementable splitting algorithm for the 1-norm regularized split feasibility problem[J].J.Sci.Comput.,2016,67:281–289.

[15]He S,Zhu W.A note on approximating curve with 1-norm regularization method for the split feasibilit problem[J].J.Appl.Math.,2012,16:3800–3844.

[16]Massao Fukushima.非線性最優化基礎[M].北京:科學出版社,2011.

[17]蘭曉堅,曲彪.求解分裂可行問題的一種半空間投影算法[J].數學雜志,2011,31(3):547–553.

[18]房明磊,朱志斌,陳鳳華,張聰.互補約束規劃問題的一個廣義梯度投影算法[J].數學雜志,2011,31(4):685–694.

PROJECTION ALGORITHMS FOR THE SOLUTION OF SPLIT FEASIBILITY PROBLEM WITH 1-NORM CONSTRAINTS

CHANG Han-xiao,QU Biao
(School of Management,Qufu Normal University,Rizhao 276826,China)

In this paper,we mainly study the solution algorithm of the split feasibility problem subject to 1-norm constraints.By using the alternating projections algorithm,we solve the problem successfully and propose arelaxed alternating projections algorithm which improves the shortage of projecting directly onto the closed convex set.And we obtain the convergence of this algorithm.

split feasible problem;1-norm constraints;alternating projections;relaxed

90C25;65K05

O221.2

A

0255-7797(2017)06-1234-11

2016-03-11接收日期:2016-06-28

國家自然科學基金(11271226);山東省優秀中青年科學家科研獎勵基金(BS2012SF027).

暢含笑(1990–),女,河南開封,碩士,主要研究方向:非線性規劃.