A Predictor-corrector Infeasible-interior-point Algorithm for Semidefinite Optimization in a Wide Neighborhood

Article type: Research Article

Authors: Kheirfam, Behrouz^*

Affiliations: Department of Applied Mathematics, Azarbaijan Shahid Madani University, Tabriz, I.R. Iran. b.kheirfam@azaruniv.edu

Correspondence: [*] Address for correspondence: Department of Applied Mathematics, Azarbaijan Shahid Madani University, Tabriz, I.R. Iran.

Abstract: In this paper, we propose a predictor-corrector infeasible interior-point algorithm for semidefinite optimization based on the Nesterov-Todd scaling scheme. In each iteration, the algorithm computes the new iterate using a new combination of the predictor and corrector directions. Using the Ai-Zhang’s wide neighborhood for linear complementarity problems, and extended to semidefinite optimization by Li and Terlaky, it is shown that the iteration complexity bound of the algorithm is 𝒪(n54logε−1) , where n is the dimension of the problem and ɛ is the required precision.

Keywords: Semidefinite optimization, wide neighborhood, infeasible-interior-point method, predictor-corrector method, polynomial complexity

DOI: 10.3233/FI-2017-1511

Journal: Fundamenta Informaticae, vol. 152, no. 1, pp. 33-50, 2017