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 is $O(\sqrt{N}\log ({N}/{\varepsilon})$, where $N$ stands for the number of second-order cones in the problem formulation and $\varepsilon$ is the desired accuracy. The bound coincides with the currently best iteration bound for second-order conic optimization. We also generalize an infeasible interior-point method for linear optimization [C. Roos, A full-Newton step ${O}(n)$ infeasible interior-point algorithm for linear optimization, 16(4) 2006, 1110-1136.] to second-order conic optimization. As usual for infeasible interior-point methods the starting point depends on a positive number $\zeta$. The algorithm either finds an $\varepsilon$-solution in at most $O\br{N\log({N}/{\varepsilon}})$ steps or determines that the primal-dual problem pair has no optimal solution with vanishing duality gap satisfying a condition in terms of $\zeta$.
Citation
Manuscript. Delft University of Technology. P.O. Box 5031, 2600 GA Delft, The Netherlands. May 2008.
Article
View Full Nesterov-Todd Step Primal-Dual Interior-Point Methods for Second-Order Cone Optimization