Wide Neighborhood Interior-Point Algorithms With Arc-Search For Linear Complementarity Problem

Since the seminal paper of famous scholar Karmarkar in 1984,some experts and scholars at home and abroad have been working on the interior-point algorithm and achieved a lot of results.The interior-point algorithm has become one of the very efficient algorithms for solving linear programming.It not only has polynomial-time complexity but also has high efficiency in practice.Nowadays,the interior-point algorithm has been successfully generalized to convex programming,linear complementary problem,semi-definite programming,symmetric cone optimization and so on.This paper proposes the wide neighborhood interior-point algorithms with arc-search for convex quadratic programming,linear complementarity problem and semi-definite programming,and proves the polynomial iteration complexity of the new algorithms.The numerical experiments show that the algorithms are reliable and efficient.The whole paper contains five chapters.Chapter one introduces the research background,algorithm model,basic concept and basic notations;Chapter two proposes a wide neighborhood interior-point algorithm with arc-search for convex quadratic programming and proves the polynomial iteration complexity of the algorithm.The numerical experiments prove that the algorithm is feasible;The third chapter introduces the wide neighborhood interior-point algorithm with arc-search for P_*(k)linear complementarity problem and achieves the polynomial complexity of the algorithm.The numerical results verify that the algorithm has good computational efficiency;In Chapter four,based on the Nesterov-Todd symmetric strategy,we extend the arc-search interior-point algorithm for convex quadratic programming to semi-definite programming and give the proof of polynomial complexity for the algorithm.the summary and outlook is in Chapter five of this paper.