论文部分内容阅读
变分不等式问题在数学规划、交通工程、经济平衡等应用科学领域有着广泛的应用．在过去的数十年中，涌现出大量的求解单调变分不等式问题的数值算法，其中简单易行的投影算法(Projection Method)从一开始就备受关注．在现实生活中，很多问题一般没有函数表达式，只能对给定的自变量，观测到相应的函数值，而这种观测往往是代价不菲的。基于这样的考虑，我们着眼于只用函数值的方法，更关心调用函数值次数少的实用投影算法．
本文主要从应用和算法两个方面来研究变分不等式．在应用方面，我们对一类较为普遍的交通问题建立了数学模型，并将其归结为非线性互补问题，这是一种特殊的变分不等式问题．我们使用直接自调比投影算法去求解这类问题．由于计算代价较小，计算实践证明这种方法确实是有效的。
在算法方面，本文致力于研究投影算法中的邻近点类算法(Proximal Point Algo—rithm)．它通过求解一系列条件较好的同类子问题而得到原问题的解，该方法一般具有线性收敛性．注意到传统的邻近点算法在有些时候并不实用，因为在迭代过程中精确求解子问题往往代价很高．而在此基础上提出的近似邻近点算法(Approximate ProximalPoint Algorithm)则不必精确求解子问题，很好地弥补了传统算法的不足，因此得到了迅速发展．面对种类繁多的近似邻近点算法，我们最为关心的是在实际应用中哪些算法更加实用．本文剖析了两种近似邻近点算法，这两种方法具有相同的不精确准则和步长，但是搜索方向不同．总体说来它们每一步的计算量相当，收益却有所差异，
其中一种方法无论从理论还是计算上来看都优于另外一种方法． 由He，Yang and Yuan[Journal of Mathematical Analysis and Applications，300(2)，pp．362-374，2004]提出的近似邻近点算法(HYY method)是Solodov-Svaiter[MathematicalProgramming Ser．B，88(2)，pp．371-389，2000]近似邻近点算法(SS method)的改良方法.在此基础上，本文提出了一种改进的下降方法．与前两种方法相比，这种新方法可以充分利用已有的信息来获得最优步长，保证每一步尽可能取得较好的收益．我们通过网络平衡问题的一个实例，分别使用三种方法进行数值实验，结果表明新方法更加实用．
接下来我们研究一类带约束的极小极大问题的数值求解方法．对线性约束引入Lagrange乘子后，这类极小极大问题转化为常见的结构型变分不等式，可以用增广Lagrange乘子法(Augmented Lagrangian Method)求解．为了将高维的变分不等式子问题转化为一系列容易得多的低维子问题，我们把邻近点算法和增广Lagrange乘子法巧妙地结合起来，提出了一种新的邻近点类型的预测校正交替方向法(Prediction-Correction Alternating Direction Method)．并且证明了新方法是全局收敛的。
对基本投影法的延伸扩展也是我们感兴趣的问题．实际生活中，有一类变分不等式不满足强单调且Lipschitz连续，而只满足相对较弱的”上强制”条件．经济平衡里关于政策干预和市场行为的双层规划中的上层问题就是上强制变分不等式．针对这类有应用背景的问题我们提出了一种改进的投影下降算法，它利用扩展的基本投影法生成的迭代点构造了一个新的下降方向和最优步长．考虑到在实际应用中每次调用函数值可能花费较大，我们相应地提出了减少函数调用次数的调比策略．
本文提出的实用投影算法通过选取合适的下降方向和最优步长，用较少的计算时间(或存储)就可以得到原问题的可靠解．对于这些新提出算法，我们都提供了数值实验来说明新方法的实用性．