Polynomiality of an inexact infeasible interior point algorithm for semidefinite programming

• 成果类型: Article
• 署名作者: Zhou, GL; Toh, KC
• 署名单位: Nanyang Technological University; Massachusetts Institute of Technology (MIT); Singapore-MIT Alliance for Research & Technology Centre (SMART); National University of Singapore
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-003-0431-5
• 发表日期: 2004
• 页码: 261-282
• 关键词: linear complementarity-problem; search directions; CONVERGENCE; computation

摘要

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 epsilon-approximate solution of an SDP in O(n(2)ln(1/epsilon)) iterations. This bound of our algorithm is the same as that of the exact infeasible interior point algorithms proposed by Y. Zhang.