Corvinus
Corvinus

Predictor-corrector interior-point algorithm based on a new search direction working in a wide neighbourhood of the central path

Illés, Tibor and Rigó, Petra Renáta and Török, Roland (2021) Predictor-corrector interior-point algorithm based on a new search direction working in a wide neighbourhood of the central path. Working Paper. Corvinus University of Budapest, Budapest.

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

Abstract

We introduce a new predictor-corrector interior-point algorithm for solving P_*(κ)-linear complementarity problems which works in a wide neighbourhood of the central path. We use the technique of algebraic equivalent transformation of the centering equations of the central path system. In this technique, we apply the function φ(t)=√t in order to obtain the new search directions. We define the new wide neighbourhood D_φ. In this way, we obtain the first interior-point algorithm, where not only the central path system is transformed, but the definition of the neighbourhood is also modified taking into consideration the algebraic equivalent transformation technique. This gives a new direction in the research of interior-point methods. We prove that the IPA has O((1+κ)n log⁡((〖〖(x〗^0)〗^T s^0)/ϵ) ) iteration complexity. Furtermore, we show the efficiency of the proposed predictor-corrector interior-point method by providing numerical results. Up to our best knowledge, this is the first predictor-corrector interior-point algorithm which works in the D_φ neighbourhood using φ(t)=√t.

Item Type:Monograph (Working Paper)
Series Name:Corvinus Economics Working Papers - CEWP
Series Number / Identification Number:2021/02
Uncontrolled Keywords:predictor-corrector interior-point algorithm; P_*(κ)-linear complementarity problems; wide neighbourhood; algebraic equivalent transformation technique
JEL classification:C61 - Optimization Techniques; Programming Models; Dynamic Analysis
Subjects:Mathematics, Econometrics
ID Code:6474
Deposited By: Ádám Hoffmann
Deposited On:04 May 2021 15:28
Last Modified:04 May 2021 15:30

Repository Staff Only: item control page

Downloads

Downloads per month over past year

View more statistics