A primal–dual predictor–corrector interior-point method for symmetric cone programming with O(√r log ϵ⁻¹) iteration complexity

ABSTRACT

In this paper,we propose a new predictor–corrector interior-point method for symmetric cone programming. This algorithm is based on a wide neighbourhood and the Nesterov–Todd direction. We prove that, besides the predictor steps, each corrector step also reduces the duality gap by a rate of $1-\left(1/\text{O}\right(\sqrt{r}\left)\right)$, where r is the rank of the associated Euclidean Jordan algebras. In particular, the complexity bound is $\text{O}\left(\sqrt{r}\log {\epsilon }^{-1}\right)$, where $\epsilon >0$ is a given tolerance. To our knowledge, this is the best complexity result obtained so far for interior-point methods with a wide neighbourhood over symmetric cones. The numerical results show that the proposed algorithm is effective.

KEYWORDS:

• Euclidean Jordan algebra
• Symmetric cone
• interior-point methods
• predictor–corrector algorithm
• wide neighbourhood

2010 AMS Subject Classifications:

• 90C05
• 90C51

Acknowledgements

The research of the first author was supported by a grant from IPM (No. 95900076) which is acknowledged. The second and third authors would like to thank Shahrekord University for financial support. The second and third authors were also partially supported by the Center of Excellence for Mathematics, University of Shahrekord, Shahrekord, Iran. The second and third authors wish to thank the York University, Professor Michael Chen and his group for hospitality during their recent sabbatical.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

The research of the first author was in part supported by a grant from IPM (No. 95900076). The research of the second and third authors were supported by a grant from Shahrekord University (Nos. 94GRD1M1034, 94GRD1M2003).