Polynomiality of an inexact infeasible interior point algorithm for semidefinite programming

被引：0
作者：
Guanglu Zhou
Kim-Chuan Toh
机构：
[1] Singapore-MIT Alliance,High Performance Computation for Engineered Systems
[2] National University of Singapore,Department of Mathematics
来源：
Mathematical Programming | 2004年 / 99卷
关键词：
semidefinite programming; primal-dual; infeasible interior point method; inexact search direction; polynomial complexity;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
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(n2ln(1/ε)) iterations. This bound of our algorithm is the same as that of the exact infeasible interior point algorithms proposed by Y. Zhang.
引用
收藏
页码：261 / 282
页数：21
相关论文
共 17 条
[1]  
Freund undefined(1999)undefined Math. Oper. Res. 24 50-undefined
[2]  
Helmberg undefined(1996)undefined SIAM J. Optim. 6 342-undefined
[3]  
Gu undefined(2000)undefined SIAM J. Optim. 10 462-undefined
[4]  
Kojima undefined(1997)undefined SIAM J. Optim. 7 86-undefined
[5]  
Kojima undefined(1999)undefined Math. Program. 85 51-undefined
[6]  
Korzak undefined(2000)undefined SIAM J. Optim. 11 133-undefined
[7]  
Mizuno undefined(1994)undefined Math. Program. 67 52-undefined
[8]  
Mizuno undefined(1999)undefined Math. Program. 84 105-undefined
[9]  
Monteiro undefined(1997)undefined SIAM J. Optim. 7 663-undefined
[10]  
Monteiro undefined(1999)undefined SIAM J. Optim. 9 551-undefined
12