一种新的求解凸二次规划的原始-对偶多项式内点算法  

A New Primal-Dual Polynomial Algorithm for Convex Quadratic Programming

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

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

出　　处：《数学的实践与认识》2012年第17期206-210,共5页Mathematics in Practice and Theory

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

摘　　要：对凸二次规划问题提出了一种新的原始-对偶路径跟踪算法,算法迭代方向的求解是不同于传统的牛顿法,而是借助于一种新的工具找到搜寻方向.最后证明了算法具有多项式复杂性.In this paper,we present a new primal-dual path-following method to solve the convex quadratic programming. The new method is based on a technique for finding the search directions not different to the classical Newton method. At last,we prove that the algorithm has polynomial-time complexity.

关 键 词：凸二次规划 内点算法 路径跟踪算法 多项式复杂性 

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