53. Simplified Analysis of Kernel-Based Interior-Point Methods for Linear Complementarity Problems
Invited abstract in session WF-3: Interior-Point Methods for Linear Complementarity Problems II, stream Advances in theory and practice of interior-point methods.
Wednesday, 16:45 - 18:15Room: C 104
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
- Complementarity and variational problems
- Complexity and efficiency of optimization algorithms
- Linear and nonlinear optimization
Status: accepted
Back to the list of papers