  


PrimalDual InteriorPoint Algorithms for Semidefinite Optimization Based on a Simple Kernel Function
G. Q. Wang (guoq_wanghotmail.com) Abstract: Interiorpoint methods (IPMs) for semidefinite optimization (SDO) have been studied intensively, due to their polynomial complexity and practical efficiency. Recently, J.Peng et al. introduced socalled selfregular kernel (and barrier) functions and designed primaldual interiorpoint algorithms based on selfregular proximity for linear optimization (LO) problems. They have also extended the approach for LO to SDO. In this paper we present a primaldual interiorpoint 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 selfregular due to its growth term increasing linearly. We derive the complexity analysis for algorithms with large and smallupdate 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, interiorpoint methods, primaldual methods, large and small update methods, complexity bounds Category 1: Linear, Cone and Semidefinite Programming Category 2: Linear, Cone and Semidefinite Programming (Semidefinite 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  