A new wide-neighborhood predictor-corrector interior-point method for semidefinite optimization

In this paper, we present a new predictor-corrector interior-point algorithm based on a wide neighborhood for semidefinite optimization. The proposed algorithm is a Mizuno-Todd-Ye predictor-corrector type and uses the Nesterov-Todd (NT) search direction in predictor step and a commutative class of search directions involving Helmberg-Kojima-Monteiro and NT directions in corrector step. We show that the proposed algorithm at every both predictor and corrector steps reduces the duality gap. The method enjoys the iteration complexity of O (root n kappa L-infinity), which matching to the currently best known iteration bound for wide neighborhood algorithms. Numerical results also confirm the algorithm is reliable and promising.

Automated summary

This paper presents a new predictor-corrector interior-point algorithm based on a wide neighborhood for semidefinite optimization. The algorithm reduces the duality gap at every predictor and corrector steps, with an iteration complexity matching the currently best known iteration bound for wide neighborhood algorithms. Numerical results confirm the reliability and promise of the proposed algorithm.