A Full Nesterov–Todd Step Infeasible Interior-Point Method for Second-Order Cone Optimization

• DOI: 10.1007/s10957-013-0278-8
• Publication Date: 2013-02-14T16:28:14Z
• Authors: M. Zangiabadi; G. Gu; C. Roos
• Keywords: Interior point method; Conic optimization; Conic section; Duality (order theory); Cone (formal languages); Theory of computation; Second-order cone programming

After a brief introduction to Jordan algebras, we present a primal–dual interior-point algorithm for second-order conic optimization that uses full Nesterov–Todd steps; no line searches are required. The number of iterations of the algorithm coincides with the currently best iteration bound for second-order conic optimization. We also generalize an infeasible interior-point method for linear optimization to second-order conic optimization. As usual for infeasible interior-point methods, the starting point depends on a positive number. The algorithm either finds a solution in a finite number of iterations or determines that the primal–dual problem pair has no optimal solution with vanishing duality gap.