Research On Three Types Of Wide Neighborhood Interior-point Algorithms For Linear Programming

Linear programming（LP for short）is widely used in agriculture,military,economics,man-agement and engineering,etc.It provides managers with scientific management basis and opti-mal decision-making for the rational use of limited resources.Therefore,LP has become one of the hot research topics.And people designed a lot of algorithms for LP.Early typical algorithms are:simplex method and ellipsoid algorithm.However,the simplex method does not have poly-nomial complexity,and the ellipsoid algorithm does not have good numerical effects.Therefore,scholars began to look for algorithms with the advantages of both.Until 1984,Karmark proposed the interior point algorithm,which has polynomial complexity,and its numerical effect can be compared with the simplex method.At present,the contradiction between theory and practice in the field of interior point algorithm research is an open problem.This paper focuses on this contradiction and the contents are as follows:In the first chapter,we first introduces the research background and research significance,and then introduces the prerequisite knowledge and the main arrangement of this article.In the second chapter,we first study the wide neighborhood primal-dual interior-point al-gorithm of N_∞^-（γ）and N（τ,β）.Then we focused on the wide neighborhood primal-dual interior-point algorithm of N₁（τ,β）.And we theoretically proved that the algorithm has the best algorith-m complexity O(n^1/2L)of the current feasible interior-point algorithm.Finally,through numerical experiments,we show that the three types of the wide neighborhood primal-dual interior-point algorithm are effective.In the third chapter,we design a variant of the Mehrotra type predictive-correction algo-rithm.In this algorithm,time and number of iterations are improved by adding a variant form of the Mehrotra type correction step to the wide neighborhood primal-dual interior-point algorith-m.And we prove the effectiveness of the algorithm through theoretical analysis and numerical experiments.Finally,we made a summary and outlook on the paper.The focus of this article is to study one-norm wide neighborhood N₁（τ,β）.The neighborhood is wider than N_∞^-（γ）and narrower than N（τ,β）,and it has the same algorithm complexity O(n^1/2L)as N（τ,β）neighborhood.Second,we use an important inequality‖uv‖₁≤‖u‖·‖v‖,and improved the algorithm complexity based on this inequality.Finally,we illustrate the value of research N₁（τ,β）by comparing the numerical experimental results of three types of wide neighborhoods.