数学物理学报(英文版)

• 论文 • 上一篇    下一篇

AN INFEASIBLE-INTERIOR-POINT PREDICTOR-CORRECTOR ALGORITHM FOR THE SECOND-ORDER CONE PROGRAM

迟晓妮; 刘三阳   

  1. 西安电子科技大学数学系, 西安 710071
  • 收稿日期:2006-01-04 修回日期:2006-12-31 出版日期:2008-07-20 发布日期:2008-07-20
  • 通讯作者: 迟晓妮
  • 基金资助:

    Supported by the National Science Foundation (60574075, 60674108)

AN INFEASIBLE-INTERIOR-POINT PREDICTOR-CORRECTOR ALGORITHM FOR THE SECOND-ORDER CONE PROGRAM

Chi Xiaoni; Liu Sanyang   

  1. Department of Mathematical Sciences, Xidian University, Xi'an 710071, China
  • Received:2006-01-04 Revised:2006-12-31 Online:2008-07-20 Published:2008-07-20
  • Contact: Chi Xiaoni

摘要:

A globally convergent infeasible-interior-point predictor-corrector algorithm is presented for the second-order cone programming (SOCP) by using the Alizadeh--Haeberly--Overton (AHO) search direction. This algorithm does not require the feasibility of the initial points and iteration points. Under suitable assumptions, it is shown that the algorithm can find an ε-approximate solution of an SOCP in at most O(\sqrt{n}\ln(ε0/ε)) iterations. The iteration-complexity bound of our algorithm is almost the same as the best known bound of feasible interior point algorithms for the SOCP.

关键词: Second-order cone programming, infeasible-interior-point algorithm,
predictor-corrector algorithm,
global convergence

Abstract:

A globally convergent infeasible-interior-point predictor-corrector algorithm is presented for the second-order cone programming (SOCP) by using the Alizadeh--Haeberly--Overton (AHO) search direction. This algorithm does not require the feasibility of the initial points and iteration points. Under suitable assumptions, it is shown that the algorithm can find an ε-approximate solution of an SOCP in at most O(\sqrt{n}\ln(ε0/ε)) iterations. The iteration-complexity bound of our algorithm is almost the same as the best known bound of feasible interior point algorithms for the SOCP.

Key words: Second-order cone programming, infeasible-interior-point algorithm,
predictor-corrector algorithm,
global convergence

中图分类号: 

  • 90C25