论文部分内容阅读
1984年,Karmarkar提出求解线性规划的新方法称为内点法,并证明该方法不但具有多项式复杂性,而且实际计算对大规模线性规划问题的效果优于单纯形方法.该算法发表后,掀起研究内点法的热潮.但是内点法要求解集有界性和对数障碍函数的一致凸性,为此冯果忱、于波、林正华提出了利用牛顿同伦和不动点同伦组合的组合同伦内点法,该算法对凸规划问题取消了解集有界性和对数障碍函数的一致凸性并且可以求解非凸规划问题,并在一定条件下证明了同伦路径的存在性和收敛性.但是组合同伦内点法需要可行内点作为初始点.
最近,于波、商玉凤提出动边界组合同伦算法,该算法取消了初始点必须为内点的限制,并能够求解更广泛的非凸规划问题.由于动边界组合同伦路径有可能从可行域外部趋近最优解,近似计算可能使得最后得到的近似解不满足约束条件,对很多实际问题不能满足要求.本文我们给出一种改进的动边界组合同伦算法,使得同伦路径对任意初始点,同伦路径的后半段都在可行域的内部,这样可以通过数值跟踪同伦路径得到在可行域内的近似解.我们给出同伦路径的存在性和收敛性证明,并通过数值实验验证新算法的有效性.