A wide neighborhood infeasible-interior-point method with arc-search for linear programming

详细信息    查看全文

• 作者：Ximei Yang ; Yinkui Zhang ; Hongwei Liu
• 刊名：Journal of Applied Mathematics and Computing
• 出版年：2016
• 出版时间：June 2016
• 年：2016
• 卷：51
• 期：1-2
• 页码：209-225
• 全文大小：465 KB
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Computational Mathematics and Numerical Analysis
  Applied Mathematics and Computational Methods of Engineering
  Theory of Computation
  Mathematics of Computing
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1865-2085
• 卷排序：51

文摘

In this paper, we propose an arc-search infeasible-interior-point method for linear programming. The proposed algorithm is based on a wide neighborhood of the central path and searches the optimizers along the ellipses that approximate the entire the central path. We also establish polynomial complexity of the proposed algorithm. Finally, numerical experiments show that the proposed algorithm is efficient and reliable.KeywordsLinear programmingInfeasible-interior-point methodArc-searchWide neighborhoodComplexity