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/2008
Entry Accepted: 07/26/2008
Entry Last Modified: 09/25/2008

Modify/Update this entry