EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

3923. Simplified Analysis of Kernel-Based Interior-Point Methods for $P_*(\kappa)$- Linear Complementarity Problems

Invited abstract in session MB-38: Interior point methods, stream Conic Optimization: Theory, Algorithms, and Applications.

Monday, 10:30-12:00
Room: 34 (building: 306)

Authors (first author is the speaker)

1. Goran Lesaja
Mathematical Sciences, Georgia Southern University
2. Zsolt Darvay
Department of Mathematics and Computer Science of the Hungarian Line, Babes-Bolyai University
3. Marianna E.-Nagy
Corvinus University of Budapest
4. Petra Renáta Rigó
Corvinus University of Budapest
5. Anita Varga
Corvinus Centre for Operations Research, Corvinus University of Budapest

Abstract

We consider kernel based Interior-point methods (IPMs) for $P_*(\kappa)$-
Linear Complementarity Problems (LCP) that are based on the class of Eligible kernel functions (EKFs). The importance of kernel-based IPMs stems from the fact that the iteration bounds of large-step IPMs is significantly improved for some instances of EKFs. However, the derivation of the iteration bounds for particular EKFs is usually long and quite involved which was the motivation to investigate whether this process can be simplified and under what conditions.

Hence, we introduce additional conditions on the class of EKFs, which are not very restrictive, however, they allow for the significant simplification of the analysis and calculation of iteration bounds. We derive a new simplified scheme to calculate iteration bounds and illustrate it with calculation of iteration bounds of most EKFs with polynomial and exponential barrier terms mentioned in the literature. In all cases we match the complexity obtained using the classical scheme.

Keywords

Status: accepted

Back to the list of papers