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

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.

Citation

Manuscript, Delft University of Technology, Delft, The Netherlands. Shanghai University, Shanghai, China.

Article

Download

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