An O(r(cond(G))1/4log¼ϵ−1) iteration predictor–corrector interior-point method with a new one-norm neighbourhood for symmetric cone optimization. (2nd December 2022)

• Record Type: Journal Article
• Authors: Shahraki, M. Sayadi; Mansouri, H.
• Is Part Of: Optimization. Volume 71:Number 12(2022)
• Page Start: 3419
• Page End: 3437
• Publication Date: 2022-12-02
• Subjects: Interior-point method -- complexity bound -- symmetric cone optimization -- Euclidean Jordan algebra -- one-norm; 90C51 -- 90C33; Mathematical optimization -- Periodicals; 519.7
• DOI: 10.1080/02331934.2021.1899177
• Languages: English
• ISSNs: 0233-1934

Abstract

Abstract : In this paper, we propose a predictor–corrector interior-point method for symmetric cone optimization. The proposed algorithm is based on a new one-norm neighbourhood, which is an even wider neighbourhood than a given negative infinity neighbourhood. The convergence is shown for a commutative class of search directions, which includes the Nesterov–Todd direction and the xs and sx directions. We show that the algorithm has O ( r ( c o n d ( G ) ) 1 / 4 log ⁡ ϵ − 1 ) iteration complexity bound which is better than that of the usual wide neighbourhood algorithm O ( r c o n d ( G ) log ⁡ ϵ − 1 ) . To our knowledge, these are the best complexity results obtained so far for the solution of symmetric cone optimization. We prove that beside the predictor steps, each corrector step also reduces the duality gap by a rate of 1 − 1 O ( r ) . Finally, numerical experiments show that the proposed algorithm is efficient and reliable.