The Research Of Interior-point Algorithm For Weighted Complementarity Problems

This paper mainly studies the complementary problem and its algorithm,in addition we also introduced some application of complementary problem in economic.As a generalization of complementary problem,weighted complementary problem is first proposed by Potra(SIAM Journal on Optimization)in 2012.The paper points out that some equilibrium problems in the field of the economy's,such as Fisher market equilibrium problem can be reduced to the weighted linear complementary problem,and this problem can be solved by interior point algorithm effectively.So far,for the new mathematical model of the weighted complementarity problems,there is few research achievements of corresponding theory and algorithm,therefore,we first study the classic complementary problem and the corresponding theory and algorithm,based on these study,we focus on the interior point algorithm for weighted complementarity problems,analyze the convergence for this algorithm,and study the corresponding numerical calculation results,etc.All parts of the this text contents are arranged as following:The first chapter is the introduction,which introduces the research background and current situation of the complementary problem and its algorithm.Besides that,this chapter also gives some basic concepts and symbol conventions which are often used in the complementary problems.The second chapter introduces a few class model of the classic complementary problem,and gives the weighted complementary problem,especially the monotonous model of weighted complementary problem,what's more,the conversion from the Fisher market equilibrium problem used in the field of economic to the weighted complementary problem is presented in this paper.The third chapter mainly introduces the basic idea,important concepts and algorithm framework of path-following interior point algorithm.Besides that,based on the new definition of wide neighborhood,we propose the path-following method to solve weighted complementary problem,analyze the feasibility of the method and its iteration complexity.In the fourth chapter,we improve the path-following method for weighted complementarity problems in third chapter,propose a new path-following method based on a kind of new direction with a parameter ?,and prove that this method can reduce the iteration complexity.In the end,we give the corresponding numerical experiments to verify the effectiveness of the algorithm.The fifth chapter is the summary of the our work and the expectation for the future.