A Mizuno-Todd-Ye predictor-corrector infeasible-interior-point method for linear programming over symmetric cones

摘要

We propose a Mizuno-Todd-Ye predictor-corrector infeasible-interior-point method for linear programming over symmetric cones by using a wide neighborhood. In the corrector step, we adopt a special strategy, which can ensure the existence of a step size to keep every iteration in the given small neighborhood. By using an elegant analysis, we obtain the iteration bounds for a commutative class of directions. In particular, the iteration bound is for the Nesterov-Todd search direction, and for the xs and sx search direction. To our knowledge, the obtained iteration bounds match the currently best known iteration bounds for infeasible-interior-point method. Some preliminary numerical results are provided as well.