论文部分内容阅读
本论文主要讨论两种运用在线性规划和半定规划中的内点的预估一校正算法。所谓的预估一校正算法就是在“预估”步之后再取一步“校正”步。大多数的路径一跟踪算法仅仅使用“预估”步骤,而不取“校正”步。为了至少保证最差情形的迭代复杂度,必须设定中心化参数的值,而这样一来就限制了可能的收敛速度。当我们固定中心化参数为0来允许大的改善,为了得到合理的步长,必须扩大预估步骤的中心路径的邻域范围,从而校正步骤就必不可少了,这就是预估一校正算法的由来。这两种算法最初的提出都只是固定迭代点在各自的狭小的参数邻域内,而且只能分别针对线性规划或半定规划中的某一种情况进行运算,因而都具有局限性,并且在一定程度上给使用者选取初始点造成限制。本文的工作就是改进算法,消除它们的这些局限性,并且对算法进行扩展,使得这两种算法在线性规划和半定规划中都能通用。
为此,本文做了以下几方面的工作:
1.分析了求解线性规划和半定规划的内点法的理论基础,指明了建立预估-校正算法的理论依据。
2.对于原来运用在半定规划中的预估-校正算法,将其参数范围扩大,理论证明改进的正确性,并作特殊化处理将改进后的算法扩展应用于线性规划中。
3.对于原来运用在线性规划中的预估-校正算法,先对其参数作一般化处理,改进算法,然后引入算子,变换系统形式,并给出理论证明,将改进后的算法扩展到半定规划中。
4.对改进扩展后的算法进行编程处理,简单举例说明,从数值计算的角度保证改进及扩展后预估-校正算法的可行性。