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

摘要

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.View full textDownload full textKeywordssemidefinite optimization, predictor-corrector algorithms, Mehrotra-type algorithm, polynomial complexityRelated var addthis_config = { ui_cobrand: "Taylor & Francis Online", services_compact: "citeulike,netvibes,twitter,technorati,delicious,linkedin,facebook,stumbleupon,digg,google,more", pubid: "ra-4dff56cd6bb1830b" }; Add to shortlist Link Permalink http://dx.doi.org/10.1080/10556780802571392