Preprint A738/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 prob-
lems 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.