线性规划的邻域跟踪算法被引量：12

导出

摘要提出了线性规划的邻域跟踪算法.当这个邻域是宽邻域时,该算法就是宽邻域原始-对偶内点算法;如果这个邻域退化成中心路径,则算法就退化成中心路径跟踪算法.证明了该算法具有O( nL)次迭代复杂性,而经典的宽邻域算法是O(nL)次迭代复杂性.也证明了该算法在非退化条件下是二次收敛的,并给出了一些计算结果.

作者艾文宝

机构地区北京邮电大学理学院教学部

出处《中国科学（A辑）》 CSCD 北大核心 2004年第1期40-47,共8页 Science in China(Series A)

基金国家自然科学基金资助项目(批准号:19731010)

关键词线性规划邻域跟踪算法原始-对偶内点算法宽邻域算法二次收敛

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

引文网络
相关文献

参考文献12

1[1]Kojima M, Mizuno S, Yoshise A. A polynomial-time algorithm for a class of linear complementarity problems. Mathematical Programming, 1989, 44:1～26 被引量：1
2[2]Megiddo N. Pathways to the optimal set in linear programming. In: Megiddo N, ed. Progression Mathematical Programming: Interior Point and Related Methods. New York: Springer-Verlag, 1989. 131～158 被引量：1
3[3]Monteiro R D C, Adler I. Interior path following primal-dual algorithms, part Ⅰ: linear programming.Mathematical Programming, 1989, 44:27～41 被引量：1
4[4]Monteiro R D C, Adler I. Interior path following primal-dual algorithms, Part Ⅱ: convex quadratic programming. Mathematical Programming, 1989, 44:43～66 被引量：1
5[5]Wright S J. Primal-Dual Interior-Point Methods. Philadephia: SIAM Publications, 1997 被引量：1
6[6]Mizuno S, Todd M J, Ye Y. On adaptive step primal-dual interior-point algorithms for linear programming.Mathematics of Operations Research, 1993, 18:964～981 被引量：1
7[7]Gonzaga C C. The largest step path following algorithm for monotone linear complementarity problems.Mathematical Programming, 1997, 76:309～332 被引量：1
8[8]Sturm J F, Zhang S. On a wide region of centers primal-dual interior point algorithms for linear programming. Tinbergen Institute Rotterdam, Erasmus University, Rotterdam, The Netherlands, 1995 被引量：1
9[9]Hung P, Ye Y. An asymptotical O(√nL)-iteration path-following linear programming algorithm that use wide neighborhoods. SIAM J Optimization, 1996, 6:570～586 被引量：1
10[10]Ye Y. Interior Point Algorithms: Theory and Analysis. New york: A Wiley-Interscience Publication, 1997 被引量：1

同被引文献99

1夏少刚.对“求解线性规划问题的一种全搜索方法”的改进与修正[J].运筹与管理,2004,13(3):10-14. 被引量：3
2高国成,王卓鹏,刘晓妍.线性规划问题的规范型算法[J].运筹与管理,2004,13(3):35-38. 被引量：5
3唐建国.线性规划的符号跟踪算法[J].运筹与管理,2005,14(3):55-59. 被引量：3
4唐焕文,张立卫.求解线性规划的极大熵方法[J].计算数学,1995,17(2):160-172. 被引量：15
5唐建国.线性规划的目标函数最速递减算法[J].运筹与管理,2005,14(4):55-59. 被引量：9
6刘明华,罗旺,肖淑芳.基于数学形态学的图象骨架提取与重建[J].井冈山学院学报（综合版）,2005,26(10M):33-35. 被引量：3
7盛松柏.解线性不等式组的松弛直交变换法[J].高等学校计算数学学报,1990,12(4):370-379. 被引量：2
8Kojima M,Mizuno S,Yoshise A.A primal-dual interior point algorithm for linear programming[C].N.Megiddo.In Progress in Mathematical Progmming:Interior Point and Related Methods.New York:Springer-Verlag,1989.29-47. 被引量：1
9Megiddo N.Pathways to the optimal set in linear programming[C].N.Megisso.In Progress in Mathematical Programming:Interior Point and Related Methods.New York:Springer-Verlag,1989.131-158. 被引量：1
10Kojima M,Mizuno S,Yoshise A.A polynomial-time algorithm for a class of linear complementarity problems[J].Math.Program.,1989,44:1-26. 被引量：1

引证文献12

1唐建国.线性规划的目标函数最速递减算法[J].运筹与管理,2005,14(4):55-59. 被引量：9
2黄有度,苏化明.线性规划的一种快速收敛的迭代算法[J].合肥工业大学学报（自然科学版）,2005,28(9):1204-1209.
3唐建国.线性规划的约束条件“滚雪球”算法[J].数学的实践与认识,2006,36(4):135-143.
4李政广,吴黎明,赖南辉,王立萍,程伟涛.骨架提取在IC晶片缺陷机器视觉识别中的研究[J].半导体技术,2007,32(4):324-327. 被引量：6
5刘长河.线性互补问题的邻域跟踪算法[J].四川理工学院学报（自然科学版）,2010,23(2):140-143. 被引量：2
6刘长河,丁艳风.求解单调线性互补问题的邻域跟踪内点算法[J].陕西理工学院学报（自然科学版）,2010,26(2):72-77.
7刘长河,刘红卫,尚有林.对称锥规划的邻域跟踪算法[J].中国科学：数学,2013,43(7):691-702. 被引量：2
8常铮,李敬华.线性互补问题的Mehrotra型预估矫正算法[J].纺织高校基础科学学报,2013,26(4):498-501.
9汪威威,刘红卫,毕红梅.线性规划基于修正牛顿方向的宽邻域内点算法[J].吉林大学学报（理学版）,2014,52(3):408-412.
10刘长河,任建林.线性规划的一个宽邻域预估-矫正内点算法[J].平顶山学院学报,2014,29(2):6-9.

二级引证文献22

1高雷阜,于冬梅.一种求解对称锥互补问题的算法[J].系统仿真学报,2015,27(5):1050-1056.
2唐建国.线性规划的约束条件“滚雪球”算法[J].数学的实践与认识,2006,36(4):135-143.
3夏少刚,郑直,费威.与“求线性规划问题可行基的一种方法”的再商榷[J].运筹与管理,2006,15(3):16-18. 被引量：1
4罗进,张志军,刘任河.单纯形法中确定主元素的两个新法则[J].武汉工程大学学报,2008,30(1):122-124. 被引量：3
5陈英霞,朱维钧.关于单纯形算法的两点思考[J].怀化学院学报,2008,27(11):26-27.
6曹岩,姚慧,党军弟.Delphi环境下目标规划图解法算法程序的开发[J].计算机应用与软件,2009,26(6):198-200.
7肖婧,谭阳红.基于新特征提取法和量子神经网络的手写数字识别[J].电子测量技术,2009,32(6):84-87. 被引量：11
8周学松,赵恒.线性规划中一个避免人工变元的方法的改进[J].运筹与管理,2011,20(5):31-38. 被引量：1
9双小川,张克.基于统计和结构特征的手写数字识别研究[J].计算机工程与设计,2012,33(4):1533-1537. 被引量：17
10张朝勇,苏真伟,乔丽,陈谋钦.一种基于LED和线激光的钢轨表面缺陷检测系统[J].科学技术与工程,2012,20(36):9877-9880. 被引量：8

1刘长河.线性互补问题的邻域跟踪算法[J].四川理工学院学报（自然科学版）,2010,23(2):140-143. 被引量：2
2常铮,李敬华.线性互补问题的Mehrotra型预估矫正算法[J].纺织高校基础科学学报,2013,26(4):498-501.
3马晓珏,刘红卫.线性规划的邻域跟踪算法在退化情形下的局部收敛性[J].吉林大学学报（理学版）,2016,54(4):732-736.
4刘长河,丁艳风.求解单调线性互补问题的邻域跟踪内点算法[J].陕西理工学院学报（自然科学版）,2010,26(2):72-77.
5刘长河,刘红卫,尚有林.对称锥规划的邻域跟踪算法[J].中国科学：数学,2013,43(7):691-702. 被引量：2
6汪威威,刘红卫,毕红梅.线性规划基于修正牛顿方向的宽邻域内点算法[J].吉林大学学报（理学版）,2014,52(3):408-412.
7张艺.线性约束凸二次规划的一个原始-对偶内点算法[J].宁波大学学报（理工版）,2004,17(3):249-252. 被引量：1
8刘长河,任建林.线性规划的一个宽邻域预估-矫正内点算法[J].平顶山学院学报,2014,29(2):6-9.
9刘长河,刘红卫,朱见广.具有O(n～(1/2)L)复杂性的Mehrotra型预估-矫正算法[J].吉林大学学报（理学版）,2011,49(4):633-637. 被引量：4
10刘新泽,刘红卫,刘长河.P_*(κ)线性互补问题的预估-校正内点算法[J].吉林大学学报（理学版）,2013,51(5):789-794.

中国科学（A辑）

2004年第1期

浏览历史

内容加载中请稍等...

线性规划的邻域跟踪算法被引量：12

参考文献12

同被引文献99

引证文献12

二级引证文献22

相关作者

相关机构

相关主题

浏览历史

线性规划的邻域跟踪算法 被引量：12

参考文献12

同被引文献99

引证文献12

二级引证文献22

相关作者

相关机构

相关主题

浏览历史

线性规划的邻域跟踪算法被引量：12