Please use this identifier to cite or link to this item: https://doi.org/10.1007/s10107-003-0431-5
Title: Polynomiality of an inexact infeasible interior point algorithm for semidefinite programming
Authors: Zhou, G.
Toh, K.-C. 
Keywords: Inexact search direction
Infeasible interior point method
Polynomial complexity
Primal-dual
Semidefinite programming
Issue Date: Mar-2004
Citation: Zhou, G., Toh, K.-C. (2004-03). Polynomiality of an inexact infeasible interior point algorithm for semidefinite programming. Mathematical Programming 99 (2) : 261-282. ScholarBank@NUS Repository. https://doi.org/10.1007/s10107-003-0431-5
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.
Source Title: Mathematical Programming
URI: http://scholarbank.nus.edu.sg/handle/10635/103947
ISSN: 00255610
DOI: 10.1007/s10107-003-0431-5
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

13
checked on Nov 15, 2018

WEB OF SCIENCETM
Citations

13
checked on Dec 25, 2017

Page view(s)

20
checked on Nov 16, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.