Predictor-corrector interior-point algorithm for sufficient linear complementarity problems based on a new type of algebraic equivalent transformation technique

Zsolt Darvay, Tibor Illés and Petra Renáta Rigó

Corvinus Economics Working Papers (CEWP) from Corvinus University of Budapest

Abstract: We propose a new predictor-corrector (PC) interior-point algorithm (IPA) for solving linear complementarity problem (LCP) with P_* (κ)-matrices. The introduced IPA uses a new type of algebraic equivalent transformation (AET) on the centering equations of the system defining the central path. The new technique was introduced by Darvay et al. [21] for linear optimization. The search direction discussed in this paper can be derived from positive-asymptotic kernel function using the function φ(t)=t^2 in the new type of AET. We prove that the IPA has O(1+4κ)√n log⁡〖(3nμ^0)/ε〗 iteration complexity, where κ is an upper bound of the handicap of the input matrix. To the best of our knowledge, this is the first PC IPA for P_* (κ)-LCPs which is based on this search direction.

Keywords: Predictor-corrector interior-point algorithm; P_* (κ)-linear complementarity problem; new search direction; polynomial iteration complexity (search for similar items in EconPapers)
JEL-codes: C61 (search for similar items in EconPapers)
Date: 2020-09-14
New Economics Papers: this item is included in nep-cmp and nep-ore
References: Add references at CitEc
Citations:

Downloads: (external link)
https://unipub.lib.uni-corvinus.hu/5908/ original version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cvh:coecwp:2020/03

Access Statistics for this paper

More papers in Corvinus Economics Working Papers (CEWP) from Corvinus University of Budapest 1093 Budapest, Fõvám tér 8.. Contact information at EDIRC.
Bibliographic data for series maintained by Adam Hoffmann ().