Open AccessA path-following interior-point algorithm for linear and quadratic problems
Author(s) -
Stephen J. Wright
Publication year - 1993
Language(s) - English
Resource type - Reports
DOI - 10.2172/432434
Subject(s) - linear complementarity problem , monotone polygon , mathematics , interior point method , criss cross algorithm , linear programming , mixed complementarity problem , complementarity theory , quadratic programming , mathematical optimization , complementarity (molecular biology) , convergence (economics) , quadratic equation , regular polygon , path (computing) , algorithm , linear fractional programming , computer science , nonlinear system , physics , geometry , quantum mechanics , programming language , biology , economics , genetics , economic growth
We describe an algorithm for the monotone linear complementarity problem that converges for many positive, not necessarily feasible, starting point and exhibits polynomial complexity if some additional assumptions are made on the starting point. If the problem has a strictly complementary solution, the method converges subquadratically. We show that the algorithm and its convergence extend readily to the mixed monotone linear complementarity problem and, hence, to all the usual formulations of the linear programming and convex quadratic programming problems