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

Journal of Jilin University Science Edition

Previous Articles Next Articles

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

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

CLC Number:

O221.1

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]	YONG Longquan. High Order Newton Method for Solving Linear ProgrammingBased on Uniform Smooth Approximation Function from Above#br# [J]. Journal of Jilin University Science Edition, 2019, 57(2): 265-270.
[2]	MA Xiaojue, LIU Hongwei. Local Convergence of the NeighborhoodFollowing Algorithmfor Linear Programming under Degenerate Cases [J]. Journal of Jilin University Science Edition, 2016, 54(04): 732-736.
[3]	LIU Yubao, QIN Guihe. Adaptive Differential Evolution Algorithm forReliability Redundancy Optimization [J]. Journal of Jilin University Science Edition, 2016, 54(01): 70-76.
[4]	LI Jianhua, LI Zipeng, LV Xianrui, ZHANG Hui. A PrimalDual Interior Point Method with Parameter Perturbationfor Solving a Class of General Nonlinear Programming Problems [J]. Journal of Jilin University Science Edition, 2015, 53(06): 1099-1104.
[5]	YANG Ximei, LIU Hongwei, LIU Changhe. ArcSearch InteriorPoint Algorithm [J]. Journal of Jilin University Science Edition, 2014, 52(04): 693-697.
[6]	LIU Xinze, LIU Hongwei, LIU Changhe. A PredictorCorrector InteriorPoint Algorithm forP*(κ)Linear Complementarity Problems [J]. Journal of Jilin University Science Edition, 2013, 51(05): 789-794.
[7]	JIN Jian-Lu, TAN Jia-Wei, HE Chi, LIU Qiang-Fu. Aggregate Homotopy InteriorPoint Method forGeneral Nonlinear Programming Problems [J]. J4, 2011, 49(06): 1044-1052.
[8]	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.
[9]	JIANG Zhi-Xia, LI Jun, ZHANG Shan. An Improved Primaldual Point Method [J]. J4, 2009, 47(4): 677-682.
[10]	FENG Zixuan, WANG Cailing, JI Shuguan. Interiorpoint QuasiNewton Method of Modified Augmented Lagrangian Function [J]. J4, 2009, 47(02): 245-247.
[11]	ZHANG Shan, JIANG Zhixia,, LIU Yuanhui. Primaldual Point Method for Nonlinear Programming [J]. J4, 2007, 45(05): 717-722.
[12]	SU Menglong, ZHAO Liqin, L Xianrui. A Combined Maximum Entropy Homotopy Method for Solving the KKT Point of a Class of Nonconvex Nonlinear Programming Problems [J]. J4, 2006, 44(05): 710-714.
[13]	SHANG Yu-feng,, YU Bo. Boundary Moving Combined Homotopy Method for Nonconvex Nonlinear Programming and Its Convergence [J]. J4, 2006, 44(03): 357-361.
[14]	CAO Xiao-wei, SUN Ji-gui. Design and Implementation of SolvingCheckout Employee Scheduling Problem [J]. J4, 2002, 40(01): 61-66.
[15]	HUANG Qing-dao, LAKU Xian-rui, WANG Guo-ming. Dual Simplex Method of Linear Programmingwith Bounded Variabl [J]. J4, 2002, 40(01): 44-47.

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

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Metrics

Comments

Recommended 0