An Infeasible Interior-point Algorithm for Monotone Linear Complementarity Problems

An Infeasible Interior-point Algorithm for Monotone Linear Complementarity Problems

In this study, we implement a variant of infeasible interior-point algorithm for solving monotone linear complementarity problems (LCP). We first reformulate the monotone LCP as an minimization problem. Then a descent iterative method is applied to the latter. The descent direction is computed via the Newton method. However, for maintaining the positivity of iterates, a novel and efficient strategy is proposed. Some numerical results are reported to show the efficiency of our proposed approach.

___

  • Achache, M., Roumili, H., Keraghel, A.: A numerical study of an infeasible primal-dual path-following algorithm for linear programming. Applied Mathematics and Computation (186)(2), 1472--1479 (2007)
  • Cottle, R.W., Pang, J.S., and Stone, R.E.: The Linear Complementarity Problem. Academic Press, San Diego (1992)
  • Wright, S.J.: Primal-Dual Interior Point Methods. SIAM, Philadelphia, USA (1997)