首页 | 本学科首页   官方微博 | 高级检索  
     检索      

Neighborhood-following algorithms for linear programming
作者姓名:Al Wenbao School of Science  Beijing University of Posts and Telecommunications  Beijing  China
作者单位:Al Wenbao School of Science,Beijing University of Posts and Telecommunications,Beijing 100876,China
基金项目:国家自然科学基金,中国科学院知识创新工程项目
摘    要:In this paper, we present neighborhood-following algorithms for linear programming. When the neighborhood is a wide neighborhood, our algorithms are wide neighborhood primal-dual interior point algorithms. If the neighborhood degenerates into the central path, our algorithms also degenerate into path-following algorithms. We prove that our algorithms maintain the O(n~(1/2)L)-iteration complexity still, while the classical wide neighborhood primal-dual interior point algorithms have only the O(nL)-iteration complexity. We also proved that the algorithms are quadratic convergence if the optimal vertex is nondegenerate. Finally, we show some computational results of our algorithms.


Neighborhood-following algorithms for linear programming
Al Wenbao School of Science,Beijing University of Posts and Telecommunications,Beijing ,China.Neighborhood-following algorithms for linear programming[J].Science in China(Mathematics),2004,47(6):812-820.
Authors:Email author<" target="_blank">Wenbao AiEmail author<
Institution:School of Science, Beijing University of Posts and Telecommunications, Beijing 100876, China
Abstract:In this paper, we present neighborhood-following algorithms for linear programming. When the neighborhood is a wide neighborhood, our algorithms are wide neighborhood primal-dual interior point algorithms. If the neighborhood degenerates into the central path, our algorithms also degenerate into path-following algorithms. We prove that our algorithms maintain the O(n~(1/2)L)-iteration complexity still, while the classical wide neighborhood primal-dual interior point algorithms have only the O(nL)-iteration complexity. We also proved that the algorithms are quadratic convergence if the optimal vertex is nondegenerate. Finally, we show some computational results of our algorithms.
Keywords:linear programming  primal-dual interior point methods  wide neighborhood methods  quadratic convergence  
本文献已被 CNKI 万方数据 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号