论文部分内容阅读
近年来,投影收缩算法和交替方向法在求解变分不等式问题上的应用引起人们的关注。投影收缩算法主要用于求解单调变分不等式问题,其主要优点是在每步迭代过程中只需一至二步的简单投影运算以及每步迭代所产生的迭代点到解点的距离严格单调下降。交替方向法(又称为分裂算法)主要用于求解具有可分结构的大规模(例如交通平衡问题上、偏微分方程数值求解产生的)变分不等式问题,它将求解高维的原变分不等式问题转化为解一系列容易得多的低维的子问题,从而保证了算法的效率。
本文将这两种解变分不等式的数值算法应用到一些设置问题和组合优化问题上,包括单设备设置问题、多设备设置问题、轴辐网络设置问题和给定结构下的Steiner最小树问题。这些问题本质上都可以看作一类特殊的距离和的问题。利用范数的一个性质,可转化为一种结构简单的单调线性变分不等式问题来求解。
对于由单设备设置问题、多设备设置问题和本文中所提出的新的轴辐网络设置问题产生的单调线性变分不等式,我们可利用文[55]中的分裂算法来求解。算法第一步中的子变分不等式问题等价于一个线性方程组,根据其系数矩阵的性质,我们可以直接给出这个线性方程组的解的表达式,从而可以将此子变分不等式转化为一个显式的等式,大大地简化了计算的难度。在实际计算过程中,如果罚因子β过大或过小,都会使求解时间显著增加。因此,我们在每步迭代过程中采用自适应的调比准则,对过大或过小的罚因子β进行调整,以保证算法的效率。
在Steiner最小树问题中,由于每个正则点的度为1,Steiner点的度为3,其产生的单调线性变分不等式具有适于用投影收缩算法来求解的结构。本文采用了文[50]中的投影收缩算法,并通过计算和分析得出每步迭代中的计算工作量为O(N)。初步的数值试验表明,投影收缩算法在求解Steiner最小树问题上是简单有效的。
此外,我们还提出了解一类线性规划问题的分裂算法。在很多情况下,该分裂算法的两个子变分不等式问题均可化简为显式的等式来计算,从而可以提高算法的效率。文中还给出例子表明,如果在每步迭代过程中采取自适应的调比准则,算法会更具有实用性。