Optimization Online


Full Nesterov-Todd Step Primal-Dual Interior-Point Methods for Second-Order Cone Optimization

M. Zangiabadi (M.Zangiabadi***at***tudelft.nl)
G. Gu (G.Gu***at***tudelft.nl)
C. Roos (C.Roos***at***tudelft.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society