A New Primal Dual Interior Point Method For Linear Programming

Linear programming is not only the earliest branch of operations research,but also a branch widely used in production and life.Linear programming can be used to solve the problems of automatic control,engineering design,space technology and so on.Therefore,the study of linear programming has important realistic significance.Path following method is a class of effective methods for solving linear programming.In each iteration,the method strictly limits the iteration point to a neighborhood of the central path,and reaches the optimal solution of the problem along the central path.In each iteration of the method,each component on the right side of the complementarity condition is the same value relaxation.Based on the path following method,this paper propose a new primal-dual interior point method for linear programming.This paper adds a quadratic term to the objective function of the linear programming.In this paper,we make substitution for variables in the KKT condition of the new problem.This paper relaxes the new variables and complementarity conditions.In each iteration,each component on the right side of the complementarity condition depends on the corresponding component of the current iteration point.This paper defines a new center path neighborhood.Under certain conditions,the solution generated by the method in this paper converges to the optimal solution of the original problem.This paper tests the artificial synthesis problems and the Netlib test collection.The error between the real optimal value and the optimal value produced by the method in this paper is within a certain range,so the method in this paper is effective.