具有O(nL)复杂性的Mehrotra型预估-矫正算法

J4 ›› 2011, Vol. 49 ›› Issue (04): 633-637.

具有O(nL)复杂性的Mehrotra型预估-矫正算法

刘长河^1,2, 刘红卫¹, 朱见广¹

1. 西安电子科技大学数学系, 西安 710071； 2. 河南科技大学数学与统计学院, 河南洛阳 471003

收稿日期:2010-09-06 出版日期:2011-07-26 发布日期:2011-08-16
通讯作者: 刘红卫 E-mail:hwliu@mail.xidian.edu.cn

MehrotraType PredictorCorrector Algorithm withO(nL)Iteration Complexity

LIU Changhe^1,2, LIU Hongwei^1, ZHU Jianguang¹

1. Department of Mathematics, Xidian University, Xi’an 710071, China； 2. School of Mathematics and Statistics, Henan University of Science and Technology, Luoyang 471003, Henan Province, China

Received:2010-09-06 Online:2011-07-26 Published:2011-08-16
Contact: LIU Hongwei E-mail:hwliu@mail.xidian.edu.cn

摘要/Abstract

摘要：

针对内点方法在理论和实践之间存在着计算效果好的算法在理论上具有较差复杂性的矛盾, 提出一种求解线性规划问题的Mehrotra型预估-矫正内点算法, 并证明了该算法的迭代复杂性是O(nL). 数值实验结果验证了算法的有效性.

关键词: 线性规划, 内点方法, Mehrotra型预估矫正算法, 宽邻域算法, 多项式复杂性

Abstract:

In interior point methods, there is an inconsistency between theory and practice: fast algorithms in practice may actually render
worse complexity bounds. We proposed a new Mehrotratype predictorcorrector interior point algorithm for linear programming. The O(nL)iteration complexity of the algorithm was given, the same as the best complexity result for any interior point method. The numerical experiments show that this algorithm has a superior practical performance.

Key words: linear programming, interior point methods, Mehrotratype predictorcorrector algorithm, wide neighborhood algorithm, polynomial complexity

中图分类号:

O221.1

刘长河, 刘红卫, 朱见广. 具有O(nL)复杂性的Mehrotra型预估-矫正算法[J]. J4, 2011, 49(04): 633-637.

LIU Chang-He, LIU Gong-Wei, SHU Jian-An. MehrotraType PredictorCorrector Algorithm withO(nL)Iteration Complexity[J]. J4, 2011, 49(04): 633-637.

[1]	雍龙泉. 基于上方一致光滑逼近函数的高阶牛顿法求解线性规划[J]. 吉林大学学报(理学版), 2019, 57(2): 265-270.
[2]	苏孟龙, 吕显瑞. 同伦内点方法求解一类无界区域上的多目标规划问题[J]. 吉林大学学报(理学版), 2019, 57(06): 1367-1371.
[3]	马晓珏, 刘红卫. 线性规划的邻域跟踪算法在退化情形下的局部收敛性[J]. 吉林大学学报(理学版), 2016, 54(04): 732-736.
[4]	刘玉宝, 秦贵和. 面向可靠性冗余优化的自适应差分进化算法[J]. 吉林大学学报(理学版), 2016, 54(01): 70-76.
[5]	李建华, 李子鹏, 吕显瑞, 张慧. 带参数扰动的原始对偶内点算法[J]. 吉林大学学报(理学版), 2015, 53(06): 1099-1104.
[6]	杨喜美, 刘红卫, 刘长河. 弧搜索内点算法[J]. 吉林大学学报(理学版), 2014, 52(04): 693-697.
[7]	汪威威, 刘红卫, 毕红梅. 线性规划基于修正牛顿方向的宽邻域内点算法[J]. 吉林大学学报(理学版), 2014, 52(03): 408-412.
[8]	庞天一, 孙钊, 温静雅, 东双, 赵文晋, 李鱼. 规模化养殖场沼气工程替代传统模式发电的GHG减排不确定性优化模型[J]. J4, 2013, 51(01): 153-157.
[9]	赵雪, 张春阳, 张树功. 弱拟法锥条件下解多目标规划问题的同伦方法[J]. J4, 2012, 50(4): 663-666.
[10]	雍龙泉, 刘三阳, 张建科, 陈涛, 邓方安. 绝对值方程的一种严格可行内点算法[J]. J4, 2012, 50(05): 887-891.
[11]	金鉴禄, 谭佳伟, 贺莉, 刘庆怀. 一般非线性规划问题的凝聚同伦内点方法[J]. J4, 2011, 49(06): 1044-1052.
[12]	苏孟龙, 赵立芹, 吕显瑞. 同伦内点方法求解一类无界非凸集合上的不动点问题[J]. J4, 2011, 49(05): 839-843.
[13]	刘兵兵, 郭亚君. 灰色多随从二层线性规划问题及其解法[J]. J4, 2011, 49(04): 625-632.
[14]	姜志侠, 李军, 张珊. 一个改进的原始对偶内点方法[J]. J4, 2009, 47(4): 677-682.
[15]	冯子玹, 王彩玲, 冀书关. 修正的增广拉格朗日函数内点拟牛顿法[J]. J4, 2009, 47(02): 245-247.