A Potential-Reduction Algorithm for Linear Complementarity Problems

摘要

F'easible-interior-point algorithms start from a strictly feasible interior point, but infeassible-interior-point algorithms just need to start from an arbitrary positive point, we give a potential reduction algorithm from an infeasible-starting-pointfor a class of non-monotone linear complementarity problem. Its polynomial complexity is analyzed. After finite iterations the algorithm produces an approximate solution of the problem or shows that there is no feasible optimal solution in a large region.