New interior-point methods for linear optimization problem

Lee, Jongkyu

doi:10.1007/s11590-026-02286-w

New interior-point methods for linear optimization problem

2026-03-01

0

PRE

AI

DOI：10.1007/s11590-026-02286-w

Original

Original request for help

Save

Abstract

En 中文

In this paper, we propose new interior-point methods for solving linear optimization problem based on a generalized class of kernel functions, originally defined in Cho and Cho (J Nonlinear Convex Anal 22:901-917, 2021). New search directions and proximity measures are defined based on these kernel functions. We prove that the iteration complexity is O (root n(logn) log n & micro;(0)/& varepsilon;) for long-step methods and O (root n log n & micro;(0)/& varepsilon;) or short-step methods, where n is the dimension of the problem, where n is the dimension of the problem, & micro;(0) > 0, and & varepsilon;> 0. These represent the theoretically best complexity results for such methods so far. Finally, numerical examples are given to demonstrate the efficiency of the proposed methods. Our method achieved the fewest iteration and shortest running time in 84% of test cases, including 36 randomly generated problems, 25 NETLIB benchmark problems (Koch in Oper Res Lett 32:138-142, 2004), and 41 instances from Bouafia et al. (J Optim Theory Appl 170(2):528-545, 2016).

Keywords:

Interior-point method

Linear optimization

Long- and short-step methods

Kernel function

Complexity

New interior-point methods for linear optimization problem

Abstract

Journal

Organization