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

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

0.00 Avg rating0 Votes
Article ID: iaor20061405
Country: Germany
Volume: 4
Issue: 4
Start Page Number: 409
End Page Number: 433
Publication Date: Dec 2005
Journal: Journal of Mathematical Modelling and Algorithms
Authors: , ,
Keywords: computational analysis
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 O(qn)log(n/ε) and O(q2√(n))log(n/ε), respectively, which are as good as those in the linear case.

Reviews

Required fields are marked *. Your email address will not be published.