A Full-Newton Step Interior-Point Method for Monotone Weighted Linear Complementarity Problems

Soodabeh Asadi, Zsolt Darvay, Goran Lesaja, Nezam Mahdavi-Amiri, Florian Potra

Research output: Contribution to journalArticlepeer-review

31 Scopus citations

Abstract

In this paper, a full-Newton step Interior-Point Method for solving monotone Weighted Linear Complementarity Problem is designed and analyzed. This problem has been introduced recently as a generalization of the Linear Complementarity Problem with modified complementarity equation, where zero on the right-hand side is replaced with the nonnegative weight vector. With a zero weight vector, the problem reduces to a linear complementarity problem. The importance of Weighted Linear Complementarity Problem lies in the fact that it can be used for modelling a large class of problems from science, engineering and economics. Because the algorithm takes only full-Newton steps, the calculation of the step size is avoided. Under a suitable condition, the algorithm has a quadratic rate of convergence to the target point on the central path. The iteration bound for the algorithm coincides with the best iteration bound obtained for these types of problems.

Original languageEnglish
Pages (from-to)864-878
Number of pages15
JournalJournal of Optimization Theory and Applications
Volume186
Issue number3
DOIs
StatePublished - Sep 1 2020

Scopus Subject Areas

  • Management Science and Operations Research
  • Control and Optimization
  • Applied Mathematics

Keywords

  • Full-Newton step
  • Interior-point
  • Path-following
  • Weighted complementarity

Fingerprint

Dive into the research topics of 'A Full-Newton Step Interior-Point Method for Monotone Weighted Linear Complementarity Problems'. Together they form a unique fingerprint.

Cite this