How bad is a gradient algorithm for linear programming?
Peter A. Bruijs(p.a.bruijswxs.nl)
Abstract: In their 1972 paper ‘How good is the simplex algorithm ?’ Klee and Minty present a class of problems the simplex algorithm for linear programming (LP) is not able to solve in a polynomial way. Later developments have resulted in algorithms by Khachiyan and Karmarkar that do solve LP in a polynomial way, although the bounds they generate are not exclusively based on LP’s problem dimensions m and n. Until now it is an open question whether there exists a strongly polynomial algorithm solving LP in O(m,n) operations. In this paper we try to identify characteristics of present algorithms that might hinder in attaining such a result, and look at the possibilities a strongly gradient oriented algorithm might offer in this respect.
Keywords: linear programming - simplex algorithm - ellipsoid method - interior-point methods - gradient methods - computational complexity
Category 1: Linear, Cone and Semidefinite Programming
Category 2: Linear, Cone and Semidefinite Programming (Linear Programming )
Citation: unpublished report no actual affiliation, produced after retirement april 2011
Entry Submitted: 04/20/2011
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|