A New Primal-Dual Interior-Point Algorithm for Second-Order Cone Optimization

Y.Q. Bai (yqbaistaff.shu.edu.cn)
G.Q. Wang (guoq_wanghotmail.com)
C. Roos (c.roosewi.tudelft.nl)

Abstract: We present a primal-dual interior-point algorithm for second-order conic optimization problems based on a specific class of kernel functions. This class has been investigated earlier for the case of linear optimization problems. In this paper we derive the complexity bounds $O(\sqrt{N})(\log N)\log\frac{N}{\epsilon})$ for large- and $O(\sqrt{N})\log\frac{N}{\epsilon}$ for small- update methods, respectively. Here $N$ denotes the number of second order cones in the problem formulation.

Keywords: second-order conic optimization, interior-point methods, primal-dual method, large- and small-update methods, polynomial complexity

Category 1: Linear, Cone and Semidefinite Programming (Second-Order Cone Programming )

Category 2: Linear, Cone and Semidefinite Programming

Citation: Department of Mathematics, College Science, Shanghai University, Shanghai, 200436, China. Faculty of Electrical Engineering, Mathematics and Computer Science, Delft University of Technology, P.O. Box 5031, 2600 GA Delft, The Netherlands.

Download: [PDF]

Entry Submitted: 11/15/2004
Entry Accepted: 11/16/2004
Entry Last Modified: 11/15/2004

Modify/Update this entry