Polynomiality of an inexact infeasible interior point algorithm for semidefinite programming
Zhou, G. Toh, K.-C.
Zhou, G.
Citations
Altmetric:
Alternative Title
Abstract
In this paper we present a primal-dual inexact infeasible interior-point algorithm for semidefinite programming problems (SDP). This algorithm allows the use of search directions that are calculated from the defining linear system with only moderate accuracy, and does not require feasibility to be maintained even if the initial iterate happened to be a feasible solution of the problem. Under a mild assumption on the inexactness, we show that the algorithm can find an ε-approximate solution of an SDP in O(n 2 ln(1/ε)) iterations. This bound of our algorithm is the same as that of the exact infeasible interior point algorithms proposed by Y. Zhang. © Springer-Verlag 2003.
Keywords
Inexact search direction, Infeasible interior point method, Polynomial complexity, Primal-dual, Semidefinite programming
Source Title
Mathematical Programming
Publisher
Series/Report No.
Collections
Rights
Date
2004-03
DOI
10.1007/s10107-003-0431-5
Type
Article