弧搜索内点算法

吉林大学学报(理学版)

弧搜索内点算法

杨喜美¹, 刘红卫¹, 刘长河²

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

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

ArcSearch InteriorPoint Algorithm

YANG Ximei¹, LIU Hongwei¹, LIU Changhe²

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:2013-10-10 Online:2014-07-26 Published:2014-09-26
Contact: LIU Hongwei E-mail:hwliu@mail.xidian.edu.cn

摘要/Abstract

摘要：

利用弧搜索内点算法对线性规划问题进行求解, 得到该算法的多项式复杂度为O(n^3/4L). 该算法在中心路径的一个宽邻域内, 沿椭圆近似寻找线性规划的最优解. 数值实验表明了该算法的有效性.

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

Abstract:

The arcsearch interiorpoint algorithm was used to solve the linear programming problem and the iteration complexity O(n^3/4L) was obtained for this algorithm. The proposed algorithm was used to search for the optimizers along the ellipses in a wide neighborhood of the central path. The numerical results show that this algorithm is efficient.

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

中图分类号:

O221.1

杨喜美, 刘红卫, 刘长河. 弧搜索内点算法[J]. 吉林大学学报(理学版), 2014, 52(04): 693-697.

YANG Ximei, LIU Hongwei, LIU Changhe. ArcSearch InteriorPoint Algorithm[J]. Journal of Jilin University Science Edition, 2014, 52(04): 693-697.

[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(03): 408-412.
[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.