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

Journal article (2005)

Authors

GQ Wang External organisation
Y. Bai Old - EWI Ch. Optimization Technology
C. Roos Old - EWI Ch. Optimization Technology
Research Group
Old - EWI Ch. Optimization Technology
More Info
expand_more

Published Date

2005

Language

Undefined/Unknown

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Research Group

Old - EWI Ch. Optimization Technology

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.