Researches On The Potential Reduction Interior-point Algorithm

Although the simplex method is efficient in practical application, it is not the polynomial time algorithm in theory, which led to the research on polynomial algorithm for the linear programming problem. In 1978 the first polynomial algorithm for the linear programming problem, the ellipsoidal method, was presented by L.G Khachiyan and resulted in great impact on the theory of complexity, but unfortunately the practical implementations of the algorithm have been inefficient than the simplex method. In 1984, N.Karmarkar found a new algorithm for linear programming— Karmarkar's algorithm, which makes a great breakthrough in linear programming. Karmarkar's algorithm not only has a better polynomial complexity than the ellipsoid method, but also is a challenging competitor of the simplex method in practice, especially for large-scale problems. Different from the simplex method, which choose the optional point along the boundary of the feasible region, Karmarkar's algorithm is based on the construction of the simplex method, which starts from the originally feasible interior-point, walks up in the feasible region to the optional point following the steepest descent direction. So Karmarkar's algorithm is also called interior-point method. Since the publication of Karmarkar's paper, interior point methods theory has been a very active research direction in mathematical programming.This thesis is devoted to researching on the potential reduction interior point algorithm. Using partial updating and the Sherman-Morrison-Woodbury rule on the top of the frame work developed by Kojima, Minzuno, Yoshise, we developed a modified potential reduction interior point algorithm to solve the linear complementarity problems with positive semi-definite matrices. The total number of iterations requiredby our algorithm is at most O(^1/2nL), and the total number of arithmetic operationsis O(rn²), and its steps are not constrained by the need to remain approximatelycentered. The global convergence results for these algorithms are established and some numerical test also included.