A second-order corrector wide neighborhood infeasible interior-point method for linear optimization based on a specific kernel function

Communications in Combinatorics and Optimization

article

Kheirfam, Behrouz¹  Nasrollah, Afsaneh² 

[1] Mathematics;Department of Mathematics, Azarbaijan Shahid Madani University

关键词: Linear optimization;    predictor-corrector methods;    wide neighborhoods;    polynomial complexity;   

DOI  :  10.22049/cco.2021.27044.1185

学科分类：社会科学、人文和艺术（综合）

来源: Azarbaijan Shahide Madani Universit

【 摘 要 】

In this paper, we present a second-order corrector infeasible interior-pointmethod for linear optimization in a large neighborhood of the central path. The innovation of our method is to calculate the predictor directions using a specific kernelfunction instead of the logarithmic barrier function. We decompose the predictor direction induced by the kernel function to two orthogonal directions of the correspondingto the negative and positive component of the right-hand side vector of the centeringequation. The method then considers the new point as a linear combination of thesedirections along with a second-order corrector direction. The convergence analysis ofthe proposed method is investigated and it is proved that the complexity bound isO(n54 log ε−1).

【 授权许可】

CC BY-SA