Hadamard流形上極大單調向量場奇點的Mann迭代算法

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

?

Hadamard流形上極大單調向量場奇點的Mann迭代算法

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

通過組合鄰近點算法和Mann迭代技術,構造了求解Hadamard流形上極大單調向量場奇點的一個新方法,其中鄰近點子問題允許非精確的計算.在適當的假設下,證明了新算法產生的序列收斂于極大單調向量場的一個奇點.主要結果推廣和改善了近年的一些文獻的相關結果.

極大單調向量場; 鄰近點算法; Mann迭代; Hadamard流形

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

0∈A(x),

(1)

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

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

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

(2)

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

(3)

C. Li等[2]證明了相應的收斂性結果.

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

在線性空間的框架下,受尋找一些映像的不動點的方法的啟發,一些學者(如文獻[26-29])設計了鄰近Halpern型方法和鄰近Mann型方法來求解問題(1).這類方法都已經證明了擁有較好的收斂性質.

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

到現在為止,Riemann流形上大多數的鄰近點算法(如文獻[2,5,7,10,18-19,21])都是精確迭代的版本.然而,因為鄰近點算法本質上是隱迭代方法,因此在每個迭代中精確求解子問題的代價是昂貴的.正如E. A. P. Quiroz等[19]所指出的那樣,為了計算的可實現性,在流形框架下分析非精確迭代算法的收斂性是重要的.這是本文的另一個主要動機.

受以上文獻的啟發,在本文中通過組合鄰近點算法和Mann型迭代,設計了一個求解Hadamard流形上極大單調向量場的奇點的新方法,其中鄰近點子問題允許非精確的計算.在適當的條件下,證明了新方法產生的序列收斂于極大單調向量場的一個奇點.

1 預備知識

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

一個Riemann流形稱為是完備的是指對于每一點x∈M,從x出發的所有測地線對于每一個-∞

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

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

命題 1.1 設M是一個Hadamard流形且p∈M,那么expp:TpM→M是一個微分同胚,并且對于任意兩點p,q∈M,存在連接p到q的唯一正規測地線.

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

α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)

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

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

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

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

下面的命題說明距離函數是凸的.

命題 1.3[30]設d:M×M→R是距離函數,那么d關于乘積Riemann度量是凸函數,即對于任給的測地線γ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)).

特別地,對每一個p∈M,函數d(·,p):M→R是一個凸函數.

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

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

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

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

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

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

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

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

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

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

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

(i) 單調的,如果對于任意的x,y∈D(A),

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

(ii) 強單調的,如果存在ρ>0使得對于任意的x,y∈D(A),

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

(iii) 極大單調的,如果它是單調的且對于任意的x∈D(A)和u∈TxM有如下蘊含關系成立:

?y∈D(A),

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

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

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

(b) 在M上是Kuratowski上半連續的,如果對于每一個點x0∈D(A),A在點x0是Kuratowski上半連續的.

由文獻[2]中定理3.7可知:

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

2 Mann迭代算法

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

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

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

(7)

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

d(zn,yn)≤εn.

(8)

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

(9)

或等價地,

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

(10)

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

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

?x∈D(A),

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

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

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

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

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

∞.

(11)

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

接著,給出算法2.1的收斂性結果.

定理 2.1 設{xn}是由算法2.1產生的序列.假設

(12)

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

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

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

(13)

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

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

結合(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)

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

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

αnd(xn,zn)+εn.

(20)

應用引理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).

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

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

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

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

(24)

由(7)式可知,對每一個k,有unk-1∈A(ynk-1).由于A是極大單調的,根據注1.1可知A是Kuratowski上半連續的.再結合(24)式可得0∈A-1(0).

由命題1.2可得

(25)

(26)

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

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

(ii) 如果算法2.1中εn=0且αn=0,那么定理2.1退化為Li等人的主要結果(參見文獻[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

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

O221.2

A

1001-8395(2015)06-0818-06

10.3969/j.issn.1001-8395.2015.06.005

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