A New Second-Order Infeasible Primal-Dual Path-Following Algorithm for Symmetric Optimization

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/4log ϵ⁻¹) for the Nesterov-Todd direction, and 𝒪(r^7/4log ϵ⁻¹) 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.

KEYWORDS:

• Euclidean Jordan algebra
• infeasible
• path-following algorithm
• second-order corrector
• symmetric cone optimization

MATHEMATICS SUBJECT CLASSIFICATION:

• 90C05
• 90C51

Acknowledgments

We are grateful to the anonymous referees and editor for their useful comments that help us improve the presentation of this article.