Primal-dual interior-point algorithms for semidefinite optimization based on a simple kernel function

GQ Wang, Y Bai, C Roos

    Research output: Contribution to journalArticleScientificpeer-review

    47 Citations (Scopus)

    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. Keywords semidefinite optimization - interior-point methods - primal-dual methods - large- and small-update methods - polynomial complexity Mathematics Subject Classifications (2000) 90C22, 90C31.
    Original languageUndefined/Unknown
    Pages (from-to)409-433
    Number of pages25
    JournalJournal of Mathematical Modelling and Algorithms
    Volume4
    Issue number4
    DOIs
    Publication statusPublished - 2005

    Keywords

    • academic journal papers
    • Vakpubl., Overig wet. > 3 pag

    Cite this