A UNIFIED APPROACH TO INFEASIBLE-INTERIOR-POINT ALGORITHMS VIA GEOMETRICAL LINEAR COMPLEMENTARITY-PROBLEMS

There are many interior-point algorithms for LP (linear programming), QP (quadratic programming), and LCPs (linear complementarity problems) . While, the algebraic definitions of these problems are different fro m each other, we show that they are all of the same general form when we define the problems geometrically. We derive some basic properties related to such geometrical (monotone) LCPs and based on these propert ies, we propose and analyze a simple infeasible-interior-point algorit hm for solving geometrical LCPs. The algorithm can solve any instance of the above classes without making any assumptions on the problem. It features global convergence, polynomial-time convergence if there is a solution that is ''smaller'' than the initial point, and quadratic c onvergence if there is a strictly complementary solution.