- | ||||
|
![]()
|
Primal-Dual Interior-Point Algorithms for Semidefinite Optimization Based on a Simple Kernel Function
G. Q. Wang (guoq_wang 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 Modify/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 | |
![]() |