弧搜索内点算法

Journal of Jilin University Science Edition

Previous Articles Next Articles

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

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

CLC Number:

O221.1

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

[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]	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.
[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]	CHI Xiao ni, LIU Sanyang, ZHANG Xiao wei. An Inexact Infeasibleinteriorpoint Algorithm for Secondorder Cone Programming [J]. J4, 2007, 45(05): 743-747.
[12]	ZHANG Shan, JIANG Zhixia,, LIU Yuanhui. Primaldual Point Method for Nonlinear Programming [J]. J4, 2007, 45(05): 717-722.
[13]	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.
[14]	SHANG Yu-feng,, YU Bo. Boundary Moving Combined Homotopy Method for Nonconvex Nonlinear Programming and Its Convergence [J]. J4, 2006, 44(03): 357-361.
[15]	CAO Xiao-wei, SUN Ji-gui. Design and Implementation of SolvingCheckout Employee Scheduling Problem [J]. J4, 2002, 40(01): 61-66.

ArcSearch InteriorPoint Algorithm

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Metrics

Comments

Recommended 0