A New Second-Order Infeasible Primal-Dual Path-Following Algorithm for Symmetric Optimization. (2nd April 2016) - Yang, Ximei; Zhang, Yinkui; Liu, Hongwei; Shen, Peiping
ABSTRACT: In this article, we propose a new second-order infeasible primal-dual path-following algorithm for symmetric cone optimization. The algorithm further improves the complexity bound of a wide infeasible primal-dual path-following algorithm. The theory of Euclidean Jordan algebras is used to carry out our analysis. The convergence is shown for a commutative class of search directions. In particular, the complexity bound is 𝒪( r 5/4 log ϵ −1 ) for the Nesterov-Todd direction, and 𝒪( r 7/4 log ϵ −1 ) for the xs and sx directions, where r is the rank of the associated Euclidean Jordan algebra and ϵ is the required precision. If the starting point is strictly feasible, then the corresponding bounds can be reduced by a factor of r 3/4 . Some preliminary numerical results are provided as well.