A New Second-Order Infeasible Primal-Dual Path-Following Algorithm for Symmetric Optimization. (2nd April 2016)

• Record Type: Journal Article
• Authors: Yang, Ximei; Zhang, Yinkui; Liu, Hongwei; Shen, Peiping
• Is Part Of: Numerical functional analysis and optimization. Volume 37:Number 4(2016)
• Page Start: 499
• Page End: 519
• Publication Date: 2016-04-02
• Subjects: Euclidean Jordan algebra -- infeasible -- path-following algorithm -- second-order corrector -- symmetric cone optimization; 90C05 -- 90C51; Functional analysis -- Periodicals; Numerical analysis -- Periodicals; Mathematical optimization -- Periodicals; Numerical Analysis, Computer-Assisted; 515.705
• DOI: 10.1080/01630563.2016.1138127
• Languages: English
• ISSNs: 0163-0563

Abstract

ABSTRACT: In this article, we propose a new second-order infeasible primal-dual path-following algorithm for symmetric cone optimization. The algorithm further improves the complexity bound of a wide infeasible primal-dual path-following algorithm. The theory of Euclidean Jordan algebras is used to carry out our analysis. The convergence is shown for a commutative class of search directions. In particular, the complexity bound is 𝒪( r 5/4 log ϵ −1 ) for the Nesterov-Todd direction, and 𝒪( r 7/4 log ϵ −1 ) for the xs and sx directions, where r is the rank of the associated Euclidean Jordan algebra and ϵ is the required precision. If the starting point is strictly feasible, then the corresponding bounds can be reduced by a factor of r 3/4 . Some preliminary numerical results are provided as well.