Abstract:

This paper presents a class of primal-dual path-following interior-point algorithms for symmetric cone programming (SCP) based on wide neighborhoods and new directions with a parameter θ. When the parameter θ = 1, the direction is exactly the classical Newton direction. When the parameter θ is independent of the rank of the associated Euclidean Jordan algebra, the algorithm terminates in at most O(κr log ε^-1)  iterations, which coincides with the best known iteration bound for the classical wide neighborhood algorithms. When the parameterθ =√n/βτ and Nesterov–Todd search direction is used, the algorithm has O (√r log ε⁻¹ )iteration complexity, the best iteration complexity obtained so far by any interior-point method for solving SCP. To our knowledge, this is the first time that a class of interior-point algorithms including the classical wide neighborhood path-following algorithm is proposed and analyzed over symmetric cone.