Interior-point method for second-order cone programming based on a simple kernel function

Interior-point methods not only are the most effective methods in practice but also have polynomial-time complexity. In this paper we present a primal-dual interior-point algorithm for second-order cone programming problems based on a simple kernel function. We derive the iteration bounds O(nlogε/n) and O(√nlogε/n) for large- and small-update methods, respectively, which are as good as those in the linear programming.

I. Introduction

The second-order cone (SOC) in has the form

$$K:=\{x=(x_{0}, x_{1})\in R\times R^{k-1}:x_{0}-\Vert x_{1}\Vert \geq 0\}$$ , where refers to the Euclidean norm of vectors. In this paper we consider second-order cone programming (SOCP) in standard format $$(P)\ \min\{c^{T}x: Ax=b, x\in K\}$$ , where is the Cartesian product of several second-order cones, i.e., , where for each , and . We partition the vector accordingly , with . Furthermore, and . The dual of problem is $$(D)\ \max\{b^{T}y:A^{T}v+s=c, s\in K\}.$$ Without loss of generality we assume that has full rank: rank .