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 from 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 properties, we propose and analyze a simple infeasible-interior-point algorithm 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 convergence if there is a strictly complementary solution.This research was performed while the first author was visiting the Institute of Applied Mathematics and Statistics, Würzburg University as a Research Fellow of the Alexander von Humboldt Foundation.