论文部分内容阅读
互补问题的理论和算法在经济学,对策论和数学规划领域有着广泛的应用,关于互补问题的研究一直是非线性科学和计算科学的热点问题,求解互补问题的算法的研究也取得了很多成果.在这些算法之中,内点算法一直是个非常活跃的研究方向.因为内点算法具有更优越的计算复杂度,而且在实际计算中,尤其对大规模问题更显其高效性.正是由于内点算法的这种优点,人们希望内点算法不只是解决维向量的互补问题,还可以解决大规模矩阵的问题.在进行了大量研究后, Kojima M等人提出关于对称矩阵的半定线性互补问题(SDLCP),并且在单调仿射子空间的假设下,构造了以沿着中心路径的牛顿方向为搜索方向的内点算法的理论框架.
本文主要是在Kojima M所提出的关于对称矩阵的单调半定线性互补问题的理论基础上,用另外一种搜索方向(NT方程组)构造内点算法来求解这个问题.Kojima M的关于对称矩阵的SDLCP研究中,采用的中心路径上的牛顿方向产生的矩阵不能保证对称性,而Nesterov-Todd改进后得出的NT方程组是可以保持对称性的.文中以NT方程组的解为搜索方向,分别构造了单调线性算子条件下的路径跟踪法和势函数约减法.其中路径跟踪法要求初始点在中心路径邻域内,并且选取步长为1的窄邻域中心路径.并且分析了这种窄邻域路径跟踪算法的可行性及收敛性.而文中的势函数约减法不同于先前的路径跟踪法,它的初始点只要求在严格可行域,使用一维搜索确定步长,使得势函数在每步迭代时都达到最优.并且讨论了这种算法的可行性,确定了最小下降量,进一步分析了计算复杂度.考虑到单调算子的局限性,所以文中对单调互补问题进一步推广到了一类非单调算子(线性算子)条件下矩阵线性互补问题的路径跟踪算法,并且讨论了可行性,收敛性和计算复杂度.