期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

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

Wide-Neighborhood Interior-Point Algorithm Based on Modified Newton Direction for Linear Programming
下载PDF
导出
摘要 通过修正经典宽邻域算法的搜索方向,提出一种新的求解线性规划问题的宽邻域内点算法,并对算法进行收敛性分析,证明了该算法具有经典宽邻域算法的迭代复杂性界O(nL).数值实验表明算法是有效的. Based on modifying the search direction of classic wide-neighborhood algorithm,a new wideneighborhood 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.
作者 汪威威 刘红卫 毕红梅
机构地区 西安电子科技大学数学与统计学院 西安工业大学理学院 空军工程大学理学院
出处 《吉林大学学报（理学版）》 CAS CSCD 北大核心 2014年第3期408-412,共5页 Journal of Jilin University:Science Edition
基金 国家自然科学基金(批准号:61072144 61179040)
关键词 线性规划 内点算法 宽邻域算法 多项式复杂性 linear programming interior-point methods wide-neighborhood algorithm polynomial complexity
分类号 O221.1 [理学—运筹学与控制论]
  • 相关文献

参考文献8

  • 1Roos C, Tcrlaky T, Vial J P. Theory and Algorithms for Linear Optimization :An Interior Point Approach [M]. Chichcstcr:John Wiley & Sons,1 997.
  • 2Kojima M,Mizuno S,Yoshisc A. A Primal-Dual Interior Point Algorithm for Linear Programming [C]// Progress in Mathematical Programming Intcrior-Point and Related Methods. New York :Springer-Vcrlag,1988 :29-4 7.
  • 3Mizuno S,Todd M J,YE Yinyu. On A daptivc-Stcp Primal-Dual Intcrior-Point Algorithms for Linear Programming [J]. Math OpcrRcs,1993,18(4) :964-981.
  • 4艾文宝.线性规划的邻域跟踪算法[J].中国科学（A辑）,2004,34(1):40-47. 被引量：12
  • 5刘长河,刘红卫,朱见广.具有O(n～(1/2)L)复杂性的Mehrotra型预估-矫正算法[J].吉林大学学报（理学版）,2011,49(4):633-637. 被引量：4
  • 6ZHANG Lipu,XU Yinghong.A Full-Ncwton Step Intcrior-Point Algorithm Based on Modified Newton Direction [J]. Operations Rcscarch Letters,2011,39(5): 318-322.
  • 7Wright S J. Primal-Dual Intcrior-Point Methods [M]. Philadelphia:SIAM,1 997.
  • 8YE Yinyu,Todd M J,Mizuno S. An O√nL-Itcration Homogeneous and Self-dual Linear Programming Algorithm [J]. Math Opcr Res,1 994,1 9( 1 ): 53-67.

二级参考文献13

  • 1Al WenbaoSchool of Science, Beijing University of Posts and Telecommunications, Beijing 100876, China.Neighborhood-following algorithms for linear programming[J].Science China Mathematics,2004,47(6):812-820. 被引量：7
  • 2[1]Kojima M, Mizuno S, Yoshise A. A polynomial-time algorithm for a class of linear complementarity problems. Mathematical Programming, 1989, 44:1～26
  • 3[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
  • 4[3]Monteiro R D C, Adler I. Interior path following primal-dual algorithms, part Ⅰ: linear programming.Mathematical Programming, 1989, 44:27～41
  • 5[4]Monteiro R D C, Adler I. Interior path following primal-dual algorithms, Part Ⅱ: convex quadratic programming. Mathematical Programming, 1989, 44:43～66
  • 6[5]Wright S J. Primal-Dual Interior-Point Methods. Philadephia: SIAM Publications, 1997
  • 7[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
  • 8[7]Gonzaga C C. The largest step path following algorithm for monotone linear complementarity problems.Mathematical Programming, 1997, 76:309～332
  • 9[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
  • 10[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

共引文献13

吉林大学学报（理学版）
2014年 第3期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部