A Primal-dual Interior-point Algorithm For P_*(?)NCP Based On A New Kernel Function

The interior-point algorithm emerged in the 1980s.Karmarkar,a famous scholar,made a pioneering and outstanding contribution to the theoretical research of the interior-point algorithm.He first proposed an interior-point algorithm for linear programming(LP)—gradient projection algorithm,which is the first real meaningful polynomial interior-point algorithm.It not only has better polynomial time complexity,but also has a breakthrough in actual calculation results.As a result,Karmarkar's algorithm has attracted a lot of scholars'research enthusiasm and achieved fruitful results.Nowadays,a variety of effective polynomial interior-point algorithm have been applied to solve LP,and have been successfully extended to many optimization problems,such as linear programming(LP),semi-definite programming(SDP),complementarity problem(CP)and second-order cone programming(SOCP),and so on,some corresponding optimization software packages have been developed and widely used.This paper mainly introduces the primal-dual interior-point algorithm based on a new kernel function for solving CP.As an important branch of mathematical programming,CP is widely used in various practical problems,such as contact mechanics,traffic balance,optimal control,and so on.P_*(?)linear complementarity problem(LCP)and P_*(?)nonlinear complementarity problem(NCP)are important complementarity problems.With the advancement of computational science,the interior-point algorithm gradually shows its great potential for solving large-scale CP.The paper is divided into five chapters.Chapter 1 briefly introduces the background,research status,some basic concepts and notations of interior-point algorithms and CP problems.Chapter 2 and Chapter 3 propose the large-update primal-dual interior-point algorithms based on a new kernel function for LP andP_*(?)LCP,respectively.Through complexity analysis,the iteration results are obtained,which are the currently best known iteration results for such methods.And the numerical examples also verify the feasibility of the algorithms.Chapter 4 extends the algorithm in Chapter 2 to_*P(?)NCP,and proves that the algorithm has polynomial complexity under certain assumptions.Chapter 5 designs a full-Newton step interior-point algorithm forP_*(?)LCP.The search direction of the algorithm is obtained by Darvay's algebraic equivalent transformation method,and it can also be determined by a positive-asympotic kernel function.The sixth chapter is the summary and outlook of the full paper.