A second-order Mehrotra-type predictor-corrector algorithm with a new wide neighbourhood for semi-definite programming

Abstract

In this paper, we present a new second-order Mehrotra-type predictor–corrector algorithm for semi-definite programming (SDP). The proposed algorithm is based on a new wide neighbourhood. We are particularly concerned with an important inequality. Based on the inequality, the convergence is shown for a specific class of search directions. In particular, the complexity bound is O(√nlogϵ⁻¹) for the Nesterov–Todd search direction and O(n logϵ⁻¹) for the Helmberg-Kojima-Monteiro search direction. The derived complexity bounds coincide with the currently best known theoretical complexity bounds obtained so far for SDP. We provide some preliminary numerical results as well.

Keywords:

• semi-definite programming
• Mehrotra-type predictor–corrector algorithm
• Schatten 1-norm
• wide neighbourhood
• complexity bound

2000 AMS Subject Classifications:

• 90C22
• 90C51

Acknowledgements

We are grateful to the anonymous referees and editor for their useful comments that help us improve the presentation of this paper. We would also like to thank the supports of National Natural Science Foundation of China (NNSFC) under grant nos. 61072144 and 61179040.