Optimization Online


Polynomiality of an inexact infeasible interior point algorithm for semidefinite programming

Guanglu Zhou (matzgl***at***math.nus.edu.sg)
Kim-Chuan Toh (mattohkc***at***math.nus.edu.sg)

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

Keywords: semidefinite programming, primal-dual, infeasible interior point method

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: Technical Report No. 784, Department of Mathematics, National University of Singapore, December 2001.

Download: [Compressed Postscript]

Entry Submitted: 01/14/2002
Entry Accepted: 01/15/2002
Entry Last Modified: 01/14/2002

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society