Continuous Optimization

Polynomial Convergence of Primal-Dual Path-Following Algorithms for Symmetric Cone Programming Based on Wide Neighborhoods and a New Class of Directions

Expand
  • 1 School of Mathematics and Statistics, Henan University of Science and Technology, Luoyang 471023, Henan, China

Online published: 2017-09-30

Abstract

This paper presents a class of primal-dual path-following interior-point algorithms for symmetric cone programming (SCP) based on wide neighborhoods and new directions with a parameter θ. When the parameter θ = 1, the direction is exactly the classical Newton direction. When the parameter θ is independent of the rank of the associated Euclidean Jordan algebra, the algorithm terminates in at most O(κr log ε-1)  iterations, which coincides with the best known iteration bound for the classical wide neighborhood algorithms. When the parameterθ =√n/βτ and Nesterov–Todd search direction is used, the algorithm has O (√r log ε−1 )iteration complexity, the best iteration complexity obtained so far by any interior-point method for solving SCP. To our knowledge, this is the first time that a class of interior-point algorithms including the classical wide neighborhood path-following algorithm is proposed and analyzed over symmetric cone.

 

Cite this article

Chang-He Liu · Yuan-Yuan Huang ·You-Lin Shang . Polynomial Convergence of Primal-Dual Path-Following Algorithms for Symmetric Cone Programming Based on Wide Neighborhoods and a New Class of Directions[J]. Journal of the Operations Research Society of China, 2017 , 5(3) : 333 -346 . DOI: 10.1007/s40305-017-0172-4

Options
Outlines

/