不动点与零点迭代逼近及应用

2023-10-20 理论教育版权反馈

【摘要】：变分不等式是非线性互补问题的推广,它的提出统一了优化问题和均衡问题的研究,并且在数学领域内作为大量数学问题实际求解的统一框架.变分不等式广泛应用于工程优化,经济学和交通运输的平衡问题,对数学各个领域、计算机科学等方面都产生了巨大的影响.经典变分问题的推广和发展,将经典变分问题的约束条件放松为某些单边约束(即用不等式代替等式)的变分方法.它是研究偏微分方程、最佳控制和其他领域的一个十分有用的工具,也

变分不等式是非线性互补问题的推广,它的提出统一了优化问题和均衡问题的研究,并且在数学领域内作为大量数学问题实际求解的统一框架.变分不等式广泛应用于工程优化,经济学和交通运输的平衡问题,对数学各个领域、计算机科学等方面都产生了巨大的影响.经典变分问题的推广和发展,将经典变分问题的约束条件放松为某些单边约束(即用不等式代替等式)的变分方法.它是研究偏微分方程、最佳控制和其他领域的一个十分有用的工具,也是变分学的一个重要发展.由于变分不等式和人们的实际生活联系紧密,因此,如何求解变分不等式问题一直是数学工作者和经济学家研究的热点.

变分不等式间题是数学规划中的一类重要间题,它最初来源于偏微分方程理论,首先由Stmapachia 于20 世纪60年代提出．后来,Stmapacchia 又扩展了变分不等式的一些重要结论．Stampacchia 首次证明了变分不等式解的存在性和唯一性．随后涌现出大量关于无限维变分不等式及其相关文献的,特别是Baiocchi 和Capelo 以及Stampacchia 在书中详细介绍了无限维空间中变分不等式的应用．近二十年,变分不等式被广泛用于研究经济学、工程和控制论、交通运输等领域中．许多问题的研究本质上都可以视为变分不等式问题．变分不等式解法的研究发展迅速,已有算法主要是牛顿型方法及其推广,一般只有局部收敛性,只是对一些特殊的问题例如单调映射的变分不等式问题给出了大范围收敛的结果和大范围收敛的算法．

1967年,Scarf 首次提出了用迭代法近似求解连续映射的不动点．由于不动点法的全局收敛性,许多著名的研究员,包括Eves,Garcia,Gould,Kojima和Zang 等都致力于该方法的研究,由此掀起了一股不动点求解均衡问题的热潮．20 世纪70年代,经济学中均衡问题被证明和变分不等式的求解偶密切的联系,其中对于许多基础的均衡问题的研究都可以转化为变分不等式问题,比如新古典纯粹交易模型、纳什均衡问题以及网络均衡问题等．20 世纪70年代后期,美国能源部提出了关于能源政策研究的项目独立评估系统,这标志着现代有限维变分不等式的开端．该系统是用特殊的迭代求解的一个大规模变分不等式．Ahn 证明了该算法就是求解非线性等式系统的经典雅各比迭代法的一般形式．随后,基于Robinson 的研究,Josephy 通过大量的数值数据确立了牛顿法求解变分不等式的有效性,同时给出该方法快速收敛的理论基础．而Rutherfod 指出,把牛顿法运用于某些具有挑战性的经济均衡问题时缺乏有效性．90年代,Fischer 提出的NCP 函数,被广泛应用于KKT 条件的改写,从而得到了弱B-可微且具有全局收敛和局部收敛的半光滑化法．经过几十年的研究,有限维变分不等式的理论和算法已经得到了极大的发展．但是由于和实际生活的密切联系,变分不等式仍然是数学工作者和经济学家研究的热点．

下面给出变分不等式的一般形式:设F∶Rn→Rn 是连续可微的向量值函数,X 是Rn 上的非空闭子集.变分不等式问题,是指求向量x∗∈X,使得对任意的x ∈X 有

F(x∗)T(x-x∗)≥0.

变分不等式根据约束集X 的不同,可以转化为不同的数学问题.

(ⅰ)若约束集X 表达为

X={x ∈Rn,li≤xi(i ∈Il),xi≤ui(i ∈Iu)},

其中Il,Iu是I={1,2,…,n}的子集,此时称变分不等式为箱约束变分不等式.特别地,混合互补问题:求x=(x1,x2)∈Rn1 × Rn2,使得

其中F1∶Rn1→Rn2 和F2∶Rn→Rn2,令

容易看出,混合互补问题是具有箱约束的变分不等式问题.

(ⅱ)若X= pagenumber_ebook=158,pagenumber_book=151 ,则变分不等式问题蜕化为非线性互补问题,等价为:向量x∗∈Rn,使得

x∗≥0,F(x∗)≥0,F(x∗)Tx∗=0.

若F是放射,即F(x)=Mx＋q,这里M为n 阶矩阵,q 为n 维向量,则非线性互补问题蜕化为线性互补问题.

(ⅲ)若X=Rn,则变分不等式问题蜕化为求解系统F(x)=0;若F=▽f 是连续函数f∶Rn→R的梯度,且X是非空闭凸集,则变分不等式等价于约束优化问题的求解.

(ⅳ)若集合X={x ∈Rn,h(x)=0,g(x)≥0},其中h∶Rn→Rp,g∶Rn→Rm 为二次连续可微函数.在一定约束条件下,变分不等式的解x∗和相应的Lagrange 乘子y∗∈Rp,z∗∈Rm 满足下列KKT 系统:

F(x)＋▽h(x)Ty-▽g(x)Tz=0;h(x)=0;g(x)≥0,z ≥0,zTg(x)=0(www.chuimin.cn)

在一定条件下,满足KKT 系统的解是变分不等式的解,因此称KKT 系统为变分不等式最优性条件;而满足KKT 系统的三元组(x∗,y∗,z∗)∈Rn＋p＋m 称为KKT 三元组,对应的x∗称为变分不等式的KKT 点.

目前,变分不等式系统在数学规划、对策论、交通运输等领域都具有广泛的应用,因而受到许多数学工作者、经济学家和工程技术人员的重视.研究人员致力于求解变分不等式,提出了许多有效的算法,并且完善与丰富了算法的收敛性理论.目前广泛使用的三大类方法分别是:投影类算法、非光滑方程组法和光滑化法.

投影算法是求解变分不等式的一类简单算法,最早由Sibony,Bakusinskji 和Polyak 在19 世纪提出.它通常分为基本投影法、外梯度法以及平面投影法.这些方法主要依赖于xk＋1=PΩk(xk-akdk)的投影迭代,其中Ωk是包含X 的闭凸集,dk为收索方向,ak>0 为步长,PΩk为投影算子,即

PΩ(x)=arg min{‖x-y‖,y ∈Ω}.

投影算法有两方面的特征:第一,该算法的实现要求有效地计算闭凸集上的投影.当约束集X 相对简单使投影易于计算,则算法简单易实现.第二算法不涉及函数F 的导数信息和其他复杂运算,因而也适用于大规模问题.

基本投影法基于Banach 不动点定理,迭代格式为

xk＋1=∏X,D(xk-D-1F(x∗)).

其中D 为n 阶对称正定矩阵.该方法是其他投影算法的基础,仅当F 强单调时,算法才具有全局收敛性;且D 未知,需要额外的参数给定D.因此该方法在应用中并不广泛.

外梯度法由korpelerich 在1976年提出,方法名称源于对称变分不等式,每一次迭代需要额外的估计F 的函数值与额外的投影,即二次投影:

yk=PΩ(xk-akF(xk)),xk＋1=PΩ(xk-akF(yk)).

该算法在映射F 是Lipschitz 连续时具有全局收敛性.若映射F 是非Lipschitz 连续或者Lipschitz 常数未知,iusem 和svaiter 通过引进一种不带投影的线性搜素技术,提出了改进的求解变分不等式的外梯度法,以保证F伪单调时,算法具有全局收敛性.

平面投影法由Konnev,Iusem 和Svaiter 提出,它克服了外梯度法依赖于函数F 和Lipschitz 常数来保证收敛的缺点.其思想是在当前迭代点x∗计算投影点yk=∏X(xk-τF(xk)),用armijo 线性搜索在连接两点xk,yk 的线段上确定一个点zk,使超平面

Hk={x ∈Rn,F(zk)T(x-zk)=0}

将xk 与变分不等式的解严格分离,然后将xk 投影到超平面Hk上,再将该投影点投影到约束集X 上,得到xk＋1.可以证明xk＋1 比xk 更接近变分不等式的解集.

非光滑方程组法的基本思想是把变分不等式问题或者它的最优性条件转化为一个与之等价的非光滑方程组,然后通过求解该方程组,从而得到原问题的解.非光滑化法的提出基于非光滑分析理论,mifflin 首先给出了关于实值映射的单变量半光滑函数的定义,QI 和SUN 将其推广为向量值半光滑函数,并给出了相应的非光滑形式的牛顿法.Fischer 在1992年引入了一种结构简单的NCP 函数,FB 函数及其他的NCP 函数的出现和半光滑理论的建立,进一步促进了非光滑方程组的发展.

不动点与零点迭代逼近及应用

相关推荐