A Mehrotra-type predictor-corrector infeasible-interior-point method with a new one-norm neighborhood for symmetric optimization

In this paper, we present a Mehrotra-type predictor-corrector infeasible-interior-point method for symmetric optimization. The proposed algorithm is based on a new one-norm neighborhood, which is an even wider neighborhood than a given negative infinity neighborhood. We are emphatically concerned with the relationship between the one-norm of the Jordan product of x and y and its Frobenius-norm. Based on the relationship, the convergence is shown for a commutative class of search directions. In particular, the complexity bound is O(rlogε−1) for the Nesterov-Todd search direction, and O(r3/2logε−1) for the xs and sx search direction, where r is the rank of the associated Euclidean Jordan algebra and ε>0 is a given tolerance. To our knowledge, this is the best complexity result obtained so far for infeasible-interior-point methods with a wide neighborhood over symmetric cones.