Primal-Dual Interior-Point Algorithms for Semidefinite Optimization Based on a Simple Kernel Function |
| |
Authors: | G?Q?Wang Email author" target="_blank">Y?Q?BaiEmail author C?Roos |
| |
Institution: | (1) Department of Mathematics, College of Science, Shanghai University, Shanghai, 200436;(2) Faculty of Electrical Engineering, Mathematics and Computer Science, Delft University of Technology, P.O. Box 5031, 2600 GA Delft, The Netherlands |
| |
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 proximities for linear optimization (LO) problems. They 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 presented at the Proceedings of Industrial Symposium and Optimization Day, Australia, November 2002; the function is not self-regular. We derive the complexity analysis for algorithms based on this
kernel function, both with large- and small-updates. The complexity bounds are
and
, respectively, which are as good as those in the linear case.
Mathematics Subject Classifications (2000) 90C22, 90C31. |
| |
Keywords: | semidefinite optimization interior-point methods primal-dual methods large- and small-update methods polynomial complexity |
本文献已被 SpringerLink 等数据库收录! |
|