We present a weighted-path-following interior-point algorithm for solving second-order cone optimization. This algorithm starts from an initial point which is not on the central path. It generates iterates that simultaneously get closer to optimality and closer to centrality. At each iteration, we use only full Nesterov-Todd step; no line searches are required. We derive the complexity bound of the algorithm with small-update method, namely, O (√ NlogN e ) , where N denotes the number of second order cones in the problem formulation and e the desired accuracy. This bound is the currently best known iteration bound for second-order cone optimization.
Tang, Jingyong; Dong, Li; Fang, Liang; and Zhou, Jinchuan
"A Weighted-Path-Following Interior-Point Algorithm for Second-Order Cone Optimization,"
Applied Mathematics & Information Sciences: Vol. 09
, Article 48.
Available at: https://dc.naturalspublishing.com/amis/vol09/iss2/48