The Research Of An Interior Point Algorithm For A Class Of Nonmonotonic Linear Complementarity Problem

In 1947, Danzig presented the conception of linear programming and the famous simplex algorithm. Although the simplex method is efficient in some practical applications, it is not the polynomial time algorithm. In 1978, the first polynomial algorithm for linear programming problem--the ellipsoidal method was proposed by L.G.Khachiyan. But unfortunately, the practical implementation of the algorithm has been irremediably inefficient than the simplex method. So many scholars tried to design a polynomial algorithm with better calculation efficiency for solving linear programming.In 1984, by use of the potential function and the projection transformation, Karmarkar proposed a algorithm for linear programming--interior point algorithm. Since the publication of Karmarkar's paper, interior point algorithm has been a very active research direction in mathematical programming in recent 20 years. Karmarkar's algorithm not only has a better polynomial complexity than the ellipsoid method, but is also a challenging competitor of the simplex method in practice, especially for large scale problems.This thesis is devoted to studying the complementarity problems, which is an important branch in mathematical programming and possesses extensive applications in many fields such as economy analysis and traffic equilibrium. Therefore, it is significant to study the algorithm for solving the complementarity problems. The thesis mainly deals with the study of interior point algorithms for the non-monotone linear complementarity problems, and analyzes its convergence in detail. At last, some numerical experiments show the efficiency of methods.The thesis contains five chapters. Charpter one introduces some fundamental knowledge of the complementarity problem, then describes the historical background and then present research conditions of interior point algorithm.The second and third chapters are the core parts of this thesis. Chapter two discusses the interior-point algorithm for solving the non-monotone linear complementarity problem by using different neighborhoods. In charpter three, based on a specific algebraic transformation and the frame of KMM algorithm , a new infeasible interior algorithm for P₀ linear complementarity problem is proposed,and its global convergence analysis is also given.Chapter four is the numerical experiments and the results show the effectiveness of the proposed algorithms. Finally, a conclusion is made regarding the discuss topic together with the further expectation.