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

PDF
 Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
591kB 
Abstract
We propose a new predictorcorrector (PC) interiorpoint 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 positiveasymptotic 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:  Predictorcorrector interiorpoint 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 IEMIFM TKP2020  Budapest University of Technology and Economics, AGC32921/30.07.2019  BabesBolyai 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