Quadratic Convergence of a Non-interior Continuation Method for Second-order Cone Programming

摘要

Based on the Chen-Harker-Kanzow-Smale (CHKS) smoothing function, a non-interior continuation method is proposed for solving the second-order cone programming(SOCP). Our algorithm is shown to possess the following good properties: (i) if A has full row rank, the algorithm is well-defined and any accumulation point of the iteration sequence is a solution of the SOCP; (ii) unlike interior point methods, our algorithm does not have restrictions regarding its starting point; (iii) the algorithm only needs to solve one linear system of equations and to perform one line search at each iteration; (iv) in absence of uniform nonsingularity, our algorithm is globally and locally quadratically convergent.