一种新的对偶原始算法的有效实现

Effective implementation of a novel dual primal algorithm

为了规避求解线性规划问题时存在的一系列不足(如受原始退化影响、迭代次数随规模大幅增长、占用中央处理器时间长等),提出了一种处理一般线性规划问题的新对偶原始算法(NDPA),即采用求解一系列无约束最小二乘问题获得残差,确定搜索方向,而不是通过经典非线性优化算法来处理约束最小二乘问题.通过随机生成的线性规划问题试验,初步证明NDPA在迭代次数和计算时间上相较修正后单纯形法具有较大优越性,且NDPA在运行时间上对于修正后单纯形法的优势随测试问题规模的增大而增强,符合对NDPA的期望.当问题规模等于200时,其计算时间可减少约48.87%.

To avoid some deficiencies such as being easily influenced by primal degeneracy, required more iterations, ran sometimes slower in terms of CPU time, etc., a novel dual primal(NDP) algorithm for solving general linear programming problems was proposed,where the search direction was determined by finding the residual of a series of unconstrained least squares problem, but not by some classical nonlinear optimized algorithms to dealing with constrained least squares problems. Through experiments of randomly constructed linear programming problems, it is proved that the NDP algorithm has more advantages than the revised simplex algorithm in iteration number and calculation time. Furthermore, the advantages of the NDP algorithm on running time have an obvious rising tendency when the problem size grows up. The result meets our expectations for the NDP algorithm.When the problem size is 200,the computing time reduces by about 48.87%.