VOCAL 2024
Abstract Submission

103. An Ai-Zhang-type interior-point framework 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:15
Room: C 104

Authors (first author is the speaker)

1. Anita Varga
Corvinus Centre for Operations Research, Corvinus University of Budapest
2. Marianna E.-Nagy
Corvinus University of Budapest

Abstract

Based on their step size, interior point algorithms (IPAs) can be categorized into short- and long-step methods. Despite generally achieving superior theoretical complexity, short-step variants, in practice, are outperformed by long-step IPAs. The first long-step IPA with the same iteration complexity as the short-step variants was proposed by Ai and Zhang in 2005.
To determine new search directions for IPAs, Darvay introduced the algebraically equivalent transformation (AET) technique in 2002. His main concept involved applying an invertible and continuously differentiable transformation function to the central path problem.
This presentation investigates a long-step interior-point framework and a related function class for solving linear complementarity problems (LCPs). The main question we addressed is what type of functions Darvay's technique can be applied with so that an Ai-Zhang type IPA's desired convergence and complexity properties can be proved.
In 2014, Potra proposed a procedure for determining the step lengths in an Ai-Zhang-type IPA for LCPs without prior knowledge of the coefficient matrix's handicap value while preserving the IPA's best known iteration complexity. We generalized this methodology for our framework applying the AET technique. In the talk, we present our numerical results to examine the efficiency of the generalized procedure for different transformation functions.

Keywords

Status: accepted

Back to the list of papers