Research On Infeasible Interior-point Algorithms In Linear Programming

Interior point algorithm is a farily effective algorithm to solve linear programming problem. The algorithm favored by more and more research workers after many successful improvements. This paper focuses on interior-point algorithm for solving linear programming, Unlike the previous linear search iterative direction, in the last two chapters we use the arc search iteration direction to find the optimal solution, Under the condition of initial points not feasible, we discuss algorithms’ iteration complexity and numerical experience results.Firstly, we make a brief introduction to research problem and some basic knowledge that is necessary for complexity analysis.Secondly, due to the second order type Mehrotra estimates-correction algorithm has been widely used in linear programming, using the the new method of adaptive update given by [44], An infeasible Mehrotra predictor corrector algorithm in the wide neighborhood is presented with this updating method. At last, we testify the complexity bound of the presented algorithm is O(n3/2log(1/ε)) without employing safeguards.Thirdly, Consider in practical application, the choice of feasible initial point rather difficult, based on Yang[34]proposed a polynomial arc-search interior-point algorithm for linear programming, which searches optimizers by using the ellipse and uses correction step, we put forward an infeasible-interior-point method to consider the same problem. In this case, the complexity bound of the algorithm is O(n5/4log(1/ε))Finally, because of the limitation of narrow neighborhood, we give an corresponding polynomial arc search infeasible interior point algorithm for linear programming based on wide neighborhood of infeasible,in the last, we derive the complexity bound of the algorithm is O(n3/2log(1/ε)).