Polynomial convergence of Mehrotra-type prediction–corrector infeasible-IPM for symmetric optimization based on the commutative class directions

摘要

In this paper, we establish polynomial convergence of Mehrotra-type prediction corrector infeasible-interior-point method for symmetric optimization using a wide neighborhood of the central path. In order to show that the convergence of our algorithm for the commutative class of search directions, we prove the important inequality ‖x∘y‖1⩽3‖x‖F‖y‖F, where a mapping ‖·‖1 is defined by ‖x‖1=∑i=1r|λi| with the spectral decomposition x=∑i=1rλici. In particular, the complexity bound is O(r2logε-1) for the Nesterov–Todd search direction, and O(r5/2logε-1) for the xs and sx search direction. We provide some preliminary numerical results as well.