基于投影的求解变分不等式显式迭代方法

来源 :南京大学 | 被引量 : 0次 | 上传用户:awii0813
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
论文研究基于投影的求解变分和逆不等式显式迭代方法,论述了显式迭代求解方法的特点。这里所说的显式方法是指求解的计算过程中只需要函数值的方法。变分和逆变分不等式有很多应用的数学问题,它们广泛见于物理、工程设计、交通运输以及管理科学等重要领域,因此研究变分和逆变分不等式求解方法的理论性质和实际计算表现具有重要的意义。实际生活中遇到的问题,函数一般没有显式表达式,只有函数值的信息是可获取的,因此众多隐式方法(需要函数甚至它的Jacobi矩阵的解析表达式)无法实施,显式方法才符合解决实际问题的需要。此外,函数值的获得往往花费相当大的代价,因而求解方法需要尽量少地调用函数值来节省工作量。论文中显式方法是针对不同类型变分和逆变分不等式各自特性设计的,共同目的都是为了在实际应用中只用函数值信息;为了提高收敛速度,深入探讨了自调比技术和最优步长策略。文章主要内容有下面四个部分。   在第二章中,我们利用计算数学方面关于“预测校正”的思想,对变分不等式求解提出了一种新的只用函数值的方法。已有的外梯度方法可以看作一步预测加一步校正的(Prediction-Correction,简记PC)方法。预测产生距离函数的下降方向,校正产生新的迭代点。从几何直觉上讲,二次预测所生成的搜索方向更偏向解集,因而可以使得迭代点更快的接近解点。因此,我们利用外梯度算法和Runge-Kutta法的思想,提出了二次预测一次校正法(简称为PPC)。PPC的预测过程只利用当前已知点及其相应的函数值信息,而不需要函数的表达式。PPC方法在每一步迭代通常需要计算3次函数值,而外梯度方法通常只需要计算2次函数值,虽然PPC方法每步迭代的计算量增加了,但是却可能在总体上提高了收敛速度。在论文中,我们分析并证明了PPC方法的收敛性。为了比较PPC和PC方法,在相同的运行环境以及相同的参数设置下,进行了数值试验,发现PPC方法在总迭代步数,总函数值计算次数以及CPU计算时间可以比PC方法减少,显示了PPC方法的有效性及潜在优势。   第三章节主要是讨论求解带多面体约束的变分不等式问题。我们在外梯度方法的基础上,提出一种自调比的预测校正法(Self-Adaptive Prediction-CorrectionMethod,简记SAPC)。在预测过程中,我们对自变量和Lagrange乘子分别处理,采用Gauss-Seidel格式,及时更新信息。在实际计算中,我们使用一种自调比技术来自动平衡自变量和拉格朗日乘子,并分析了最优步长的选取法则。该调比技术实施过程简单,只需利用已知的函数值信息。我们同样采用类似的思想自动调整步长为下一步服务。我们在与外梯度方法同样宽松的假设条件下证明了SAPC方法的收敛性。我们通过交通平衡问题和随机的带约束的二次规划问题验证SAPC方法的有效性。计算实践证明SAPC方法比一般的PC方法的收敛速度提高了许多,此外,算法中的自调比成份是必不可少的。   第四章节主要是求解带耦合线性约束可分凸规划。已有分解类型的方法只适用于求解特殊的耦合线性等式约束,并且子问题的求解代价高。我们结合增广拉格朗日方法和邻近点算法(PPA)思想,提出一种分解方法,非对称临近分解方法(Asymmetric Proximal Decomposition Method,简记AsDPM),可以求解一般的耦合线性约束可分凸规划。该方法是在拉格朗日函数中加入辅助的二次项,使之具有可分性质,在每步迭代计算中可独立地并行求解N个子极小化问题。在此基础上,我们还提出了AsPDM的非精确求解形式,其目的是降低求解子问题的工作量。非精确形式在求解N个子极小化问题的过程只需要利用各自子问题的函数值信息,并且相应的非精确准则是可并行实施的,子问题步长的选取只与子问题自身有关,保持了精确形式可分的优点。我们把可分凸规划转化成结构型变分不等式,在此框架下分析并证明了非精确AsPDM的收敛性,此外还详细探论了AsPDM算法与经典PPA之间的联系与区别。   第五章节主要是讨论如何求解带线性约束的逆变分不等式CIVI。为了说明CIVI在系统控制中具有广泛的应用背景,我们先引入一个空间价格平衡的例子。传统的空间价格平衡问题对平衡状态是无约束的,是一个经典的变分不等式。我们对平衡状态进行了约束,就是CIVI,求解满足约束的平衡状态问题就是求解CIVI。为了求解CIVI,我们转化CIVI成一个特殊的广义变分不等式GVI。利用这个GVI结构的特殊性,我们提出类临近点算法求解这个GVI,并证明了该算法的收敛性。但是该算法求解过程代价高,为此我们提出了一种基于PPA的算法,该算法在计算过程中只需要已知点的函数值,因此具有实用性。我们证明了该算法的收敛性,基于应用背景的算例(带平衡约束的空间价格问题)证实了算法的有效性。
其他文献
当学生小学比业升入初中以后,由于个体差异,学生的两极分化日益严重,在数学方面尤为突出。要全面提高数学的教学质量,“如何转化学困生”就是初中数学教师首先要解决的问题。
三连杆刚性机械臂是一个复杂的动力学系统,实现刚性机械臂高精度控制必须考虑系统动力学特性,其模型的建立是极其重要的。动力学建模为控制器设计提供依据。本文采用基于Takagi
半群代数理论最先源于Sushkevich在1937年编的一本书广义群论.从那时起,在许多数学工作者和其他科目的推动下已经发展成关于特别的对象、特别的课题和特别的方法的一个代数分
在初中数学几何教学中,圆是一个重要内容。在圆中作辅助线来证明和求解圆的有关问题,又是一个重点和难点问题。怎样才能顺利解决这个问题呢?我经过多年的教育教学实践,用圆中
本文利用活动标架法和射影光锥模型来研究四维Lorentz空间形式Q41中类空曲面的polar变换。对于Q41中类空曲面,我们构造了一类变换,称为polar变换。我们证明,polar,变换将类空Will
在半群理论中,研究半群的扩张是一类非常重要的问题,而平移壳和共轭壳是研究这类问题的非常重要和有效的工具.Petrich在1980年的文章[9]中首先研究了逆半群的共轭壳,从而获得了逆
在金融市场中,市场风险是最主要的风险,而20世纪90年代初的金融灾难,即发生在巴林银行、日本大和银行以及其它一些金融机构的灾难性事件,使人们意识到,市场风险对金融机构以及公司
本文比较了高斯伪似然准则、修正后的准则以及基于经验似然的准则在连续和离散数据中,选择GEE方法中工作相关矩阵的效果。在此基础上,我们探讨了对多个纵向数据同时选择工作选
本文研究了二阶线性微分方程f"+eazf+h(z)ebzf=O的解以及它们的一阶,二阶,三阶导数,微分多项式取小函数的点的收敛指数,其中a,b是非零复常数且a=cb(c>1),h(z)是非零多项式。并研究
实施素质教育是教育形势发展和教育改革的需要,而培养学生想象力是社会发展的需要。本文阐述了培养学生的数学想象力是实现数学教学目标的需要,是学生生理和心理发展的需要,