一类线性约束凸规划问题的内点算法及其计算复杂性

摘要：

对于满足尺度李谱希茨条件的一类线性约束凸规划问题,提出了一种原始-对偶内点算法.该算法所取牛顿方向与常见算法不同,该算法可以在任一内部可行点启动,并且全局收敛.当初始点靠近中心路径时,此算法便成为中心路径跟踪算法,总迭代次数为O(√nL),其中L是问题的输入长度.

关键词： 凸规划 内点算法 原始-对偶 路径跟踪法 全局收敛性 多项式时间算法 迭代复杂性

作者: 王浚岭

作者单位: 三峡大学理学院数学系(湖北宜昌)

会议类型: 国内会议

会议名称: 中国运筹学会第七届学术交流会

会议地点: 青岛

会议语种:中文

页码: 926-931

在线出版日期: 2004-10-01（万方平台首次上网日期，不代表论文的发表时间）