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.
|
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