Abstract: In order to overcome the deficiency that initial points should be strictly feasible in interior point methods, a primal-dual infeasible-interior-point algorithm for the second-order cone programming(SOCP) is presented. Based on the optimality conditions and complementarity conditions for SOCP, a new merit function is defined in the algorithm. The smaller the value of the merit function is, the closer the iteration point is to the solution. Without the strict feasibility of the initial points and iteration points, the algorithm is shown to possess both polynomial-time complexity and Q-linear convergence.

Key words: sencond-order cone programming, infeasible-interior-point algorithm, Q-linear convergence, polynomial-time complexity