Two new predictor-corrector algorithms for second-order cone programming

• Published in: Applied mathematics and mechanics 2011-04, Vol.32 (4), p.521-532
• Main Author: 曾友芳 白延琴 简金宝 唐春明
• Format: Article
• Language: English
• Subjects: Algorithms; Applications of Mathematics; Categories; Classical Mechanics; Complexity; Convergence; Fluid- and Aerodynamics; Iterative methods; Mathematical Modeling and Industrial Mathematics; Mathematical models; Mathematics; Mathematics and Statistics; Partial Differential Equations; Predictor-corrector methods; Programming
• ISSN: 0253-4827; 1573-2754
• DOI: 10.1007/s10483-011-1435-x

Based on the ideas of infeasible interior-point methods and predictor-corrector algorithms, two interior-point predictor-corrector algorithms for the second-order cone programming （SOCP） are presented. The two algorithms use the Newton direction and the Euler direction as the predictor directions, respectively. The corrector directions belong to the category of the Alizadeh-Haeberly-Overton （AHO） directions. These algorithms are suitable to the cases of feasible and infeasible interior iterative points. A simpler neighborhood of the central path for the SOCP is proposed, which is the pivotal difference from other interior-point predictor-corrector algorithms. Under some assumptions, the algorithms possess the global, linear, and quadratic convergence. The complexity bound O（rln（εo/ε）） is obtained, where r denotes the number of the second-order cones in the SOCP problem. The numerical results show that the proposed algorithms are effective.