论文部分内容阅读
论文研究基于投影的求解变分和逆不等式显式迭代方法,论述了显式迭代求解方法的特点。这里所说的显式方法是指求解的计算过程中只需要函数值的方法。变分和逆变分不等式有很多应用的数学问题,它们广泛见于物理、工程设计、交通运输以及管理科学等重要领域,因此研究变分和逆变分不等式求解方法的理论性质和实际计算表现具有重要的意义。实际生活中遇到的问题,函数一般没有显式表达式,只有函数值的信息是可获取的,因此众多隐式方法(需要函数甚至它的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的算法,该算法在计算过程中只需要已知点的函数值,因此具有实用性。我们证明了该算法的收敛性,基于应用背景的算例(带平衡约束的空间价格问题)证实了算法的有效性。