“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 16446
School of Mathematics
  Title:   An \MboxO\Left(\SqrtR\Br\Cond(G)1/4\Log \Varepsilon−1\Right)‎ ‎Iteration Predictor-Corrector Interior-Point Method With A New One-Norm Neighborhood‎ ‎For Symmetric Cone Optimization
  Author(s):  Marzieh Sayadi Shahraki (Joint with H. Mansouri)
  Status:   To Appear
  Journal: Optimization
  Supported by:  IPM
  Abstract:
In this paper‎, ‎we propose a predictor-corrector interior-point method for symmetric‎ ‎cone optimization‎. ‎The proposed algorithm is based on a new‎ ‎one-norm neighborhood‎, ‎which is an even wider neighborhood than a‎ ‎given negative infinity neighborhood‎. ‎The convergence is shown‎ ‎for a commutative class of search directions‎, ‎which includes the‎ ‎Nesterov-Todd direction and the xs and sx directions‎. ‎We show‎ ‎that the algorithm has O\br√r\br\cond(G)1/4logε−1 iteration complexity bound which is better‎ ‎than that of the usual wide neighborhood algorithm‎ ‎O\brr√{\cond(G)}logε−1‎. ‎To our‎ ‎knowledge‎, ‎these are the best complexity results obtained so far‎ ‎for the solution of SCO‎. ‎We prove that‎, ‎besides the predictor steps‎, ‎each corrector step also reduces the duality gap by a rate of 1−[1/(O\br√r)]‎. ‎Finally‎, ‎numerical experiments showthat the proposed algorithm is efficient‎ ‎and reliable‎.

Download TeX format
back to top
scroll left or right