线性规划基于修正牛顿方向的宽邻域内点算法

吉林大学学报(理学版)

线性规划基于修正牛顿方向的宽邻域内点算法

汪威威^1,2, 刘红卫¹, 毕红梅³

1. 西安电子科技大学数学与统计学院, 西安710126; 2. 西安工业大学理学院, 西安 710032；3. 空军工程大学理学院, 西安 710051

收稿日期:2013-08-29 出版日期:2014-05-26 发布日期:2014-08-27
通讯作者: 刘红卫 E-mail:hwliu@mail.xidian.edu.cn

WideNeighborhood InteriorPoint Algorithm Based on Modified Newton Direction for Linear Programming

WANG Weiwei^1,2, LIU Hongwei¹, BI Hongmei³

1. School of Mathematics and Statistics, Xidian University, Xi’an 710126, China；2. School of Science, Xi’an Technological University, Xi’an
710032, China;3. School of Science, Air Force Engineering University, Xi’an 710051, China

Received:2013-08-29 Online:2014-05-26 Published:2014-08-27
Contact: LIU Hongwei E-mail:hwliu@mail.xidian.edu.cn

摘要/Abstract

摘要：

通过修正经典宽邻域算法的搜索方向, 提出一种新的求解线性规划问题的宽邻域内点算法, 并对算法进行收敛性分析, 证明了该算法具有经典宽邻域算法的迭代复杂性界O(nL). 数值实验表明算法是有效的.

关键词: 线性规划, 内点算法, 宽邻域算法, 多项式复杂性

Abstract:

Based on modifying the search direction of classic wideneighborhood algorithm, a new wideneighborhood interior point algorithm for linear programming was proposed. The convergence analysis of the new algorithm was presented. And the algorithm enjoys the iteration bound O(nL), the same as the complexity result for classic wideneighborhood interior point method. The numerical calculation shows that the new algorithm is efficient.

Key words: linear programming, interiorpoint methods, wideneighborhood algorithm, polynomial complexity

中图分类号:

O221.1

汪威威, 刘红卫, 毕红梅. 线性规划基于修正牛顿方向的宽邻域内点算法[J]. 吉林大学学报(理学版), 2014, 52(03): 408-412.

WANG Weiwei, LIU Hongwei, BI Hongmei. WideNeighborhood InteriorPoint Algorithm Based on Modified Newton Direction for Linear Programming[J]. Journal of Jilin University Science Edition, 2014, 52(03): 408-412.

[1]	雍龙泉. 基于上方一致光滑逼近函数的高阶牛顿法求解线性规划[J]. 吉林大学学报(理学版), 2019, 57(2): 265-270.
[2]	马晓珏, 刘红卫. 线性规划的邻域跟踪算法在退化情形下的局部收敛性[J]. 吉林大学学报(理学版), 2016, 54(04): 732-736.
[3]	刘玉宝, 秦贵和. 面向可靠性冗余优化的自适应差分进化算法[J]. 吉林大学学报(理学版), 2016, 54(01): 70-76.
[4]	李建华, 李子鹏, 吕显瑞, 张慧. 带参数扰动的原始对偶内点算法[J]. 吉林大学学报(理学版), 2015, 53(06): 1099-1104.
[5]	杨喜美, 刘红卫, 刘长河. 弧搜索内点算法[J]. 吉林大学学报(理学版), 2014, 52(04): 693-697.
[6]	刘新泽, 刘红卫, 刘长河. P*(κ)线性互补问题的预估-校正内点算法[J]. 吉林大学学报(理学版), 2013, 51(05): 789-794.
[7]	庞天一, 孙钊, 温静雅, 东双, 赵文晋, 李鱼. 规模化养殖场沼气工程替代传统模式发电的GHG减排不确定性优化模型[J]. J4, 2013, 51(01): 153-157.
[8]	雍龙泉, 刘三阳, 张建科, 陈涛, 邓方安. 绝对值方程的一种严格可行内点算法[J]. J4, 2012, 50(05): 887-891.
[9]	金鉴禄, 谭佳伟, 贺莉, 刘庆怀. 一般非线性规划问题的凝聚同伦内点方法[J]. J4, 2011, 49(06): 1044-1052.
[10]	刘兵兵, 郭亚君. 灰色多随从二层线性规划问题及其解法[J]. J4, 2011, 49(04): 625-632.
[11]	刘长河, 刘红卫, 朱见广. 具有O(nL)复杂性的Mehrotra型预估-矫正算法[J]. J4, 2011, 49(04): 633-637.
[12]	姜志侠, 李军, 张珊. 一个改进的原始对偶内点方法[J]. J4, 2009, 47(4): 677-682.
[13]	冯子玹, 王彩玲, 冀书关. 修正的增广拉格朗日函数内点拟牛顿法[J]. J4, 2009, 47(02): 245-247.
[14]	迟晓妮, 刘三阳, 张晓伟. 求解二次锥规划的非精确不可行内点法[J]. J4, 2007, 45(05): 743-747.
[15]	张珊, 姜志侠,, 刘元慧. 求解非线性规划的原始对偶内点法[J]. J4, 2007, 45(05): 717-722.