Abstract:

In this paper, we present an infeasible-interior-point algorithm, based on a new wide neighborhood for symmetric cone programming. We treat the classical Newton direction as the sum of two other directions, and equip them with different step sizes.We prove the complexity bound of the new algorithm for the Nesterov-Todd (NT) direction, and the xs and sx directions. The complexity bounds obtained here are the same as small neighborhood infeasible-interior-point algorithms over symmetric cones.

Key words: Infeasible-interior-point algorithm , Wide neighborhood, Symmetric cone programming, Euclidean Jordan algebra, Polynomial complexity