A primal-dual interior-point algorithm for second-order cone optimization with full Nesterov-Todd step

作者：Wang G Q^*; Bai Y Q

来源：Applied Mathematics and Computation, 2009, 215(3): 1047-1061.

DOI：10.1016/j.amc.2009.06.034

• Second-order cone optimization
• Interior-point algorithm
• Small-update method
• Iteration bound

In this paper we propose a primal-dual path-following interior-point algorithm for second-order cone optimization. The algorithm is based on a new technique for finding the search directions and the strategy of the central path. At each iteration, we use only full Nesterov-Todd step. Moreover, we derive the currently best known iteration bound for the algorithm with small-update method, namely, O(root N log N/epsilon), where N denotes the number of second-order cones in the problem formulation and epsilon the desired accuracy.

• 出版日期2009-10
• 单位上海工程技术大学