二次锥规划的不可行内点算法  

An infeasible interior point algorithm for the second-order cone programming

作　　者：迟晓妮[1] 刘三阳[1] 李炳杰[2] 

机构地区：[1]西安电子科技大学数学科学系,陕西西安710071 [2]空军工程大学理学院,陕西西安710051

出　　处：《兰州大学学报（自然科学版）》2007年第4期136-139,共4页Journal of Lanzhou University(Natural Sciences)

基　　金：国家自然科学基金(69972036).

摘　　要：给出二次锥规划的一种不可行内点算法并证明该算法是多项式时间算法.利用本算法需O(n^(1/2)lnε^(-1))次迭代就可找到问题的ε-近似解,其迭代复杂性界与现有的二次锥规划可行内点算法的复杂性界相同.An infeasible interior point algorithm for the second-order cone programming is presented. It is shown that this algorithm is a polynomial-time algorithm which can algorithm can find an ε-approximate solution in O（√nlnε^-1） iterations. The iteration complexity bound is the same as that of the feasible interior point methods available.

关 键 词：二次锥规划 不可行内点算法 多项式时间算法 

分 类 号：O221.7[理学—运筹学与控制论]