Large-step predictor-corrector interior point method for sufficient linear complementarity problems based on the algebraic equivalent transformation
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 techni...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2023-01-01
|
| Series: | EURO Journal on Computational Optimization |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S2192440623000163 |
| _version_ | 1827582800041082880 |
|---|---|
| author | Tibor Illés Petra Renáta Rigó Roland Török |
| author_facet | Tibor Illés Petra Renáta Rigó Roland Török |
| author_sort | Tibor Illés |
| collection | DOAJ |
| description | 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 method, 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 algorithms. We prove that the interior-point method has O((1+κ)nlog((x0)Ts0ϵ)) iteration complexity. Furthermore, we show the efficiency of the proposed predictor-corrector algorithm by providing numerical results. To our best knowledge, this is the first predictor-corrector interior-point algorithm which works in the Dφ neighbourhood using φ(t)=t. |
| first_indexed | 2024-03-08T22:57:49Z |
| format | Article |
| id | doaj.art-b758ea0012c34cc4a055566db89c2eef |
| institution | Directory Open Access Journal |
| issn | 2192-4406 |
| language | English |
| last_indexed | 2024-03-08T22:57:49Z |
| publishDate | 2023-01-01 |
| publisher | Elsevier |
| record_format | Article |
| series | EURO Journal on Computational Optimization |
| spelling | doaj.art-b758ea0012c34cc4a055566db89c2eef2023-12-16T06:07:00ZengElsevierEURO Journal on Computational Optimization2192-44062023-01-0111100072Large-step predictor-corrector interior point method for sufficient linear complementarity problems based on the algebraic equivalent transformationTibor Illés0Petra Renáta Rigó1Roland Török2Corvinus University of Budapest, HungaryCorvinus University of Budapest, Hungary; Corresponding author.Doctoral School of Economics, Business and Informatics, Corvinus University of Budapest, HungaryWe 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 method, 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 algorithms. We prove that the interior-point method has O((1+κ)nlog((x0)Ts0ϵ)) iteration complexity. Furthermore, we show the efficiency of the proposed predictor-corrector algorithm by providing numerical results. To our best knowledge, this is the first predictor-corrector interior-point algorithm which works in the Dφ neighbourhood using φ(t)=t.http://www.sciencedirect.com/science/article/pii/S2192440623000163Predictor-corrector interior-point algorithmP⁎(κ)-linear complementarity problemsWide neighbourhoodAlgebraic equivalent transformation technique |
| spellingShingle | Tibor Illés Petra Renáta Rigó Roland Török Large-step predictor-corrector interior point method for sufficient linear complementarity problems based on the algebraic equivalent transformation EURO Journal on Computational Optimization Predictor-corrector interior-point algorithm P⁎(κ)-linear complementarity problems Wide neighbourhood Algebraic equivalent transformation technique |
| title | Large-step predictor-corrector interior point method for sufficient linear complementarity problems based on the algebraic equivalent transformation |
| title_full | Large-step predictor-corrector interior point method for sufficient linear complementarity problems based on the algebraic equivalent transformation |
| title_fullStr | Large-step predictor-corrector interior point method for sufficient linear complementarity problems based on the algebraic equivalent transformation |
| title_full_unstemmed | Large-step predictor-corrector interior point method for sufficient linear complementarity problems based on the algebraic equivalent transformation |
| title_short | Large-step predictor-corrector interior point method for sufficient linear complementarity problems based on the algebraic equivalent transformation |
| title_sort | large step predictor corrector interior point method for sufficient linear complementarity problems based on the algebraic equivalent transformation |
| topic | Predictor-corrector interior-point algorithm P⁎(κ)-linear complementarity problems Wide neighbourhood Algebraic equivalent transformation technique |
| url | http://www.sciencedirect.com/science/article/pii/S2192440623000163 |
| work_keys_str_mv | AT tiborilles largesteppredictorcorrectorinteriorpointmethodforsufficientlinearcomplementarityproblemsbasedonthealgebraicequivalenttransformation AT petrarenatarigo largesteppredictorcorrectorinteriorpointmethodforsufficientlinearcomplementarityproblemsbasedonthealgebraicequivalenttransformation AT rolandtorok largesteppredictorcorrectorinteriorpointmethodforsufficientlinearcomplementarityproblemsbasedonthealgebraicequivalenttransformation |