Banach空间中广义方程的限制型牛顿算法*

赵天晶， 欧阳薇

(云南师范大学数学学院,650500,云南省昆明市)

0 引 言

考虑如下 Robinson[12]意义下的广义方程

0∈f(x)+F(x),

(1)

其中f:X→Y是一个连续函数,F:X⟹Y是有闭图的集值映射,X和Y是Banach空间.众所周知,许多优化相关问题,如非线性规划、均衡问题等,均可转化为广义方程(1)并受到许多学者广泛关注[4-6].特别地,当(1)中集值映射为某个凸集的次微分映射时,该广义方程就转化为通常的变分不等式问题.

为了逼近广义方程(1)的解,在度量正则性假设下,多种牛顿型算法及其改进形式被广泛研究[2,3,7-9].当广义方程(1)中f光滑时,Josephy[10]引入牛顿型算法的策略是线性化单值映射f,而集值映射F保持不变.对于任意给定的初始点x0,通过求解下面局部线性化方程构造序列{xk}:

0∈f(xk)+Df(xk)(xk+1-xk)+F(xk+1),k=0,1,…,

(2)

其中Df表示f的Fréchet导算子.在f+F具有度量正则性的假设下,当Df连续时,牛顿型算法(2)具有线性收敛性;当f是Lipschitz连续时,牛顿型算法(2)具有二次收敛性,关于牛顿型算法(2)更详细的收敛性结论,参见文献[5].

当广义方程(1)中f非光滑时,我们考虑如下迭代过程构造序列{xk}:

0∈Ak(xk,xk+1)+F(xk+1),

(3)

其中函数序列Ak:X×X→Y及起始点x0∈X. 当f光滑时,令Ak(x,u)=f(u)+Df(u)(x-u),则迭代过程(3)退化为(2).如果令Ak(x,u)=γk(u-x)+f(u)(k=0,1,…),其中{γk}是正数列,此时迭代过程(3)退化为邻近点算法,其基本形式为

0∈γk(xk+1-xk)+f(xk+1)+F(xk+1),k=0,1,2,….

关于改进型牛顿算法的更多详细信息,参见文献[1,4,5,7,9]. 一般地,在正则性假设下,仅能保证牛顿型算法(3)或(2)至少产生一个收敛序列,并不能得出牛顿型算法(3)或(2)所产生的任意序列均收敛. 为此,Rashid和Yuan[11]在正则性假设下研究了限制型牛顿算法. 受此启发,针对广义方程(1)及其对应的牛顿型算法(3),本文给出一种限制型牛顿算法,并在度量正则性假设下,给出了几种收敛性条件. 作为应用,我们还考虑了一种特殊形式——限制型邻近点算法,并给出了对应收敛性条件.

1 预备知识

在本节,主要介绍本文所需要的相关符号、定义和已知结论,用来作为后续论证的统一记法和必要准备.我们总是假设所考虑的空间为Banach空间,用BX代表空间X的闭单位球及用Br(x)表示以x∈X为中心,r>0为半径的闭球.给定子集C,D⊂X,定义

并且有

定义集值映射F:X⟹Y的图为:gph(F):={(x,y)∈X→Y:y∈F(x)}.如果gph(F)在空间X×Y是闭的,那么称F在此空间有闭图;记F-1:Y⟹X为F的逆映射,即F-1(y):={x∈X:y∈F(x)}(对任意的y∈Y).

定义1.2称映射序列Ak:X×X→Y是f关于非负常数列{μk}及{εk}的点基近似,如果对于任意的x,y,u,v∈X都有

(4)

及

(5)

为证明本文的主要结论,我们还需要如下集值形式的不动点定理.

2 主要结论

考虑广义方程(1),本节主要讨论限制型牛顿算法在点基近似和度量正则性的假设下的收敛性分析. 设η>1,引入如下限制型牛顿算法:

(6)

在开始收敛性分析的主要定理的阐述之前,需要给出以下引理来作为后面论证的支撑工具.给定k∈及u∈X,定义如下辅助函数gk(·,u)=f(·)-Ak(u,·)及Rk,u(·):=Ak(u,·)+F(·),其中函数序列Ak:X×X→Y.

(7)

(8)

(9)

(10)

从而对任意的y∈Bb(0),都有(f+F)-1(y)≠∅.令Φk:X⟹X(k∈)使得

Φk(x)=(f+F)-1(gk(x,u))，∀x∈X.

由(4)式可得

(11)

和

(12)

由ε的任意性可得(7)成立.证毕.

至此,我们已经做好了主要结论的准备工作,那么下面给出广义方程(1)在度量正则性假设下的收敛性结论.

(13)

注2.1上述定理不仅给出了线性收敛性条件,而且给出了限制型牛顿算法(6)产生的序列所在范围的半径与度量正则性的常数之间的确切关系.特别地,当f光滑时,定理2.2依然改进了主要结论.

若取Ak(u,x)=γk(x-u)+f(x)(k=0,1,2，…),其中{γk}是一正数序列,则限制型牛顿算法(6)退化为如下限制型临近点算法

(14)

由定理2.2可得如下推论.

证明令Ak(u,x)=γk(x-u)+f(x)(k=0,1,2，…),容易看出Ak是f的点基近似,即(4)和(5)式对于μk=γk,εk=0 成立. 从而由定理2.2可得结论成立. 证毕.

下面,在度量正则性假设下,我们给出另一种收敛性条件.

(15)

(16)

(17)

(18)

(19)

(20)

(21)

(22)