论文部分内容阅读
论文主要给出了一些变分不等式的数值解法．主要内容有下面五个单元．
在第一单元，即第二章，我们注意到Glowinski在交替方向法中引入松弛因子γ后，其中γ∈(0，√5+1/2)，可使交替方向法在实际求解结构变分不等式时更有效．在此工作基础上，我们也在具有邻近项的交替方向法中引入松弛因子γ，并证明了在具有邻近项的交替方向法中，松弛因子的取值范围仍然是(0，√5+1/2)，即当γ∈(0，√5+1/2)时，具有邻近项的交替方向法也收敛．
第二单元(即第三章)的主要工作是通过对步长的改善来改进修正的外梯度方法．外梯度方法及其修正方法都是求解变分不等式Ⅵ(Ω，F)的直接方法，在求解变分不等式的迭代过程中仅仅需要使用函数F的函数值．外梯度方法的这种性质使得其具有很好的实用性，因为对于一些来自实际问题的变分不等式，其函数F通常没有显式的表达式，只能根据给定的变量值观测到相应的函数值，而且这种函数值的观测通常需要通过代价比较大的试验．对此类变分不等式问题的求解，减少调用函数F的次数非常有实际意义．在这一章中，我们对修正的外梯度方法的步长给出了一种新的取法．利用新方法求解变分不等式Ⅵ(Ω，F)，虽然在确定新步长时需要一些额外的相对简单的计算，但可以达到减少计算函数值次数的目的。此外，我们给出了使用新步长的修正的外梯度方法的收敛性和步长的一些性质．大量数值试验表明使用新步长的修正的外梯度方法比原先的方法减少调用函数的次数大约在百分之12～25之间。
在第三单元(即第四章)，我们给出了一个不同于Frank—Wolfe方法及其修正方法的启发式算法，用来求解用户交通平衡问题中的非线性互补问题(这里出现的非线性互补问题是变分不等式的特例)。通过利用列生成技术以及平衡条件，新的算法不需要列举出每个起点与终点对之间的所有可行路径，但在获得用户交通平衡状态时，新算法能够给出交通平衡时所有的有流的路径及其路径上的流量大
小．此外，我们给出了该启发式算法的一些收敛性结果．对所给测试问题，数值试验表明该方法有较好的数值结果．
在第四单元(即第五章)，我们在矩阵分裂算法和邻近点算法的基础上，给出了一个求解线性互补问题的投影算法，并给出了算法的一些收敛性结果．进行的数值试验表明新方法对于试验问题比一些已有的方法需要较少的迭代次数，而且容易实现．进一步，数值试验还表明，对于试验问题，新方法的参数的选取对数值结果影响不大，有比较好的稳定性．
在第五单元，本文根据稀疏网络的特点，将第四章中求解用户交通平衡问题的启发式算法的子过程：Dijkstra最短路算法，进行了改进．对于一个边的长度为非负的网络，我们可以利用Dijkstra最短路算法给出单个顶点到网络上其他各项点之间最短路，在Dijkstra最短路算法的实现过程中，我们可以通过引入堆，使其计算量为O(m+nlogn)，其中m，n分别为网络的边数和顶点数。由于堆的建立和操作并不是很容易实现，因此，上述方法的实现稍微有点复杂．在附录A中，我们在Dijkstra最短路算法中引入一些很简单的，但很实用的处理方法，使得新算法避免了原先算法中堆的建立和操作，并保证算法的计算量为O(m+Dmaxlog(n!))，其中Dmax是网络中与同一顶点相连的边数的最大值．由于log(n!)≤nlogn，且公路交通网络中的Dmax通常都比较小，因此，该算法处理这类问题有一定的优势．
在最后的附录B中，我们给出了上述各章的部分Matlab程序．