An arc-search O(nL) infeasible-interior-point algorithm for linear programming

作者：Yang Yaguang; Yamashita Makoto^*

来源：Optimization Letters, 2018, 12(4): 781-798.

DOI：10.1007/s11590-017-1142-9

• Polynomial algorithm
• Infeasible-interior-point method
• Linear programming

Arc-search interior-point methods have been proposed to capture the curvature of the central path using an approximation based on ellipse. Yang et al. (J Appl Math Comput 51(1-2):209-225, 2016) proved that an arc-search algorithm has the computational order of . In this paper, we propose an arc-search infeasible-interior-point algorithms and discuss its convergence analysis. We improve the polynomial bound from to , which is at least as good as the best existing bound for infeasible-interior-point algorithms for linear programming. Numerical results indicate that the proposed method solved LP instances faster than the existing method.

• 出版日期2018-6