Interior Hybrid Proximal Extragradient Methods for the Linear Monotone Complementarity Problem

Mauricio Romero Sicre | Benar Fux Svaiter

**Keywords:**

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.