An arc-search infeasible-interior-point method for symmetric optimization in a wide neighborhood of the central path

详细信息    查看全文

• 作者：Ximei Yang ; Hongwei Liu ; Yinkui Zhang
• 关键词：Euclidean Jordan algebra ; Symmetric optimization ; Arc ; search ; Infeasible ; interior ; point method ; Polynomial complexity
• 刊名：Optimization Letters
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：11
• 期：1
• 页码：135-152
• 全文大小：
• 刊物类别：Mathematics and Statistics
• 刊物主题：Optimization; Operation Research/Decision Theory; Computational Intelligence; Numerical and Computational Physics, Simulation;
• 出版者：Springer Berlin Heidelberg
• ISSN：1862-4480
• 卷排序：11

文摘

In this paper, we propose a new arc-search infeasible-interior-point method for symmetric optimization using a wide neighborhood of the central path. The proposed algorithm searches for optimizers along the ellipses that approximate the central path. The convergence is shown for a commutative class of search directions, which includes the Nesterov–Todd direction and the xs and sx directions. The complexity bound is \(\mathcal {O}(r^{5/4}\log \varepsilon ^{-1})\) for the Nesterov–Todd direction, and \(\mathcal {O}(r^{7/4}\log \varepsilon ^{-1})\) for the xs and sx directions, where r is the rank of the associated Euclidean Jordan algebra and \(\varepsilon \) is the required precision. The obtained complexity bounds coincide with the currently best known theoretical complexity bounds for the short step path-following algorithm. Some limited encouraging computational results are reported.