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

G. Q. Wang (guoq_wanghotmail.com)
Y. Q. Bai (y.baiewi.tudelft.nl)
C. Roos (c.roosewi.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