基于全牛顿步长求解凸二次规划问题的不可行内点算法  

An Infeasible Interior-Point Algorithm for Convex Quadratic Programming with Full-Newton Step

作　　者：龚小玉[1] 孙立民[1] 胡振鹏[2] 王先甲[3] 

机构地区：[1]广东石油化工学院理学院,广东茂名525000 [2]武汉大学水利水电学院,湖北武汉430072 [3]武汉大学经济与管理学院,湖北武汉430072

出　　处：《数学的实践与认识》2013年第24期92-97,共6页Mathematics in Practice and Theory

基　　金：国家自然科学基金(71071119)

摘　　要：借助于全牛顿步长对凸二次规划问题提出了一种新的不可行内点算法.算法主要迭代由可行迭代步和中心路径邻域迭代步组成.其优点是线性搜寻方向是不需要的.最后证明算法迭代复杂性为O(nlogn/ε),与目前最好的不可行内点算法复杂性一致.In this paper, we describe a new infeasible interior-point algorithm to solve a convex quadratic programming（QP）. Each iteration consists of a feasibility step and several centrality steps.Since the algorithm uses only full Newton steps, it has the advantage that no line-search are needed. At last, we prove the algorithm has O（nlog n/ε） polynomial complex- ity, which coincides with the best known one for infeasible interior-point algorithm.

关 键 词：凸二次规划 不可行内点算法 全牛顿步长 多项式复杂性 

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