求解凸二次规划问题的一种加权路径跟踪内点算法  

A Weighted-Path-Following Interior-Point Algorithm for Convex Quadratic Optimization

作　　者：金正静[1] 白延琴[2] 韩伯顺[2] 

机构地区：[1]浙江林学院理学院数学系,临安311300 [2]上海大学理学院数学系,上海200444

出　　处：《运筹学学报》2010年第1期55-65,共11页Operations Research Transactions

基　　金：国家自然科学基金(No.10771133)资助;教育部博士点基金资助(No.200802800010);上海市重点学科资助(No.S30104);浙江林学院科研项目(No.2009FR044;No.2451008040)资助

摘　　要：基于Darvay提出用加权路径跟踪内点算法解线性规划问题的相关工作,本文致力于将此算法推广于解凸二次规划问题,并证明此算法具有局部二次收敛速度和目前所知的最好的多项式时间算法复杂性.Inspired by Darvay＇s work that developed a weighted path-following interior point algorithm for solving Linear Programming, we extend in this paper the algorithm of Darvay to solve convex quadratic optimization problem and show that this algorithm has local quadratic convergence rate and the favorable polynomial complexity bound.

关 键 词：运筹学 凸二次规划 小步校正算法 纯Newton步 加权路径跟踪内点算法 多项式时间算法复杂性 

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