A New Ai–Zhang Type Interior Point Algorithm for Sufficient Linear Complementarity Problems

Marianna E.-Nagy () and Anita Varga ()
Additional contact information
Marianna E.-Nagy: Corvinus University of Budapest
Anita Varga: Budapest University of Technology and Economics
Authors registered in the RePEc Author Service: Marianna Eisenberg-Nagy

Journal of Optimization Theory and Applications, 2024, vol. 202, issue 1, No 5, 76-107

Abstract: Abstract In this paper, we propose a new long-step interior point method for solving sufficient linear complementarity problems. The new algorithm combines two important approaches from the literature: the main ideas of the long-step interior point algorithm introduced by Ai and Zhang and the algebraic equivalent transformation technique proposed by Darvay. Similar to the method of Ai and Zhang, our algorithm also works in a wide neighborhood of the central path and has the best known iteration complexity of short-step variants. However, due to the properties of the applied transforming function in Darvay’s technique, the wide neighborhood definition in the analysis depends on the value of the handicap. We implemented not only the theoretical algorithm but a greedy variant of the new method (working in a neighborhood independent of the handicap) in MATLAB and tested its efficiency on both sufficient and non-sufficient problem instances. In addition to presenting our numerical results, we also make some interesting observations regarding the analysis of Ai–Zhang type methods.

Keywords: Mathematical programming; Linear complementarity problems; Interior point algorithms; Algebraic equivalent transformation technique (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10957-022-02121-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
Working Paper: A new Ai-Zhang type interior point algorithm for sufficient linear complementarity problems (2022)
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:202:y:2024:i:1:d:10.1007_s10957-022-02121-z

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-022-02121-z

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().