Hadamard流形上極大單調(diào)向量場奇點(diǎn)的Mann迭代算法

唐國吉, 汪 星, 夏福全(. 廣西民族大學(xué) 理學(xué)院, 廣西 南寧 530006; . 江西財(cái)經(jīng)大學(xué) 信息管理學(xué)院, 江西 南昌 33003;3. 四川師范大學(xué) 數(shù)學(xué)與軟件科學(xué)學(xué)院, 四川 成都 60066)

?

Hadamard流形上極大單調(diào)向量場奇點(diǎn)的Mann迭代算法

唐國吉1, 汪 星2, 夏福全3*
(1. 廣西民族大學(xué) 理學(xué)院, 廣西 南寧 530006; 2. 江西財(cái)經(jīng)大學(xué) 信息管理學(xué)院, 江西 南昌 330013;3. 四川師范大學(xué) 數(shù)學(xué)與軟件科學(xué)學(xué)院, 四川 成都 610066)

通過組合鄰近點(diǎn)算法和Mann迭代技術(shù),構(gòu)造了求解Hadamard流形上極大單調(diào)向量場奇點(diǎn)的一個(gè)新方法,其中鄰近點(diǎn)子問題允許非精確的計(jì)算.在適當(dāng)?shù)募僭O(shè)下,證明了新算法產(chǎn)生的序列收斂于極大單調(diào)向量場的一個(gè)奇點(diǎn).主要結(jié)果推廣和改善了近年的一些文獻(xiàn)的相關(guān)結(jié)果.

極大單調(diào)向量場; 鄰近點(diǎn)算法; Mann迭代; Hadamard流形

單調(diào)算子理論是非線性分析的重要組成部分.在單調(diào)算子理論中,一個(gè)基本的問題是尋找極大單調(diào)算子的零點(diǎn),即找x∈H使得

0∈A(x),

(1)

其中A是Hilbert空間H到其自身的一個(gè)極值單調(diào)算子.為了方便,把算子A在H中所有的零點(diǎn)作成的集合記為A-1(0).

求解問題(1)的一個(gè)常用方法是鄰近點(diǎn)算法.對(duì)于任意給定的一個(gè)初始點(diǎn)x0∈H,鄰近點(diǎn)算法按照法則

0∈A(xn+1)+λn(xn+1-xn),

(2)

產(chǎn)生序列{xn},其中λn是一個(gè)正的實(shí)數(shù)列.1976年,R. T. Rockafellar[1]在適當(dāng)?shù)臈l件下證明了按法則(2)產(chǎn)生的序列弱收斂于A-1(0)中的一個(gè)元.此后,鄰近點(diǎn)算法的研究引起了眾多學(xué)者的關(guān)注.他們從不同角度(如不同的空間框架:有限維歐式空間、Hilbert空間、Banach空間、Hadamard流形、Riemann流形等;不同的研究對(duì)象:變分不等式、最優(yōu)化問題、均衡問題等)對(duì)鄰近點(diǎn)算法展開研究,并取得了豐富的成果.

(3)

C. Li等[2]證明了相應(yīng)的收斂性結(jié)果.

正如C. Li等[2]指出的那樣,把適用于歐式空間的一些概念和技巧推廣到Riemann流形是一種自然的想法,但這些工作又是不平凡的.近年來,一些學(xué)者在Riemann流形(或Hadamard流形)上研究變分包含、變分不等式和優(yōu)化問題,如文獻(xiàn)[2-25].

在線性空間的框架下,受尋找一些映像的不動(dòng)點(diǎn)的方法的啟發(fā),一些學(xué)者(如文獻(xiàn)[26-29])設(shè)計(jì)了鄰近Halpern型方法和鄰近Mann型方法來求解問題(1).這類方法都已經(jīng)證明了擁有較好的收斂性質(zhì).

最近,J. H. Wang等[24]在Hadamard流形上構(gòu)造了一個(gè)鄰近Halpern型方法來求解極大單調(diào)向量場的奇點(diǎn).在適當(dāng)?shù)臈l件下,他們證明了算法產(chǎn)生的序列收斂于極大單調(diào)向量場的離初始點(diǎn)最近(按Riemann度量的意義)的奇點(diǎn).另一方面,C. Li等[12]在Hadamard流形上構(gòu)造了2種迭代算法(即Halpern型迭代和Mann型迭代)來求解非擴(kuò)張映像的不動(dòng)點(diǎn).從他們提供的數(shù)值例子可以看出,Mann型迭代比Halpern型迭代具有更快的收斂速度.一個(gè)自然的問題是:是否能通過組合鄰近點(diǎn)算法和Mann型迭代設(shè)計(jì)一種新的方法來求解極大單調(diào)向量場的奇點(diǎn).這是本文的主要?jiǎng)訖C(jī)之一.

到現(xiàn)在為止,Riemann流形上大多數(shù)的鄰近點(diǎn)算法(如文獻(xiàn)[2,5,7,10,18-19,21])都是精確迭代的版本.然而,因?yàn)猷徑c(diǎn)算法本質(zhì)上是隱迭代方法,因此在每個(gè)迭代中精確求解子問題的代價(jià)是昂貴的.正如E. A. P. Quiroz等[19]所指出的那樣,為了計(jì)算的可實(shí)現(xiàn)性,在流形框架下分析非精確迭代算法的收斂性是重要的.這是本文的另一個(gè)主要?jiǎng)訖C(jī).

受以上文獻(xiàn)的啟發(fā),在本文中通過組合鄰近點(diǎn)算法和Mann型迭代,設(shè)計(jì)了一個(gè)求解Hadamard流形上極大單調(diào)向量場的奇點(diǎn)的新方法,其中鄰近點(diǎn)子問題允許非精確的計(jì)算.在適當(dāng)?shù)臈l件下,證明了新方法產(chǎn)生的序列收斂于極大單調(diào)向量場的一個(gè)奇點(diǎn).

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

為了讀者方便,在這一節(jié)中回顧一下Riemann流形的一些基本定義,性質(zhì)和記號(hào),這些內(nèi)容在任何一本Riemann幾何的教材(如[30])中都能找到.

一個(gè)Riemann流形稱為是完備的是指對(duì)于每一點(diǎn)x∈M,從x出發(fā)的所有測地線對(duì)于每一個(gè)-∞

假設(shè)M是完備的,在點(diǎn)x的指數(shù)映射expx:TxM→M是指對(duì)每一個(gè)v∈TxM有expxv=γv(1,x),其中γ(·)=γv(·,x)起于點(diǎn)x速度為v的測地線.那么對(duì)每一個(gè)實(shí)數(shù)t有expxtv=γv(t,x).對(duì)每一個(gè)點(diǎn)x∈M,expx在TxM上是可微的.

一個(gè)完備的,單連通且具有非正截面曲率的Riemann流形稱為Hadamard流形.以下假設(shè)M是一個(gè)m維Hadamard流形.下面的結(jié)果是眾所周知的(如參見文獻(xiàn)[30]的定理4.1).

命題 1.1 設(shè)M是一個(gè)Hadamard流形且p∈M,那么expp:TpM→M是一個(gè)微分同胚,并且對(duì)于任意兩點(diǎn)p,q∈M,存在連接p到q的唯一正規(guī)測地線.

這個(gè)命題說明M微分同胚于歐氏空間Rm.這樣,容易看到M與Rm有同樣的拓?fù)浜臀⒎纸Y(jié)構(gòu).此外,Hadamard流形與歐氏空間有一些類似的幾何性質(zhì).下面的命題取自于文獻(xiàn)[30]的命題4.5,它將在本文的研究中起重要的作用.回顧Riemann流形中的測地三角形△(p1p2p3)是指由三點(diǎn)p1,p2和p3,以及連接這3個(gè)點(diǎn)的最小測地線組成的集合.

α1+α2+α3≤π,

(4)

(5)

由

d(pi,pi+1)d(pi+1,pi+2)cosαi+1

不等式(5)可寫為

d2(pi,pi+1)+d2(pi+1,pi+2)-

(6)

一個(gè)子集K?M稱為是凸的,如果K中任意兩點(diǎn)p和q,連接p到q的測地線都包含于K,即如果γ:[a,b]→M是一條測地線使得p=γ(a)和q=γ(b),那么對(duì)于所有的t∈[0,1]都有γ((1-t)a+tb)∈K.

函數(shù)f:M→R稱為是凸的,如果對(duì)于M上的任意測地線γ,復(fù)合函數(shù)f°γ:R→R是凸的,即對(duì)任意的a,b∈R和0≤t≤1,有

(f°γ)(ta+(1-t)b)≤

t(f°γ)(a)+(1-t)(f°γ)(b).

下面的命題說明距離函數(shù)是凸的.

命題 1.3[30]設(shè)d:M×M→R是距離函數(shù),那么d關(guān)于乘積Riemann度量是凸函數(shù),即對(duì)于任給的測地線γ1:[0,1]→M和γ2:[0,1]→M和所有的t∈[0,1]有如下不等式成立:

d(γ1(t),γ2(t))≤

(1-t)d(γ1(0),γ2(0))+td(γ1(1),γ2(1)).

特別地,對(duì)每一個(gè)p∈M,函數(shù)d(·,p):M→R是一個(gè)凸函數(shù).

引理 1.1[8]設(shè)△(pqr)是M上的一個(gè)測地三角形,那么存在p′,q′,r′∈R2使得

d(p,q)=‖p′-q′‖,d(q,r)=‖q′-r′‖,

d(r,p)=‖r′-p′‖.

引理 1.2[12]設(shè)△(pqr)是M中的測地三角形,△(p′q′r′)是其比較三角形.

1) 設(shè)α,β,γ(分別地,α′,β′,γ′)是△(pqr)(分別地,△(p′q′r′))在頂點(diǎn)p,q,r(分別地,p′,q′,r′)的三個(gè)角,那么

α′≥α,β′≥β,γ′≥γ.

2) 任意給定連接p到q的測地線上的點(diǎn)z,z′是線段[p′,q′]上滿足d(z,p)=‖z′-p′‖和d(z,q)=‖z′-q′‖的點(diǎn)(稱為z的比較點(diǎn)),那么有不等式

d(z,r)≤‖z′-r′‖.

把所有滿足定義域D(A)是閉凸集的集值向量場A:M→2TM(即對(duì)每個(gè)x∈M有A(x)?TxM)記為X(M),其中A的定義域D(A)是

D(A)={x∈M:A(x)≠?}.

定義 1.1 設(shè)A∈X(M)是一個(gè)向量場,那么稱A是:

(i) 單調(diào)的,如果對(duì)于任意的x,y∈D(A),

?u∈A(x), ?v∈A(y);

(ii) 強(qiáng)單調(diào)的,如果存在ρ>0使得對(duì)于任意的x,y∈D(A),

?u∈A(x), ?v∈A(y);

(iii) 極大單調(diào)的,如果它是單調(diào)的且對(duì)于任意的x∈D(A)和u∈TxM有如下蘊(yùn)含關(guān)系成立:

?y∈D(A),

v∈A(y)?u∈A(x).

Hadamard流形上向量場的Kuratowski半連續(xù)性概念由C.Li等[2]引入.

定義 1.2 設(shè)A∈X(M),x0∈D(A).A稱為:

(b) 在M上是Kuratowski上半連續(xù)的,如果對(duì)于每一個(gè)點(diǎn)x0∈D(A),A在點(diǎn)x0是Kuratowski上半連續(xù)的.

由文獻(xiàn)[2]中定理3.7可知:

注 1.1 如果A極大單調(diào)且D(A)=M,那么A是Kuratowski上半連續(xù)的.

2 Mann迭代算法

現(xiàn)在正式給出的算法.令δ∈(0,1).

算法 2.1 初始化:設(shè)x0∈M任意取定.

迭代過程:對(duì)于給定的xn∈M,選取參數(shù)λn>0和元素yn∈M使得

(7)

選取誤差εn≥0和元素zn∈M使得

d(zn,yn)≤εn.

(8)

選取αn∈[0,1-δ]并通過下式定義xn+1,

(9)

或等價(jià)地,

xn+1=γn(1-αn),

(10)

其中γn:[0,1]→M是連接xn到zn的測地線(即γn(0)=xn和γn(1)=zn).

注 2.1 注意到算法2.1中的(7)式是一個(gè)隱迭代.這樣一個(gè)基本的問題是說明這個(gè)步驟是可定義的.事實(shí)上,對(duì)每個(gè)n,定義Bn∈X(M)如下:

?x∈D(A),

那么當(dāng)A∈X(M)是單調(diào)時(shí),每個(gè)Bn是強(qiáng)單調(diào)的.完全類似于文獻(xiàn)[2]中的注4.4,知道如果A是極大單調(diào)向量場且D(A)=M,那么(7)式是可定義的,從而算法2.1是良定的.

注 2.2 (i) 如果M=Rn,那么算法2.1退化為文獻(xiàn)[29]中的算法5.2當(dāng)Hilbert空間是有限維的情形.因此,算法2.1可看成文獻(xiàn)[29]中的算法5.2從線性空間到Hadamard流形的推廣.

(ii) 如果εn=0且αn=0,那么算法2.1退化為Hadamard流形上的精確鄰近點(diǎn)算法(參見文獻(xiàn)[2]中(4.3)式).

(iii) 與文獻(xiàn)[24]中的算法MP作比較,在迭代過程中,鄰近子問題(7)式和相應(yīng)的誤差容忍(8)式是一樣的.不同之處在于(9)式是Mann型迭代過程,而文獻(xiàn)[24]中的對(duì)應(yīng)部分是Hapern型迭代,即

(iv) 與C. Li等[12]提出的Hadamard流形上非擴(kuò)張映像不動(dòng)點(diǎn)的Mann迭代算法相比較,其關(guān)于松弛因子αn的條件與本文算法2.1的不一樣.文獻(xiàn)[12]中{αn}要求滿足

∞.

(11)

容易看到的條件比上述條件要弱.比如取αn=1/n2時(shí),(11)式就不成立了.由于條件(11)在Mann型迭代方法的收斂性證明中發(fā)揮關(guān)鍵作用,因此在Mann型迭代方法中考慮如何減弱松弛因子的限制條件是重要的.因此為了去掉條件(11),在收斂性分析中采用了與文獻(xiàn)[12]中完全不一樣的技巧.

接著,給出算法2.1的收斂性結(jié)果.

定理 2.1 設(shè){xn}是由算法2.1產(chǎn)生的序列.假設(shè)

(12)

那么{xn}收斂于A-1(0)中的一個(gè)點(diǎn).

證明 把證明過程分幾步完成.

第1步:證明序列{xn}是有界的.

(13)

考慮測地三角形△(xnynz).由命題1.2可得

d2(yn,z)+d2(yn,xn)-

結(jié)合(13)式可得

d2(yn,z)+d2(yn,xn)≤d2(xn,z).

(14)

這樣,容易看出

d(yn,z)≤d(xn,z).

(15)

由命題1.3可得

d(xn+1,z)=d(γn(1-αn),z)≤

αnd(γn(0),z)+(1-αn)d(γn(1),z)≤

αnd(xn,z)+(1-αn)d(zn,z).

(16)

d(zn,z)≤d(yn,z)+d(yn,zn)≤

d(xn,z)+εn.

(17)

d(xn+1,z)≤

αnd(xn,z)+(1-αn)d(xn,z)+(1-αn)εn≤

d(xn,z)+εn.

(18)

第2步:證明

(19)

事實(shí)上,由距離的三角不等式和(8)～(9)式可得

d(xn+1,yn)≤d(xn+1,zn)+d(zn,yn)≤

αnd(xn,zn)+εn.

(20)

應(yīng)用引理1.2的2)可得

αnd2(xn,z)+(1-αn)d2(zn,z)-

αn(1-αn)d2(xn,zn).

(21)

由(15)式和(8)式可得

d2(zn,z)≤[d(yn,z)+d(yn,zn)]2≤

[d(xn,z)+εn]2≤

d2(xn,z)+εnC,

(22)

d2(xn+1,z)≤d2(xn,z)+(1-αn)εnA-

αn(1-αn)d2(xn,zn).

結(jié)合條件αn∈[0,1-δ]可得到

δαn2d2(xn,zn)≤αn(1-αn)d2(xn,zn)≤

d2(xn,z)-d2(xn+1,z)+εnA.

第3步:證明{xn}的每一個(gè)聚點(diǎn)屬于A-1(0).

(24)

由(7)式可知,對(duì)每一個(gè)k,有unk-1∈A(ynk-1).由于A是極大單調(diào)的,根據(jù)注1.1可知A是Kuratowski上半連續(xù)的.再結(jié)合(24)式可得0∈A-1(0).

由命題1.2可得

(25)

(26)

注 2.3 定理2.1從以下方面推廣和改善了一些新近的結(jié)果.

(i) 如果M=Rn,那么定理2.1退化為文獻(xiàn)[29]的定理5.2中當(dāng)Hilbert空間是有限維的情形.

(ii) 如果算法2.1中εn=0且αn=0,那么定理2.1退化為Li等人的主要結(jié)果(參見文獻(xiàn)[2]的推論4.8).

[1] Rockafellar R T. Monotone operators and the proximal point algorithm[J]. SIAM J Control Optim,1976,14:877-898.

[2] Li C, López C, Martin-Mrquez V. Monotone vector fields and the proximal point algorithm on Hadamard manifolds[J]. J London Math Soc,2009,79:663-683.

[3] Agarwal R P, Ahmad I, Iqbal A, et al. Generalized invex sets and preinvex functions on Riemannian manifolds[J]. Taiwan J Math,2012,16:1719-1732.

[5] Bento G C, Ferreira O P, Oliveira P R. Local convergence of the proximal point method for a special class of nonconvex functions on Hadamard manifolds[J]. Nonlinear Anal,2010,73:564-572.

[6] Bento G C, Melo J G. Subgradient method for convex feasibility on Riemannian manifolds[J]. J Optim Theory Appl,2012,152:773-785.

[7] Bento G C, Ferreira O P, Oliveira P R. Proximal point method for a special class of nonconvex functions on Hadamard manifolds[J]. Optimization,2015,64:289-319.

[8] Bridson M, Haefliger A. Metric Spaces of Non-Positive Curvature[M]. Berlin:Springer-Verlag,1999.

[9] Ferreira O P, Oliveira P R. Subgradient algorithm on Riemannian manifolds[J]. J Optim Theory Appl,1998,97:93-104.

[10] Ferreira O P, Oliveira P R. Proximal point algorithm on Riemannian manifolds[J]. Optimization,2002,51:257-270.

[11] Ferreira O P, Pérez L R L, Németh S Z. Singularities of monotone vector fields and an extragradient-type algorithm[J]. J Glob Optim,2005,31:133-151.

[12] Li C, López G, Martin-Mrquez V. Iterative algorithms for nonexpansive mappings on Hadamard manifolds[J]. Taiwan J Math,2010,14:541-559.

[13] Németh S Z. Geodesic monotone vector fields[J]. Lobachevskii J Math,1999,5:13-28.

[14] Németh S Z. Monotonicity of the complementary vector field of a nonexpansive map[J]. Acta Math Hungar,1999,84:189-197.

[15] Németh S Z. Monotone vector fields[J]. Publ Math Debrecen,1999,54:437-449.

[16] Németh S Z. Variational inequalities on Hadamard manifolds[J]. Nonlinear Anal,2003,52:1491-1498.

[17] Quiroz E A P, Quispe E M, Oliveira P R. Steepest descent method with a generalized Armijo search for quasiconvex functions on Riemannian manifolds[J]. J Math Anal Appl,2008,341:467-477.

[18] Quiroz E A P, Quispe E M, Oliveira P R. Proximal point methods for quasiconvex and convex functions with Bregman distances on manifolds[J]. J Convex Anal,2009,16:49-69.

[19] Quiroz E A P, Oliveira P R. Proximal point method for minimizing quasiconvex locally Lipschitz functions on Hadamard manifolds[J]. Nonlinear Anal,2012,75:5924-5932.

[20] Tang G J, Huang N J. Korpelevich’s method for variational inequality problems on Hadamard manifolds[J]. J Glob Optim,2012,54:493-509.

[21] Tang G J, Zhou L W, Huang N J. The proximal point algorithm for pseudomonotone variational inequalities on Hadamard manifolds[J]. Optim Lett,2013,7:779-790.

[22] Tang G J, Huang N J. An inexact proximal point algorithm for maximal monotone vector fields on Hadamard manifolds[J]. Oper Res Lett,2013,41:586-591.

[23] Tang G J, Wang X, Liu H W. A projection-type method for variational inequalities on Hadamard manifolds and verification of solution existence[J]. Optimization,2015,64(5):1081-1096.

[24] Wang J H, López G. Modified proximal point algorithms on Hadamard manifolds[J]. Optimization,2011,60:697-708.

[25] Zhou L W, Huang N J. Existence of solutions for vector optimization on Hadamard manifolds[J]. J Optim Theory Appl,2013,157:44-53.

[26] Kamimura S, Takahashi W. Approximating solutions of maximal monotone operators in Hilbert spaces[J]. J Approx Theory,2000,106:226-240.

[27] Kamimura S, Kohsaka F, Takahashi W. Weak and strong convergence theorems for maximal monotone operators in a Banach space[J]. Set-Valued Anal,2004,12:417-429.

[28] Kamimura S, Takahashi W. Weak and strong convergence of solutions to accretive operator inclusions and applications[J]. Set-Valued Anal,2000,8:361-374.

[29] Xu H K. Iterative algorithms for nonlinear operators[J]. J London Math Soc,2002,66:240-256.

[30] Sakai T. Riemannian geometry[C]//Translations of Mathematical Monographs, 149. Providence:American Mathematical Society,1996.

2010 MSC：53C25; 47J25

(編輯 周 俊)

A Mann Type Iterative Scheme for Singularities of Maximal Monotone Vector Fields on Hadamard Manifolds

TANG Guoji1, WANG Xing2, XIA Fuquan3
(1.CollegeofScience,GuangxiUniversityforNationalities,Nanning530006,Guangxi;2.CollegeofInformationAdministration,JiangxiUniversityofFinanceandEconomics,Nanchang330013,Jiangxi;3.InstituteofMathematicsandSoftwareScience,SichuanNormalUniversity,Chengdu610066,Sichuan)

In this paper, by combining the techniques of the proximal point algorithm and Mann-type iteration, a method is proposed for finding the singularities of maximal monotone vector fields on Hadamard manifolds, where the proximal subproblem steps allow inexact computation. Under suitable assumptions, we prove the sequence generated by the proposed method converges to a singularity of maximal monotone vector fields on Hadamard manifolds. The main results presented in this paper generalize and improve some corresponding known results given in literatures.

maximal monotone vector field; proximal point algorithm; Mann iteration; Hadamard manifold

2015-01-16

國家自然科學(xué)基金(11426119)、教育部重點(diǎn)項(xiàng)目(212147)、廣西自然科學(xué)基金(2013GXNSFBA019015)、廣西教育廳科研重點(diǎn)項(xiàng)目(ZD2014045)和廣西高校優(yōu)秀中青年骨干教師培養(yǎng)工程(桂教人2014-39)

O221.2

A

1001-8395(2015)06-0818-06

10.3969/j.issn.1001-8395.2015.06.005

*通信作者簡介：夏福全(1973—),男,教授,主要從事變分不等式與最優(yōu)化理論的研究,E-mail:fuquanxia@sina.com