An Adaptive Infeasible Interior-Point Algorithm for Linear Complementarity Problems  

作　　者：Hossein Mansouri Mohammad Pirhaji 

机构地区：[1]Department of Applied Mathematics,Faculty of Mathematical Sciences,Shahrekord University,P.O.Box 115,Shahrekord,Iran

出　　处：《Journal of the Operations Research Society of China》2013年第4期523-536,共14页中国运筹学会会刊（英文）

基　　金：The authors are indebted to the referees for their careful reading of the manuscript and for their suggestions which helped to improve the paper.The authors also wish to thank Shahrekord University for financial support.

摘　　要：Interior-Point Methods(IPMs)not only are the most effective methods in practice but also have polynomial-time complexity.Many researchers have proposed IPMs for Linear Optimization(LO)and achieved plentiful results.In many cases these methods were extendable for LO to Linear Complementarity Problems(LCPs)successfully.In this paper,motivated by the complexity results for linear optimization based on the study of H.Mansouri et al.(Mansouri and Zangiabadi in J.Optim.62(2):285–297,2013),we extend their idea for LO to LCP.The proposed algorithm requires two types of full-Newton steps are called,feasibility steps and(ordinary)centering steps,respectively.At each iteration both feasibility and optimality are reduced exactly at the same rate.In each iteration of the algorithm we use the largest possible barrier parameter valueθwhich lies between the two values 117n and 113n,this makes the algorithm faster convergent for problems having a strictly complementarity solution.

关 键 词：Linear complementarity problem Infeasible-interior-point-method Central path Polynomial complexity 

分 类 号：O15[理学—数学]