- Full Nesterov-Todd Step Primal-Dual Interior-Point Methods for Second-Order Cone Optimization M. Zangiabadi (M.Zangiabaditudelft.nl) G. Gu (G.Gutudelft.nl) C. Roos (C.Roostudelft.nl) Abstract: 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$. Keywords: Second-Order Cone Optimization, primal-dual method, feasible and infeasible interior-point method, polynomial complexity Category 1: Convex and Nonsmooth Optimization Citation: Manuscript. Delft University of Technology. P.O. Box 5031, 2600 GA Delft, The Netherlands. May 2008. Download: [Postscript][PDF]Entry Submitted: 07/26/2008Entry Accepted: 07/26/2008Entry Last Modified: 09/25/2008Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.