A Mehrotra predictor-corrector interior-point algorithm for semidefinite optimization

Authors

MOHAMMAD PIRHAJI
MARYAM ZANGIABADI
HOSSEIN MANSOURI

DOI

10.3906/mat-1511-108

Abstract

This paper proposes a second-order Mehrotra-type predictor-corrector feasible interior-point algorithm for semidefinite optimization problems. In each iteration, the algorithm computes the Newton search directions through a new form of combination of the predictor and corrector directions. Using the Ai-Zhang wide neighborhood for linear complementarity problems, it is shown that the complexity bound of the algorithm is $O(\sqrt{n}\log \varepsilon^{-1})$ for the Nesterov-Todd search direction and $O({n}\log \varepsilon^{-1})$ for the Helmberg-Kojima-Monteiro search directions.

Keywords

Semidefinite optimization, Mehrotra-type predictor-corrector algorithm, polynomial complexity

First Page

168

Last Page

185

Recommended Citation

PIRHAJI, MOHAMMAD; ZANGIABADI, MARYAM; and MANSOURI, HOSSEIN (2017) "A Mehrotra predictor-corrector interior-point algorithm for semidefinite optimization," Turkish Journal of Mathematics: Vol. 41: No. 1, Article 16. https://doi.org/10.3906/mat-1511-108
Available at: https://journals.tubitak.gov.tr/math/vol41/iss1/16