Unified approach of primal-dual interior-point algorithms for a new class of AET functions

Illés, Tibor and Rigó, Petra Renáta and Török, Roland (2022) Unified approach of primal-dual interior-point algorithms for a new class of AET functions. Working Paper. Corvinus University of Budapest, Budapest.

PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader


We propose new short-step interior-point algorithms (IPAs) for solving P_* (κ)-linear complementarity problems (LCPs). In order to define the search directions we use the algebraic equivalent transformation technique (AET) of the system which characterizes the central path. A novelty of the paper is that we introduce a new class of AET functions. We present the complexity analysis of the IPAs that use this general class of functions in the AET technique. Furthermore, we also deal with a special case, namely φ(t)=t^2-t+√t. This function differs from the ones used in the literature in the sense that it has inflection point. It does not belong to the class of concave functions determined by Haddou et al. Furthermore, the kernel function corresponding to this AET function is neither eligible nor self-regular kernel function. We prove that the IPAs using any member φ of this new class of AET functions have polynomial iteration complexity in the size of the problem, bit length of the integral data and in the parameter κ. Beside this, we also provide numerical results that show the efficiency of the introduced methods.

Item Type:Monograph (Working Paper)
Series Name:Corvinus Economics Working Papers - CEWP
Series Number / Identification Number:2022/02
Uncontrolled Keywords:Interior-point algorithm, P∗ (κ)-linear complementarity problem, algebraic equivalent transformation technique, new class of AET functions
JEL classification:C61 - Optimization Techniques; Programming Models; Dynamic Analysis
Subjects:Mathematics, Econometrics
ID Code:7197
Deposited By: Ádám Hoffmann
Deposited On:21 Feb 2022 17:00
Last Modified:21 Feb 2022 17:00

Repository Staff Only: item control page


Downloads per month over past year

View more statistics