1. bookVolume 15 (2021): Issue 1 (October 2021)
Journal Details
License
Format
Journal
eISSN
2601-5773
First Published
30 Dec 2018
Publication timeframe
2 times per year
Languages
English
access type Open Access

Predictor-Corrector Interior-Point Algorithm for the General Linear Complementarity Problem

Published Online: 09 Dec 2021
Volume & Issue: Volume 15 (2021) - Issue 1 (October 2021)
Page range: 11 - 14
Journal Details
License
Format
Journal
eISSN
2601-5773
First Published
30 Dec 2018
Publication timeframe
2 times per year
Languages
English
Abstract

We study a predictor-corrector interior-point algorithm for solving general linear complementarity problems from the implementation point of view. We analyze the method proposed by Illés, Nagy and Terlaky [1] that extends the algorithm published by Potra and Liu [2] to general linear complementarity problems. A new method for determining the step size of the corrector direction is presented. Using the code implemented in the C++ programming language, we can solve large-scale problems based on sufficient matrices.

Keywords

[1] Illés T., Nagy M., Terlaky T.: Polynomial Interior Point Algorithms for General Linear Complementarity Problems. Algorithmic Operations Research, 5/1. (2010) 1–12. Search in Google Scholar

[2] Potra F. A., Liu X.: Predictor-Corrector Methods for Sufficient Linear Complementarity Problems in a Wide Neighborhood of the Central Path. Optimization Methods and Software, 20/1. (2005) 145–168. https://doi.org/10.1080/1055678051233131803810.1080/10556780512331318038 Search in Google Scholar

[3] Illés T., Nagy M., Terlaky T.: Ep Theorem for Dual Linear Complementarity Problems. Journal of Optimization Theory and Applications, 140. (2009) 233–238. https://doi.org/10.1007/s10957-008-9440-010.1007/s10957-008-9440-0 Search in Google Scholar

[4] Illés T., Nagy M., Terlaky T.: A Polynomial Path-Following Interior Point Algorithm for General Linear Complementarity Problems. Journal of Global Optimization, 47/3. (2010) 329–342. https://doi.org/10.1007/s10898-008-9348-010.1007/s10898-008-9348-0 Search in Google Scholar

[5] Darvay Zs., Füstös Á.: Numerical Results for the General Linear Complementarity Problem. Műszaki Tudományos Közlemények, 9. (2019) 43–46. https://doi.org/10.33894/mtk-2019.11.0710.33894/mtk-2019.11.07 Search in Google Scholar

[6] Kojima M., Megiddo N., Noma T., Yoshise A.: A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems. Springer Verlang, Berlin, 1991.10.1007/3-540-54509-3 Search in Google Scholar

[7] Illés T., Morapitiye S.: Generating Sufficient Matrices. In: Short Papers of the 8th VOCAL Optimization Conference: Advanced Algorithms held in Esztergom, Hungary. (Ed.: Friedler F.) Pázmány Péter Katolikus Egyetem, Budapest, 2018. 56–61. Search in Google Scholar

[8] de Klerk E., E.-Nagy M.: On the Complexity of Computing the Handicap of a Sufficient Matrix. Mathematical Programming, 129. (2011) 383–402. https://doi.org/10.1007/s10107-011-0465-z10.1007/s10107-011-0465-z Search in Google Scholar

[9] Darvay Zs., Illés T., Povh J., Rigó P. R.: Feasible Corrector-Predictor Interior-Point Algorithm for P*(κ)-Linear Complementarity Problems Based on a New Search Direction. SIAM Journal on Optimization, 30/3. (2020) 2628–2658. https://doi.org/10.1137/19M124897210.1137/19M1248972 Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo