- 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/2004Entry Accepted: 06/03/2004Entry Last Modified: 06/03/2004Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.