On a homogeneous algorithm for the monotone complementarity problem

Citation
Ed. Andersen et Yy. Ye, On a homogeneous algorithm for the monotone complementarity problem, MATH PROGR, 84(2), 1999, pp. 375-399
Citations number
36
Categorie Soggetti
Mathematics
Journal title
MATHEMATICAL PROGRAMMING
ISSN journal
00255610 → ACNP
Volume
84
Issue
2
Year of publication
1999
Pages
375 - 399
Database
ISI
SICI code
0025-5610(199902)84:2<375:OAHAFT>2.0.ZU;2-P
Abstract
We present a generalization of a homogeneous self-dual linear programming ( LP) algorithm to solving the monotone complementarity problem (MCP). The al gorithm does not need to use any "big-M" parameter or two-phase method, and it generates either a solution converging towards feasibility and compleme ntarity simultaneously or a certificate proving infeasibility. Moreover, if the MCP is polynomially solvable with an interior feasible starting point, then it can be polynomially solved without using or knowing such informati on at all. To our knowledge, this is the first interior-point and infeasibl e-starting algorithm for solving the MCP that possesses these desired featu res. Preliminary computational results are presented.