  


A Polynomial ArcSearch InteriorPoint Algorithm for Linear Programming
Yaguang Yang(yaguang.yangverizon.net) Abstract: In this paper, ellipse is used to approximate the central path of the linear programming. An interiorpoint algorithm is devised to search the optimizers along the ellipse. The algorithm is proved to be polynomial with the complexity bound $O(n^{\frac{1}{2}}\log(1/\epsilon))$. Numerical test is conducted for problems in Netlib. For most tested Netlib problems, the result shows that the new algorithm uses less iteration to converge than the Matlab optimization toolbox {\tt linprog} which implements the stateofart Mehrotra's predictorcorrector algorithm. For all the tested problems, the number of total iterations using the new algorithm is about 20$\%$ fewer than the one using {\tt linprog}. Keywords: Arcsearch, interiorpoint method, polynomial algorithm, linear programming. Category 1: Linear, Cone and Semidefinite Programming (Linear Programming ) Citation: Download: [PDF] Entry Submitted: 11/27/2010 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  