Optimization Online


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

Y.Q. Bai (yqbai***at***staff.shu.edu.cn)
G.Q. Wang (guoq_wang***at***hotmail.com)
C. Roos (c.roos***at***ewi.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

  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