A primal-dual interior-point algorithm for second-order cone optimization with full Nesterov–Todd step

摘要

In this paper we propose a primal-dual path-following interior-point algorithm for second-order cone optimization. The algorithm is based on a new technique for finding the search directions and the strategy of the central path. At each iteration, we use only full Nesterov–Todd step. Moreover, we derive the currently best known iteration bound for the algorithm with small-update method, namely, ONlogNε, where N denotes the number of second-order cones in the problem formulation and ε the desired accuracy.