A Mizuno-Todd-Ye predictor-corrector infeasible-interior-point method for linear programming over symmetric cones

详细信息    查看全文

• 作者：Ximei Yang ; Yinkui Zhang ; Hongwei Liu ; Yonggang Pei
• 刊名：Numerical Algorithms
• 出版年：2016
• 出版时间：August 2016
• 年：2016
• 卷：72
• 期：4
• 页码：915-936
• 全文大小：355 KB
• 刊物类别：Computer Science
• 刊物主题：Numeric Computing
  Algorithms
  Mathematics
  Algebra
  Theory of Computation
  
• 出版者：Springer U.S.
• ISSN：1572-9265
• 卷排序：72

文摘

We propose a Mizuno–Todd–Ye predictor-corrector infeasible-interior-point method for linear programming over symmetric cones by using a wide neighborhood. In the corrector step, we adopt a special strategy, which can ensure the existence of a step size to keep every iteration in the given small neighborhood. By using an elegant analysis, we obtain the iteration bounds for a commutative class of directions. In particular, the iteration bound is \(\mathcal {O}(r\log \varepsilon ^{-1})\) for the Nesterov-Todd search direction, and \(\mathcal {O}(r^{3/2}\log \varepsilon ^{-1})\) for the xs and sx search direction. To our knowledge, the obtained iteration bounds match the currently best known iteration bounds for infeasible-interior-point method. Some preliminary numerical results are provided as well.KeywordsJordan algebraSymmetric conesLinear programmingInfeasible-interior-point methodsIteration bound