A NEW O(√nL) ITERATION LARGE-UPDATE PRIMAL-DUAL INTERIOR-POINT METHOD FOR SECOND-ORDER CONE PROGRAMMING

In this article, we extend the Ai-Zhang direction for solving LCP to the class of second-order cone programming. Each iterate always follows the usual wide neighborhood N-infinity(-), not necessarily staying within it, but must stay within the wider neighborhood N (beta, tau). In addition, we decompose the classical Newton direction into two separate parts according to the positive and negative parts. We show that the algorithm has O(root nL) iteration complexity bound, where n is the dimension of the problem and L = (X-0)(T) S-0/epsilon with epsilon the required precision and (X-0, S-0) the initial interior solution. To the best of our knowledge, this is the first large-neighborhood path-following interior point method (IPMs) with the same complexity as small neighborhood path-following IPMs for second-order cone programming. It is the best result in regard to the iteration complexity bound in the context of the large-update path-following method for second-order cone programming.