Optimization Online


Primal-Dual Interior-Point Algorithms for Semidefinite Optimization Based on a Simple Kernel Function

G. Q. Wang (guoq_wang***at***hotmail.com)
Y. Q. Bai (y.bai***at***ewi.tudelft.nl)
C. Roos (c.roos***at***ewi.tudelft.nl)

Abstract: Interior-point methods (IPMs) for semidefinite optimization (SDO) have been studied intensively, due to their polynomial complexity and practical efficiency. Recently, J.Peng et al. introduced so-called self-regular kernel (and barrier) functions and designed primal-dual interior-point algorithms based on self-regular proximity for linear optimization (LO) problems. They have also extended the approach for LO to SDO. In this paper we present a primal-dual interior-point algorithm for SDO problems based on a simple kernel function which was first introduced by Bai et al. The kernel function in this paper is not self-regular due to its growth term increasing linearly. We derive the complexity analysis for algorithms with large- and small-update methods. The complexity bounds are $O(qn)\log\frac{n}{\epsilon}$ and $O( q^2\sqrt{n})\log\frac{n}{\epsilon}$, respectively, which are as good as those in linear case.

Keywords: semidefinite optimization, interior-point methods, primal-dual methods, large- and small- update methods, complexity bounds

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: Manuscript, Delft University of Technology, Delft, The Netherlands. Shanghai University, Shanghai, China.

Download: [Postscript][PDF]

Entry Submitted: 06/03/2004
Entry Accepted: 06/03/2004
Entry Last Modified: 06/03/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