On a Homogeneous Algorithm for the Monotone Complementarity problem
Erling D. Andersen and Yinyu Ye
We present a generalization of a homogeneous self-dual linear
programming (LP) algorithm to solving the
monotone complementarity problem (MCP). The
algorithm does not need to use any ``big-M'' parameter or two-phase method,
and it generates either a solution converging towards feasibility and
complementarity 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 information at all. To our knowledge,
this is the first interior-point and infeasible-starting algorithm
that possesses these desired features for solving the MCP.
Preliminary computational results are presented.
![[DVI]](../../InteriorPoint/gif/DVI.gif)
![[POSTSCRIPT]](../../InteriorPoint/gif/PS.gif)
![[IP PAGE]](../../InteriorPoint/gif/HOME.gif)
![[SEARCH AGAIN]](../../InteriorPoint/gif/SEARCH.gif)