论文部分内容阅读
变分不等式问题及其衍生出来的逆变分不等式问题在数学规划、交通控制以及经济平衡等诸多领域有着广泛的应用。在过去的几十年里,对于单调变分不等式,学者们给出了很多切实有效的数值算法。现实生活中的很多问题并没有显式的函数表达式,只能根据给定的自变量,观测到相应的函数值。只用函数值的方法(例如外梯度方法)在单调变分不等式的求解中仍然起着某种不可替代的重要作用。由于函数值的观测往往是代价不菲的,在应用只用函数值的算法的同时,考虑尽量少用函数值就特别有意义。
一般的外梯度算法都包含两步:一步预测和一步校正,其中预测步给出下降的方向,校正步中确定新的迭代点。投影收缩算法的贡献则相当于在外梯度算法校正步中运用了最优步长而提高收敛速度,最终达到求解问题少用函数值的目的。本文针对结构型的变分不等式,将约束优化理论与方法的研究中已经得到公认的一些思想与技术,用到距离函数下降方向的构造中来,达到提高算法收敛速度的效果。
论文分为三个部分,第一章的内容是变分不等式和逆变分不等式的一些介绍,包括基本定义、性质以及一些成熟的算法;第二章和第三章着重讨论变分不等式的一些具体的算法和应用;第四章和第五章主要研究逆变分不等式的一些性质、算法及其应用。
第二章的主要工作是结合了增广拉格朗日乘子法(ALM)和交替方向法(ADM)来求解结构型变分不等式。在预测步中,我们首先利用ALM的思想,将约束条件考虑在内,得到了Lagrange乘子的一个初步预测点。在此基础上,根据ADM,得到一个自变量和Lagrange乘子的共同预测点,这个过程实际上是采用了一个Gauss-Seidel迭代,这样可以更加及时的利用已有的迭代信息,有效的减少调用函数值的次数,而计算量却没有增加。另外我们也注意到[131]中提出了一种新的步长选取准则,在本章中,我们根据这种准则对校正步的最优步长做了进一步的研究。注意到分析要考虑所有的情形,不可避免地会用到一些不等式,据此得到的最优步长是保守的。我们对此做了更精细的分析,以确定新的步长,虽然这需要一些额外的计算,但是在每步迭代中并不增加函数值的调用次数,而在总体上达到减少计算函数值次数的目的。数值试验表明,基于这两点改进,我们的算法有较好的表现,比原先的方法减少约10%的调用函数值的次数。
第三章中,对单调变分不等式,经典的邻近点算法一般采用形如H(μ-μκ)的邻近项进行求解,这里的H(μ-μκ)是某个距离函数的导数,因此日必须是对称正定的。在本章中,我们对每个子问题的预测步采用了一个线性邻近项M(μ-μκ),这里的M只需正定而无需对称性。因此,M(μ-μκ)也不再是一个函数的导数。这种邻近项的修改使得算法具有更广泛的适用性,可以帮助我们解决多种类型的结构型变分不等式。另外在校正步中,我们提出了两种不同的下降方向和相应的最优步长选取准则。第一种下降方向是一个线性函数,因此迭代公式里只用到简单计算而无需投影。数值试验说明该方法不仅可行,而且有效的降低了计算量。第二种下降方向在采用相同的最优步长时,理论与实践上有更好的收敛性。我们同时证明了采用这两种下降方向的方法可以归结到一个统一框架里[82],不仅在表达上更加简洁直观,而且证明了第二种下降方向的优越性。在这个统一框架下,校正步采用第二种下降方向,并且利用第一种下降方向来计算最优步长。数值试验表明,算法的校正步经过这样的修改后表现更好。
在第四章中,我们首先从一些实际例子中引入逆变分不等式的概念,然后通过分析得出,它实际上可以扩展为高维的变分不等式。在此基础上,我们讨论了逆变分不等式的解的一些性质,并且对一类线性逆变分不等式提出一种简单的投影算法,我们给出了下降方向和步长选取准则,同时证明了算法的收敛性。数值试验也表明,该方法是切实可行的。
在第五章中,我们将逆变分不等式推广到一个连续化模型,对其采用逆变分不等式的算法来求解,在相当宽松的条件下,这个模型是全局收敛且渐近稳定的。