Corvinus
Corvinus

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

Darvay, Zsolt and Illés, Tibor and Rigó, Petra Renáta (2020) Predictor-corrector interior-point algorithm for sufficient linear complementarity problems based on a new type of algebraic equivalent transformation technique. Working Paper. Corvinus University of Budapest, Budapest.

[img]
Preview
PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
591kB

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.

Item Type:Monograph (Working Paper)
Series Name:Corvinus Economics Working Papers - CEWP
Series Number / Identification Number:2020/03
Uncontrolled Keywords:Predictor-corrector interior-point algorithm, P_* (κ)-linear complementarity problem, new search direction, polynomial iteration complexity
JEL classification:C61 - Optimization Techniques; Programming Models; Dynamic Analysis
Subjects:Mathematics, Econometrics
Projects:NKFIH 125700 - OTKA, BME IE-MI-FM TKP2020 - Budapest University of Technology and Economics, AGC32921/30.07.2019 - Babes-Bolyai University
ID Code:5908
Deposited By: Ádám Hoffmann
Deposited On:14 Sep 2020 15:22
Last Modified:14 Sep 2020 15:32

Repository Staff Only: item control page