Preprint A734/2013
Interior Hybrid Proximal Extragradient Methods for the Linear Monotone Complementarity Problem.
Mauricio Romero Sicre | Benar Fux Svaiter

We present new infeasible path-following methods for linear monotone complementarity problems based on Auslander, Tebboulle, and Ben-Tiba's log-quadratic barrier functions. The central paths associated with these barriers are always well defined and, for those problems which have a solution, convergent to a pair of complementary solutions. Starting points in these paths are easy to compute. The theoretical iteration-complexity of these new path-following methods is derived and improved by a strategy which uses relaxed hybrid proximal-extragradient steps to control the quadratic term. Encouraging preliminary numerical experiments are presented.