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 - _∞, not necessarily staying within it, but must stay within the wider neighborhood N(β,τ). 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(√nL) iteration complexity bound, where n is the dimension of the problem and L = (x oT S o/ε with 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.