On the complexity analysis of a Mehrotra-type primal–dual feasible algorithm for semidefinite optimization

Abstract

It has been shown in various papers that most interior-point algorithms and their analysis can be generalized to semidefinite optimization. This paper presents an extension of the recent variant of Mehrotra's predictor–corrector algorithm that was proposed by Salahi et al. [M. Salahi, J. Peng, and T. Terlaky, On Mehrotra-type predictor–corrector algorithms, SIAM J. Optim. 18 (2007), pp. 1377–1397] for linear optimization (LO) problems. Based on the NT [Y.E. Nesterov and M.J. Todd, Self-scaled barriers and interior-point methods for convex programming, Math. Oper. Res. 22 (1997), pp. 1–42] directions which are Newton search directions, we show that the iteration-complexity bound of the algorithm is of the same order as that of the corresponding algorithm for LO.

Keywords:

• semidefinite optimization
• predictor–corrector algorithms
• Mehrotra-type algorithm
• polynomial complexity

Acknowledgements

The work of this author was partially supported by the NSERC Grant DG:5-48923, the Canada Research Chair Program, and MITACS. The authors are grateful to the referees for their helpful comments.