Journal of the Operations Research Society of China >
Polynomial Convergence of Primal-Dual Path-Following Algorithms for Symmetric Cone Programming Based on Wide Neighborhoods and a New Class of Directions
Online published: 2017-09-30
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.
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
/
| 〈 |
|
〉 |